Bruno Marchal wrote: > Le 15-juin-06, à 18:40, Tom Caylor a écrit : > > > > > > > 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. > >> > > > > OK. You've shown by contradiction that g is not computable. I was > > just trying to go back to the definition of computable to see which > > part of the definition is violated. I think I overlooked the fact that > > you alluded to the answer to this question when you said "...you just > > will never been able to give me a finite set of instructions for doing > > that". I.e. g violates the finite description part of computability. > > I think Brent Meeker was trying to get at this idea, too, in answer to > > your diagonalization explanation in 2001. > > > > http://www.mail-archive.com/everything-list@eskimo.com/msg01002.html > > > > But both then and now, you said that this is not the right reason, and > > then you went on to repeat the proof by contradiction, which we already > > understand. > > You have perhaps miss the difference between two resembling proof. I > think A summary will be necessary. It should be easy because the proofs > are short. > > > > > If finiteness does not correspond with the reason for > > non-computability, this implies that there are g's formed by this > > diagonalization method, which have a finite description, but that take > > an infinite time to execute (thus fulfilling the definition of > > non-computable). > > Are you talking about the diagonal function g build on from the set of > all fi, and which is not computable, or about the G get from the Fi, > which is partial computable, or about some given effective enumeration > of total function (where we have used also the letter fi)? > Or just wait for a summary where the proposition will be numerated for > the sake of future use of them. Well here apparently you were talking > about the Fi. > > > > > 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. > > But here you talk distinctly about the fi. > if your fi denotes all the total computable functions, then, what we > have proved, is that not only your "program" for g would be infinite, > but, above all, could not be generated by any computational process: > you cannot generate the sequence of all, and only all, total computable > function f1, f2, f3, ... > CT is the statement that the fi are among the Fi, so that you can > generate computably a superset of the fi. > > Bruno > > http://iridia.ulb.ac.be/~marchal/

## Advertising

Yes. I am talking about the fi in all of the above. I think we are actually in agreement about this. I understand the argument, given the acceptance of the Church Thesis. 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 -~----------~----~----~----~------~----~------~--~---