Hi Tom, Hi George,

I recall the (four) diagonalization problems. I show each time the 
diagonal functions, which I will always call g, except for the Fi where 
I call it G. In each case the existence of that g proves something 
different. I have change r1, r2, r3 ... into R1 R2 R3 ... because rn 
looks to much like m in many fonts.

[Apart for Norman and the "non-mathematician": please keep this posts, 
I will send preliminary posts for you to read before]


Le 22-juin-06, à 17:03, I wrote:

> The question is: what does diagonalization prove on those
> following list of functions:
>
> 0) R1 R2 R3 R4 R5 R6 R7 R8 ...
> This is an arbitrary list of functions from N to N  (not necessarily
> computable one);


g(n) = Rn(n) + 1

All Rn are well defined function from N to N, so all Rn(n) + 1 are well 
defined number, and so g is a function from N to N. But g cannot be in 
the given (arbitrary) list, and this show that the set of functions 
from N to N is not enumerable.

Proof by contradiction.
Indeed, if this was the case, there would be a (precise) number k such 
that g = Rk. I will say that k is the index of Rk = g. Let us apply g 
on its own index k. In that case g(k) = Rk(k) + 1 = Rk(k). Again Rk(k) 
is a precise number, so, by subtraction in the last equality: 1 = 0. So 
g does not belong to the list R1 R2 R3 R4 R5 R6 R7 ... Now that list 
was arbitrary, so this proved that ALL sequences of functions from N to 
N will miss its corresponding "g", that is will miss a function from N 
to N.
This is the celebrate proof by Cantor of the non enumerability of the 
functions from N to N.

Exercise: show that the functions from N to {0,1} are not enumerable, 
by a similar proof. Hint: find the appropriate slight change in the 
definition of g.


>
> 1) h0 h1 h2 h3 h4 h5 h6 ...
> This is a list of total computable functions from N to N that we can
> generate mechanically (I mean we can generate their codes). It means
> that we can generate the codes of each hi, written in some language,
> and that, for some reason, we are sure that each hi is total
> computable. Examples: Caylor last funny enumeration; all the
> (transfinite collection of) sequences of growing functions we have
> defined in this thread (since "Smullyan Smullyan ...");


g(n) = hn(n) + 1

All hn are well defined function from N to N, and now we are told they 
are also computable. And then we are also told that we can generate 
mechanically their codes, for example: C1 C2 C3 C4 ... where each Ci 
computes the functions hi. (Meaning the program/codes Ci with input n 
will gives the result hi(n). In particular all hn(m) can be computed.
Well, this means in particular that I can compute hn(n). Just apply Cn 
on n. So obviously, for any n, I can compute hn(n)+1. Just generate the 
Ci up to Cn, apply it to n and add one. But this is g(n), and so g is a 
computable function from N to N.
But now g cannot belong to the list h1 h2 h3 ....  The hi does not 
exhaust the computable functions.

Proof by contradiction.
Indeed if g belongs to that list, then it exists a precise number k 
such that g = hk. G would have a program Ck. Let us apply g on its 
index k. g(k) = hk(k) = hk(k)+1. Now hk(k) is the result of appying the 
program Ck, which computes a total, well defined function, so it is a 
number which I can subtract  on each side of the last inequality giving 
0 = 1.
This show that all mechanically generable set of total computable 
functions will miss a total computable functions.
Obviously, the set of total computable function *is* enumerable. We 
have just proved that this set cannot be mechanically enumerable. 
Logicians says such sets are not recursively enumerable; they write 
that they are not RE.
Actually we have show more: such set are constructively not recursively 
enumerable. This is because the diagonalization is effective. Given any 
attempt to enumerate a set of total computable functions can lead 
mechanically to the counterexample. Such sets are called productive.
We have met already three examples of such sets: the set of (code of) 
total functions, the set of formal arithmetical truth, the set of all 
computable growing functions, etc.
Any RE set approximating such a set can be extended into the 
constructive transfinite (reread perhaps the posts on the growing 
functions).




>
> 2) f0 f1 f2 f3 f4 f5 f6 f7 ...
> This is an arbitrary list of *all* total computable functions;


Given that the set of the (code) of the total function is enumerable 
(although not *recursively* enumarable), we can use the bijection 
between that set and the set of natural numbers to give to such 
function the indices 0, 1, 2, 3, ... getting f0, f1, f2, f3, f4, ....
The preceding reasoning has already shown that such a bijection cannot 
be computable, indeed it would make the set of total functions 
recursively enumerable. But you can got the contradiction by direct 
construction of g, and it is instructive to do so:

g(n) = fn(n) + 1

Does that g belongs to the list of the fi ? Put in another way: is g a 
total computable function?
Suppose it is, then it exists a k such that g = fk, and applying g on 
its own indice will give gk(k) = fk(k) = fk(k) + 1. And g has been 
assumed total so that fk(k) is a number, and so I can subtract it 
getting 0 = 1 as usual.
This shows that g is not computable, and given that all fi are, it 
means that it is the bijection i -> fi is itself not computable. We 
knew that.




>
> 3) F0 F1 F2 F3 F4 F5 F6 F7 F8 ...
> This is the list of all programmable things in some "universal
> language" like fortran.  CT asserts fortran is universal so that the
> total computable function fi will be dispersed *among* those Fi things,
> so that a universal machine can really compute all the fi, among other
> things.
>
>
> Now the same diagonalization argument proves 4 different propositions
> according to which list we are talking about. Which one?
>
> Before answering, I let people muse a little about what are those 4
> different consequences,  given that the only way to really grasp those
> propositions consists in rediscovering them by oneself,  ... or at
> least in searching enough so as to be curious listening to the
> solutions.


I let you think on this one. The most important one. We will get a 
precise definition of universal function and of relative universal 
machine/code/index/number from the list of the Fi.

Must go now,

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
-~----------~----~----~----~------~----~------~--~---

Reply via email to