- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Bruno Marchal <marchal.domain.name.hidden>

Date: Sat, 17 Jun 2006 13:40:36 +0200

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

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.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 Sat Jun 17 2006 - 07:41:55 PDT

Date: Sat, 17 Jun 2006 13:40:36 +0200

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

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.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 Sat Jun 17 2006 - 07:41:55 PDT

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:11 PST
*