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

Date: Thu, 15 Jun 2006 08:57:52 -0700

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?

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.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 Thu Jun 15 2006 - 11:58:54 PDT

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