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.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 Thu Jun 15 2006 - 08:25:06 PDT