Re: *THE* PUZZLE (was: ascension, Smullyan, ...)

From: George Levy <>
Date: Sun, 11 Jun 2006 15:23:52 -0700

I went on a 10 day trip during which I had no access to email... a lot
has happened on this list since then.

Bruno Marchal wrote:

>And fortran programs
>are fortran generable, so I can generate a sequence of all fortran
>one-variable program F1 F2 F3 F4 F5 F6 F7 F8 .... ("all" means that
>soon or later this sequence goes trough any fortran programs: it is of
>course an infinite set)
>So, given that the sequence F1, F2, F3, F4, F5, ... is generable, the
>corresponding diagonal function G defined by
>G(n) = Fn(n) + 1
>*is* programmable in fortran. So there *is* a k such that G = Fk
>And what will happen if I apply G on its own number-code k?
>Just this: your machine will crash! The fortran interpreter will go in
>loop or in an infinite computations.
Ok. G(n) = Fn(n)+1 is computable. The hard part is finding the k such
that G(k)=Fk(k). I could try scanning all instances of Fk(k) from k=0 to
a very large number. The scan will never find a match.because there is
no k that satisfies both G(k) = Fk(k)+1 and G(k)=Fk(k).

>The key point if, I may insist, is that
>1) the superset (of programmable functions, not everywhere defined) is
>MECHANICALLY enumerable. You can write a fortran program generating
>their codes.
>2) the subset of (computable function from N to N) is enumerable, but
>is NOT MECHANICALLY enumerable. The bijection with N exists, but is not
>programmable, in *any* programming language!
>George ? Are you ok.
Hanging on.... Remember, I would like to know how all this relates to *me.*


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
For more options, visit this group at
Received on Sun Jun 11 2006 - 18:25:00 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:11 PST