Hi Tom,
I will comment your (important imo) first and last paragraph, for
avoiding making the post too much long and technical.
Le 14-juil.-06, à 12:30, Tom Caylor a écrit :
>
> 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".
Remember that the Fi are the partial computable function. You can
generate the set of codes, written in some universal language, of all
those functions. To fix the idea I choose often the universal language
fortran, but choose any of your favorite one.
Let us then define, like you propose, the diagonal function G by G(n) =
Fn(n).
Now the Fn are fortran generable, and they are partially computable. So
it is easy to write a program computing G:
--------
Begin
read x;
generate (by using the lexicographic order) the code of the Fi up to
the code of Fx;
ouput the result of applying the xth program on x; (or
equivalently compute Fx(x), or just call
the universal function u(x,x) if you recall it).
End
---------
Now this is a finite fortran program. So it belongs to the list of
codes of the program Fi, and you can find that code, so you can find
the indice k of the function Fk = G through the explicit program above.
So, now, you can apply G on k, giving G(k) = Fk(k).
This does not give any information (unlike with G(x) = Fx(x) + 1 where
you get a proof that this G is undefined on its own code). Your G
(where G(x) = Fx(x) could be, or not, defined on its own code).
Yes: it is a little bit like you can be your own grandpa in
computerland. If you find this magic, what will you say when I will
explain Kleene Second Recursion Theorem. But indeed, what is lovely
here is that we start from a very well-founded structure (N), and the
comp constraint already forces us to admit some non-well founded
substructure. That is why I say often to Stephen that I find it
premature to start from some non well-founded set theory, because this
is like adding magic at the start, where on the contrary, here we see
we cannot avoid it from purely arithmetical reasons. But deeply enough,
here, Stephen is right I would say (I mean "comp-right").
<snip>
>
> 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".
That is normal. It is perhaps related to what I have just say today in
the "Rép : Infinities, cardinality, diagonalisation post, where I gave
a non technical argument showing that we cannot even define what
"finite" means. So, it could be hard indeed to *define* what is meant
by "computable function from N to N". It will entirely be based on the
intuition of natural (finite) number. Intuitively a function is
computable if you can explain (to some "idiot") in a finite time, or on
a finite piece of paper, how to compute that function in a finite time,
and this on any (finite) input. This is vague, of course. And this
vagueness is what has given to Alonzo Church the motivation for
*defining* the computable functions by those definable in LAMBDA(*).
Now Stephen K. Kleene was not convinced, and tried to refute that
"definition", by finding (by diagonalisation) a computable function not
in the list of the LAMBDA functions (showing also that this was more a
scientific (refutable) thesis than a definition). It is only when
Kleene realized that the list of LAMBDA functions was closed for the
diagonalization procedures that he realized that Church's "definition"
could be *true*, and he became an ardent defenders of that thesis. He
is the one who will make the label "Church's Thesis" (the most commonly
used by logicians).
> In other words, just
> what is a function in the intuitive/mechanical sense?
So I have just said it above, and with Church thesis you can "define" a
computable function by "a function programmable in your favorite
universal language".
For all known universal procedure/system/language/machine it has been
*proved* that their are equivalent with respect to the set of
computable functions (from N to N). No need of CT to believe that. But
CT makes it possible to define get a powerful notion of universality
suitable for the comp reasoning.
> 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?
OK. Let me try a short answer which we can expand later if necessary.
Let N be the set of natural numbers {0, 1, 2, 3, 4, ...}. Let + and *
have their usual meanings of addition and multiplication. Somehow I
take platonia (here) as the standard mathematical structure <N, +, *,
0, 1>. But I allow the use of logical languages (propositional
calculus, first order predicate and function symbols together with the
quantifier "for all" (A) and "exists" (E)) to write those sentences
which I will consider as true or false independently of me.
For example ExEy(x*x = 2*(y*y)) "asserts" that sqrt(2) is rational, and
I will take that such a formula is (provably) false in arithmetical
Platonia. The point is that such a falsity is a very primitive truth
which does neither depend on me, nor on you,nor or the earth, humanity
or whatever.
All right?
The next point is that is that such a language can be shown to be
enough rich to talk on the Wi and the Fi. A proposition like "Ax(Fi(x)
is defined" ( equivalent with AxEy(Fi(x) = y) or with Ax(x belongs-to
Wi) can be written using only addition and multiplication and the
symbol 0 and 1, and the logical language of course). All the
proposition of the form "the universal dovetailer will generate such or
such third person definable states" can be translated into a
proposition of pure number theory.
Actually the UD will correspond to a theory known as Robinson
Arithmetic, which is very weak, and the rest will emerge from richer
(lobian) theory/machine M (like Peano Arithmetic, or ZF set theory)
which mainly got powerful induction axioms above Robinson arithmetic
(which actually has almost just the definition of addition and
multiplication above classical logic) emerging globally (from a first
person point of view) once you take all the theorems of Robinson
Arithmetic has true independently of you.
Sorry for that long sentence which I wrote in hurry 'cause I got
something else to do. Do this helps?
Bruno
(*) LAMBDA, or Lambda Calculus. It is a formal language Church invented
for that very purpose of defining the computable functions. It is a
cousin of the SK-COMBINATORS, for those who read the combinator posts.
See around:
http://www.mail-archive.com/everything-list.domain.name.hidden/msg05961.html
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 - 11:06:35 PDT