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

```
Bruno Marchal wrote:
> ...
> Let us be specific (also for the others).
>
> Let us continue to write f1 f2 f3 f4 f5 f6 f7 ... for the sequence of
> total computable functions.
> Let us continue to write F1 F2 F3 F4 F5 F6 F7 ... for the sequence of
> partial computable functions (this includes the fi but in a hidden
> way).
> Let us write, as usual, g for the diagonalization of the fi, and G for
> the diagonalization of the Fi.
>
> So: g(n) = fn(n)+1; and G(n) = Fn(n)+1
>
> Now g cannot be computable, it would be total and it would belongs to
> the sequence fi, and thus there would be a number code k such that g =
> fk, and then fk(k) = fk(k)+1, and then 0 = 1 by substracting the well
> defined number fk(k). Obviously each fn(n) is computable, and adding
> one is computable, so only the bijection between the fi and N can be
> the source of uncomputability.  Conclusion the bijection between i and
> fi, although well defined mathematically, is not computable.
>
> Now, if we accept Church thesis, then by definition all the total
> function are in the sequence F1 F2 F3 F4 ... But the sequence Fi is
> mechanically generable (just do it on your favorite programming
> language), and thus G is programmable, (G(n) = Fn(n)+1; note the
> capital!) but then G is programmable and thus belongs to the Fi, and
> thus you can find k, the number code of G, and then G(k) = Fk(k) =
> Fk(k)+1, but this can be ok only if Fk(k) is undefined.
>```
```
Let me try to see what is wrong with the following attempt to enumerate
the total computable functions:

inputs
1 2 3 4 5 6 7 8 9 ...
f1:    2 1 3 4 5 6 7 8 9 ...   (switch 1 and 2)
f2:    3 2 1 4 5 6 7 8 9 ...   (switch 1 and 3)
f3:    4 2 3 1 5 6 7 8 9 ...   (switch 1 and 4)
f4:    5 2 3 4 1 6 7 8 9 ...   (switch 1 and 5)
f5:    6 2 3 4 5 1 7 8 9 ...   (switch 1 and 6)
...
fn:    fn(n+1) 2 3 4 5 6 7 8 9 ... fn(n-2) fn(n-1) fn(n) 1 fn(n+2) ...
(switch 1 and fn(n+1))
...

So let's do the diagonalization move.  Let g(n) = fn(n)+1.
But from inspection of the table, we see that fn(i) = i, for all i not
equal to 1 or fn(n+1).  So g(n) = n+1.  Putting this in a table:

inputs
1 2 3 4 5 6 7 8 9 ...
g:     2 3 4 5 6 7 8 9 10 ...

But from inspection, we see that g does not fit anywhere in the table
of f1,f2,f3,... because it does not follow the rule of "switch 1 and
something else" [and also it doesn't follow fn(i)=i for all i not equal
to 1 or fn(n+1) ].

So therefore g is not part of the list.  I.e. g is not a total
computable function.

I have more to say/ask, but I have to meet someone to go jogging right
now.  I don't know when I'll have more time.

Tom

--~--~---------~--~----~------------~-------~--~----~
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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at