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

From: George Levy <glevy.domain.name.hidden>
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.*

George

--~--~---------~--~----~------------~-------~--~----~
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 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