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@eskimo.com/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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~----------~----~----~----~------~----~------~--~---
