Le 10-juil.-06, à 21:55, Tom Caylor a écrit :
>
> Bruno Marchal wrote:
>> 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).
>>
>
> I went through the 4th one now. I didn't explain it to someone else,
> but I drew diagrams and tried to construct a mathematical argument for
> some of the exercises, treating myself as a 3rd person. ;) I'm not
> finished, and I don't know when I'll get time to really do the rest
> (Exercise 2). But I can intuitively see the equivalences. And...
> according to Exercise 2 and the Church Thesis, "intuitively" is enough!
> ;)
Yes.
(About the time take it easy, I can be very slow myself).
>
>>
>> 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.
>
> OK. I noticed that you can get the Universal Machine (UM) to run for
> ever even without the "+ 1". If I think of the program for G as a big
> "case statement" with cases 1, 2, 3, to infinity, then the case for k
> will contain the code for, or better yet a call to (hence the name
> "recursive"?), Fk(k), but if we state by defining even G = Fn(n) (even
> without the "+ 1") then this is equivalent to calling G(k)... But then
> when we call G(k) we end up back in the "k case" again, calling G(k)
> again,... forever.
I'm not sure. I'm afraid your argument could be machine or language
dependent.
> This will happen even if we add the "+ 1".
> Personally I like this argument (running forever) better than the 0 = 1
> argument that somehow concludes that the UM will crash. A UM
> "crashing" to me brings up pictures of physical machines that recognize
> an unallowed operation, and then stop themselves.
Well, until now I identify crashing with "running forever". If a UM
recognizes an unallowed operation and then stops, I would say bravo to
the UM for not having crashed.
Note that the fourth diagonalization is really constructive: for any
precise specification of any UNIVERSAL machine, you can write a program
making that UM crashing (running forever).
>
>>
>> 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.
>>
>
> This makes sense. You comment on the Existence thread about why
> Aristotle choose the substance "solution" could relate to this. He did
> struggle with mysteries that come out of self-reference and
> incompleteness, and perhaps the primacy of substance was his solution.
> I've read that he discovered the similarity between deduction
> (propositions to propositions) and inference (true propositions to true
> propositions), and perhaps substance was his way of attempting to
> define truth.
Perhaps. It is not entirely obvious, because, notably, the greek use
the term "substance" in a different sense than us (in this list).
"Substance" in Aristotle (and the greeks, i.e. Plotinus) refers to
"primitive". Many late pythagoreans would say that numbers are the
primitive substance.
So yes, Aristotle, like 1Z (!), seems to have borrow to common sense
the idea that what we see is composed by elementary things (continuous
and not atomistic like the presocratic (Empedocle, Epicure).
I think it has been a fruitful speculation, and the main current
sciences could be a product of that methodological assumption. But
despite 1Z, this speculation makes the mind-body problem not only
insoluble, but quasi inexpressible (of course that is a *nice* feature
for those who want use funadmental human fears as a political tools,
like the Romans did after their JC conversion, and this explains in
part why, it is difficult to explain to scientist today that the
Aristotle versus Plato conception of reality is far from any reasonable
definitive scientific conclusion.
>
>>
>> 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
>>
>
> I don't have time to word together arguments for all of these, but I
> drew pictures. Let's see. Each Wi is a subset of N, so it is easy to
> see how each Wi could be in (a subset of) the range (output) of a
> function from N to N, so A follows.
You are too much quick here. The set R of codes of total computable
functions is also a subset of N, but this does not entail R is the
range of a total computable function. The diag2 and diag3 already
showed that R cannot be such a range. Oops, I realize I should not have
said "in the range of some Fi" but "the range of some Fi" (my fault).
>
> Each RE set is a subset of N. But it is not just any subset of N, is
> it? Likewise the set of all Wi's cannot be the set of *all* subsets of
> N, can it? This would be not enumerable.
Right.
>
>> 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
>
> These functions are the Fi.
Yes, but (even using CT) you must give an algorithm generating the set
of codes of its input/output.
Code the couple (input, output) by a number through some computable
bijection between NXN and N.
>
>> A function is intuitively total computable iff there is a (total) Fi
>> which computes it.
>
> These functions are a (non-RE) subset of the Fi.
Yes.
>
>> A function is intuitively partial computable iff it is programmable in
>> fortran (turing, ...)
>
> These functions are also the Fi.
Yes, but this should be justified. We have take CT under the form:
all total computable functions are in the sequence Fi. What makes you
so sure that we also get all the partial computable one?
>
>>
>> 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".
>
> It seems we can do this by an argument similar to the enumeration of
> the rational numbers (Cantor?). If the rows of an infinite matrix are
> number with x, and the columns with y, then you can map all of the
> (x,y) pairs with the natural numbers by starting at (1,1) and going in
> a zigzig pattern, through the whole matrix. This also brings glimpses
> of dovetailing.
No need of dovetailing here. Fu is just a function which on n will
1) decode n in their parts (x,y),
2) enumerate the (code of the) Fi up to (the code of) Fx, and
3) just compute Fx(x)
Mmmh... with CT it is quasi trivial by definition of the Fi.
But it is a key exercise to realize that "universal machine, code
program" are finite things. The *infinite* tape of the
Universal-Turing-Machine often generates confusion about that ('t was
my point here).
>
>>
>> 4) Conclude that the existence of a universal machine/number/function
>> is also a consequence of Church thesis.
>>
>
> Since the versions of Church thesis in Exercise 2 refer to the Fi, and
> Exercise 3 infers the existence of Fu from the Fi, then this follows.
>
All right,
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 11 2006 - 10:33:58 PDT