Hi Tom, hi George,
I recall the 4 diag problems, and the three solutions already provided.
Below, I give the solution of the fourth, and new exercises. Read this
with paper and pencil, or don't read it. If you understand, try to
explain to someone else (the best test).
Le 04-juil.-06, à 17:01, Bruno Marchal a écrit :
>
> 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.
With Church thesis, Fortran is a Universal Language, and a fortran
"interpreter" is a Universal Machine, where Universal means it computes
(at least) all computable functions. Fortran programs are recursively
(computably, mechanically, effectively) enumerable, so
G = Fn(n) + 1
is programmable, notably in fortran. So there is fortran code for G and
it exists in the enumeration
of all fortran programs. So there is a number k such that G = Fk. So
G(k) = Fk(k) = Fk(k) + 1. So Fk(k) cannot be defined and it makes the
Universal Machine run for ever (crash). So, the notorious "other
beasts" are the *partial* recursive function. They are functions from
*subset* of N, called domain, in N.
Note that a total function is a particular case of partial function
where the domain subset is N itself. A partial function which is not
total will be called a proper partial function.
Two direct consequences:
1) insolubility: there is no fortran program capable of distinguishing
a code of a total function from a code of a proper partial function.
Proof: indeed if such a program exists, we could, from a recursive
enumeration of (the code) of the Fi, filter out the code of the proper
partial function, and extract a recursive enumeration of the total
functions, contradicting each of the two preceding diagonalizations.
2) incompleteness: first a definition: an axiomatizable theory (about
numbers, programs) is a generator of true propositions about numbers
and programs. A theory is said to be complete if it generate all true
propositions about numbers and programs. We have a theorem: there is no
complete theory. Indeed, if we did have a complete theory about
programs we could prove for each "i" if "Fi" is total or proper
partial, and we would be able to use this to build a fortran program
capable of distinguishing a code of a total function from a code of a
proper partial function; and thus contradicting "1)" just above.
The key point now, is that the recursively enumerable sequence "Fi"
give us a sort of coordinate system for reasoning about programs. To
fix some Universal machine or language is the equivalent of fixing some
reference frame in geometry. And then we can reason in a way which does
not depend on which Universal Machine has been chosen.
Now Fi denotes just the partial function programmed by the ith fortran
program. So Fi has a domain. It is written Wi. That is: Wi = domain of
Fi.
Exercises:
1) show that
A) all the Wi are recursively enumerable (mechanically generable = in
the range of a total computable function, or empty).
B) all the recursively enumerable sets are among the Wi
2) Conclude that the following version of Church thesis are equivalent:
A set is intuitively (effectively, mechanically) generable iff it is
recursively enumerable (RE)
A function is intuitively computable iff and only if the set of codes
of its (input, ouput) is RE
A function is intuitively total computable iff there is a (total) Fi
which computes it.
A function is intuitively partial computable iff it is programmable in
fortran (turing, ...)
3) Justify the existence of a universal Fu. Fu(n) use a computable
bijection of N X N with N, to decode n into two parts x and y, and
gives as result Fx(y). The program "u" applies somehow the program "x"
on the datum "y".
4) Conclude that the existence of a universal machine/number/function
is also a consequence of Church thesis.
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 Jul 08 2006 - 10:00:33 PDT