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!
;)
>
> 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. 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.
>
> 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.
>
> 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.
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.
> 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.
> 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.
> A function is intuitively partial computable iff it is programmable in
> fortran (turing, ...)
These functions are also the Fi.
>
> 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.
>
> 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.
Tom
>
> 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 Mon Jul 10 2006 - 15:56:41 PDT