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
>End
>
>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, P3..in 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 everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Mon Jun 12 2006 - 21:05:50 PDT