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 http://groups.google.com/group/everything-list -~----------~----~----~----~------~----~------~--~---