Le 15-juin-06, à 17:57, Tom Caylor a écrit :

## Advertising

> > An even simpler case is the following: > > inputs > 1 2 3 4 5 6 7 8 9 > f1: 1 2 3 4 5 6 7 8 9 ... (identity) > f2: 2 1 3 4 5 6 7 8 9 ... (switch 1 and 2) > f3: 3 2 1 4 5 6 7 8 9 ... (switch 1 and 3) > f4: 4 2 3 1 5 6 7 8 9 ... (switch 1 and 4) > f5: 5 2 3 4 1 6 7 8 9 ... (switch 1 and 5) > ... > fn: fn(n) 2 3 4 5 6 7 8 9 ... fn(n-2) fn(n-1) 1 fn(n+1) fn(n+2) ... > (switch 1 and fn(n)) > ... > So let's do the diagonalization move. Let g(n) = fn(n)+1. > But from inspection of the table, we see that fn(n) = 1. So g(n) = 1+1 > = 2. Putting this in a table: > inputs > 1 2 3 4 5 6 7 8 9 ... > g: 2 2 2 2 2 2 2 2 2 ... > > 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. > > However, as is plainer to see with this example, how can g(n)=2 (for > all n) not be computable and total? It is not one-to-one, but does > that make it not computable or not total? Of course g(n)=2 is computable! A program could be like BEGIN READ X OUTPUT 2 END You have just proved that g(n) = 2 is not in your list. But why did you ever think that your list should enumerate all computable functions? You generate just the identity functions up to a permutation in their range: you will miss all the constant functions (not just your g(n) = 2), you will miss the factorials, and any growing functions we have defined, etc. Still, you illustrate the point: for any presentation of an effective list of computable functions from N to N, we can build a computable function from N to N which is not in the list. An effective (computable) list of functions fi is given by a computable bijection i ---> Pi with Pi a program computing fi. It is obvious that the set of the computable function fi is enumerable. The diagonalization has proved so far that , although enumerable, that set is not computably enumerable. We have to understand this to grasp that Church Thesis (CT) is a very strong statement. CT says that all the computable fi belongs to the collection of the Fi, the partial computable functions or programmable functions, which *is* effectively enumerable. Will say more. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---