Bruno Marchal wrote:
> Le 10-juil.-06, à 21:55, Tom Caylor a écrit :
>
> >>
> >> 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.
>
But with Church's Thesis how could it be machine or language dependent?
Another way of arguing without the "+ 1" is this: Define G(n) = Fn(n)
for all n. If G is in the list of Fi's, then G=Fk for some fixed k.
So Fk(n) = Fn(n) for all n. Now if all you're thinking of is a matrix
of numbers Fx(y) (a lookup table if you will) with rows numbered by x,
and columns numbered by y, then this doesn't seem problematic (unless
you introduce the "+ 1"). But such a lookup table is infinite and
therefore is not allowed as the code of a computable function. You
need code for the functions Fi. Specifically, you need code for the
function Fk (=G). What does this code look like, even in a universal
sense? Well Fk(n) = G(n) = Fn(n) for all n, so Fk would have to have
some code to compute Fk(1)=F1(1), Fk(2)=F2(2), Fk(3)=F3(3), ...Fk(k)=?,
...
How does Fk *ever* know what to compute for Fk(k)? This is actually
rather funny to me. It's like me being my own grandpa. It seems that
there already is a case of G(n) not being defined for n=k, even without
the "+ 1".
> >
>
> >
> >>
> >> 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).
>
OK. For 1A I'm not sure whether you mean "{the whole set of Wi's} is
RE", or "each and every {Wi, for a given i} is RE". I think you mean
the first one. I think that we have to use the fact that the set of
Fi's is RE (=the range of a total computable function). However, I
can't see how that would make the set of domains Wi for all i, RE. I
was thinking along the lines of a composition of two total computable
functions would be a total computable function, but it seems that the
Fi's and Wi's apples and oranges, since the Fi's are the (code of?)
functions, and the Wi's are the domains of the Fi's.
>
> >
> > 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.
>
This was trying to address 1B. I have a feeling that "all the RE sets
being among the Wi" has something to do with the Church Thesis
statement (below) about all partial computable functions being among
the Fi.
>
> >
> >> 2) Conclude that the following version of Church thesis are
> >> equivalent:
> >>
> >> A set is intuitively (effectively, mechanically) generable iff it is
> >> recursively enumerable (RE)
This one seems to be true by definition, at least you told us RE =
mechanically generable.
> >> 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.
>
I think this is my zigzag argument below. This provice a computable
bijection between NxN and N.
(1,1) (1,2) (1,3) (1,4) ...
(2,1) (2,2) (2,3) ...
(3,1) (3,2) (3,3) ...
(4,1) ...
...
<-->
(1,1), (1,2), (2,1), (3,1), (2,2), (1,3), (4,1), (3,2), (2,3), (1,4),
...
You could figure out a computable formula. I don't want to. It
probably involves n^2, and int(sqrt(n)) going the other way.
The set of Fi's are the set of computable functions and they are RE.
1A is the statement that the inputs are RE. The outputs are RE, since
the i's can be considered the input of a total computable function
mapping the i's to the Fi's for all i in 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?
>
>
The Fi's *are* the computable functions (by definition), which includes
the strictly partial *computable* functions.
I know there are still gaps in showing that all of these are
equivalent, but I've run out of the patience needed to get all of the
ducks in a row, and with the process of misunderstanding some of your
wording, I think it would take too many iterations for you to walk me
through it all.
>
>
> >
> >>
> >> 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).
>
I get your point, that if you assume Church Thesis, all of these neat
things are possible "intuitively/mechanically". I guess my first
paragraph of this post reveals that I am uncomfortable with the
vagueness of this "intuitively/mechanically". In other words, just
what is a function in the intuitive/mechanical sense? How is a
function *implemented* in Platonia? This sounds like the question
Stephen was asking on the Existence thread. We can say OK it's a
mapping from one set of numbers to another. Say f(3)=17. Exactly how
is that done?
Tom
>
> >
> >>
> >> 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 Fri Jul 14 2006 - 06:31:32 PDT