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

From: Bruno Marchal <>
Date: Sat, 17 Jun 2006 14:11:12 +0200

Le 15-juin-06, à 21:03, Jesse Mazer a écrit :

> Tom Caylor wrote:
>> So apparently we are still missing something. You need to tell us
>> *why* this is not the right reason. The set of instructions for g is
>> precisely a big "case" statement (if you will) on n, like this:
>> switch n:
>> begin
>> case 1:
>> set of instructions for f1:
>> case 2:
>> set of instructions for f2:
>> case 3:
>> set of instructions for f3:
>> ...
>> end (after an infinite number of cases)
>> This is an infinitely long program. You need the whole program to
>> define g, not just the portion you need for a given input. Is there a
>> finite version of g? I don't see how.
>> Tom
> I haven't been following the all details of this discussion, so
> apologies if
> I get things confused...but aren't those f1, f2, f3 etc. supposed to
> correspond *only* to turing machine programs which actually halt and
> give
> you a finite number as an output? If so, then although we can write
> down the
> list of all possible turing machine programs, there is no way to
> figure out
> which programs on this list correspond to one of your functions and
> which
> don't without solving the halting problem.

Note that even if you could solve the halting problem (perhaps with
some oracle) you would still not been able to solve the problem of
distinguishing the code/program of a total comp function from the code
of a strictly partial comp function.

I have proved that insolubility of code-of-total/code-of-partial
distinction again and again without using the insolubility of the
halting problem.

Of course I proceed in that way to make things as simple as possible.
Showing the insolubility of an harder problem (tot/partial) is of
course simpler than showing the insolubility of a simpler problem (the
halting problem).

Another reason is that the set R of the total fi (the constructive
reals) and the set P of the Fi will provide neat description of the
first person plenitude and the third person plenitude, and relate all
this to "Smullyan's heart of the matter".


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 Sat Jun 17 2006 - 08:12:29 PDT

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