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

```
Le 15-juin-06, à 17:57, Tom Caylor a écrit :```
```
>
> 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
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