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

From: Bruno Marchal <>
Date: Mon, 12 Jun 2006 18:49:48 +0200

Le 12-juin-06, à 00:23, George Levy a écrit :

> Ok. G(n) = Fn(n)+1 is computable.

I guess you mean programmable, or at least "partial computable". OK.

> 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).

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.

>> 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.*

I think it relates to *you* :) in many ways.
The simplest, is that the UDA shows that if comp is true, eventually
the laws of physics will emerges from a structure related to the UD
through computer science, Church thesis, arithmetical self-reference,
etc. And those laws of physics calibrate *your* possibilities, what you
can hope for locally. Of course current physics and mundane knowledge
helps more here. And for the life after death question just let us say
that the equation are too much complex (is it possible to annihilate
oneself? open problem). But the three main hypostases (truth,
provability and knowability) gives a more global picture. ... don't
really one to anticipate too much...

At some point perhaps you will recognize some Lobian machine living
through you, at least sufficiently enough for being interested in the
possible fates of lobian machines in general?

It concerns us as any plausible attempts to figure out what reality are
we "really" living concerns us. I just show that if we are machine;
then there is a first person indeterminacy, and eventually the physical
emerges from the mind/number so that Plato is right and Aristotle
wrong, and materialism is put in difficulty, and as far as theology
(the truth about *you*) concern us I'm afraid we need to backtrack a
little bit.

But it is theory, science, conjecture's based, third person
communication. No certainty here. And comp justifies the roots of our
uncertainty there, either by thought experiments or by diagonalization,
or other forms of sharable introspection.


Before comp: only two certainties: death and taxes.
After comp: only once certainties: taxes.

It may concern *us*. And note that comp just rises one doubt more. Or
destroy one certainty, at least for some it seems. But this, people in
this list already know the possibility, given that QM without collapse
do the same, with respect, of course, to the belief that nature (exists
and) follows QM.
With comp we need much less belief than QM to begin to doubt on most
fundamental questions and guess the many possibilities. Some doubts are
creative and leads to ... new taxes!

Eventually the answer to your question depends exclusively by what
*you* mean by *you*.
Mathematical self-reference can perhaps provides sort of hints, even
without comp ...

I stop here before I run into an infinite computation .....


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 Mon Jun 12 2006 - 12:50:49 PDT

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