Bruno Marchal wrote:
> 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).
>
You've written a sort of intuitive code for G above, where you say
"generate". But if G = Fk, then when we go to explicitly write the
code for G, when we get to "generate the code for Fk" what to we write?
Fk *is* G. So we start generating G from the beginning until we again
get to the part "generate the code for Fk" and then we do this forever.
It's sort of like at dinner when I ask my son or daughter what they did
today, and they tell me everything they did starting with "I woke up
and made my bed...", and jokingly they finally say, "...and then sat
down for dinner and told you, 'I woke up and made my bed...' ..." But
of course they finally stop and laugh, instead of going forever.
This is where I'm stumped. You say that we escape the diagonalization
and the program runs forever (because 0 is not equal to 1). I'm trying
to get a firm handle on what is actually going on here. Is there some
intuitive definition that is causing an ambiguity, just like the
definition of a function itself, as in my previous post?
Tom
>
> 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 - 20:57:13 PDT