Bruno Marchal wrote:

>Proceeding that way you will run into trouble. But it is very easy to 
>find the k.
>Let us be specific and let us imagine you have already written in 
>Fortran a generator of all programs of the one-variable partial 
>computable functions: F1 F2 F3 F4 F5 F6 F7 ...
>The list of programs is P1 P2 P3 P4 P5 P6 ... Each Pi(n) computes  Fi(n)
>Now program G in "Fortran". It is something like that:
>Begin G
>Read X
>Call the generator of program up to X, giving PX
>Apply PX on X, and put the result in register 439
>Add 1 to the content of register 439
>Output the content of register 439
>Now, look at your list of programs Pi until you find it, and look at 
>his number code (where n is the number code of Pn by definition). 
>Finding your program in your list of programs should be easy given that 
>the list P1 P2 P3 ... is ordered lexicographicaly (by length, and by 
>alphabetical order for those of same length). So you can find it 
>easily. Is number code is the number k. If you run G on k, your fortran 
>interpreter will run for ever (and your fortran compiler will generate 
>a code which run for ever). Speaking just a little bit loosely.
Let's be more specific.
Begin G
Read X
Call generator of program which produces P1, P2, sequence. Select 
Program PX.
Compute the value PX(X).
Save the value into register 439
Add 1 to content of register 439. Call this value Y

Now look at the list of all programs P1(1), P2(2).... The scanning 
program could be:

i = 1                    (initiate counter i to 1)
Start Loop
If Pi(i) = Y then k=i; Exit
Else i=i+1
End if
End Loop

My point is that the loop will never end and you will never find k. If 
you did find k then Pk(k) = P(k)+1 which is impossible.
However, I don't see any problem in using P(x) for computing G(x) for any x

You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at

Reply via email to