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.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 Tue Jul 04 2006 - 11:02:10 PDT