Bruno Marchal wrote:
> 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.
>
Change g to
g(n) = (Rn(n) + 1) mod 2
One way to think about this is to concatenate the output of each Ri and
put a decimal point (actually binary point) in front of it to make a
number between 0 and 1, expressed in binary. Each Ri is arbitrary,
say,
output of R1 = 0.101...
output of R2 = 0.010...
output of R3 = 0.100...
...
but each R1 is infinitely long, since the domain of each Ri is the
natural numbers N (i.e. each Ri is total). If the domain wasn't all
of N, then the diagonalization wouldn't work. Right?
So
g(1) = (R1(1) + 1) mod 2 = 0
g(2) = (R2(2) + 1) mod 2 = 0
g(3) = (R3(3) + 1) mod 2 = 1
...
and so concatenating these together into a binary number from 0 to 1
gives
output of g = 0.001...
which is different from any of the Ri's. So here we see Cantor's
original diagonal proof of the uncountability of the real numbers
played out in binary.
I have to repeat though that I have misgivings about using infinite
diagonalization to try to conclude things about real-live reality
(physics, mind/body problem). We indeed are using the law of the
excluded middle with an infinite sequence. We are saying that since g
cannot be any particular one of the Ri's, then g is not in the whole
infinite list. I know that this particular diagonalization is not one
that is used in your argument, but I think that the same fault is in
the other diagonalizations. Not that this can't be used to argue about
"imaginary" mathematical play things like the set of real numbers, or
the other creatures that come out of the following diagonalizations,
but how can we say that these things have anything to do with reality?
I know you'll probably say that it's testable, but I have yet to see
it. Diagonalization is not testing. Diagonalization just produces
negative results. Something doesn't exist. How can we test that?
>
> >
> > 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).
>
>
In this post, you don't say that the functions are "effectively
computable", just "computable". Is effectiveness implied? I thought
that computable meant just codable as an algorithm, you can program it,
and effective means it also takes a finite amount of time to produce
its output. I think I've read that computable can mean effectively
computable. Is this the case here?
So does mechanically generable basically mean that you can write a
finite program that will be able to generate the code for all of the
functions in the sequence? In other words, simply having the infinite
list of programs "hardcoded" into the program wouldn't qualify, because
then the program (that generates the code for the functions) would be
infinitely long. So mechanically generable (same as RE?) means that
the set of functions is such that it can be ordered so that it follows
some pattern that can be compressed into a finite set of rules. Right?
(By the way, Wikipedia is hard to follow here. Without re-looking it
up, I think that the definitions of "computable" and "recursively
enumerable" seem mutually circular, so I've found it hard to pin them
down.)
So in other words we've proved that the whole set of total computable
functions is *not* such that it can be ordered so that it follows a
pattern that can be compressed into a finite set of rules (algorithm).
Again, I'll be interested to find out how this relates to reality in a
testable way.
>
>
> >
> > 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.
It seems like it's actually the other way around. First we assumed
that all of the fk's are total (and so fk(k) is a number). Since all
fk's are total, then g is total. But the conclusion is the same.
> 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.
>
>
So for a bijection to be not computable would mean that you can't write
a (finite) algorithm that could take each natural number 1,2,3,... and
output the code for the corresponding f1,f2,f3,... This sounds like
saying the set of fi's are not mechanically generable (recursively
enumberable). Right?
Could we alternatively conclude that g is not total, so that some of
the fk's are not total? But then I think this would put us down in the
4th diagonalization below?
>
>
> >
> > 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/
My finite digital (equivalently, if comp it true?) brain has worn out
for now. It seems that on the 4th diagonalization, Church Thesis is
trying to say something about reality, finally. I guess it's your
bridge between math and reality. I think I need to get back to reality
and get some sleep.
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 Fri Jul 07 2006 - 01:24:28 PDT