Hi Tom, Hi George, George, and others, you can skip the "partial answer to Tom", and go directly to "K, the master set" below. Tom seems to propose an alternate proof, which does not convince me, although I cannot right now provide a full counter-example. Note that the section "K, the Master Set" could already put some light on that matter.
1) Partial answer to Tom: Le 17-juil.-06, 22:42, Tom Caylor a crit : >> Now *your* G is just defined by G(n) = GEN2(n). > > But doesn't G output the range of one of the set of *all* partial > recursive functions, whereas GEN2 outputs the code of a *fortran* > program? So shouldn't it be the following, where execute() actually > executes the fortran program generated by GEN2(n)? > > G(n) = execute(GEN2(n)) I should have written G(n) = Gen2(n) (n) (= execute Pn on n) >> Tell me if you are convince that "your" and "my" G are programmable. >> > > They are both programmable, but I think they are both non-*executable* > on "k" (if G=Fk), for the same reason, self-reference. Let me give you a counterexample with a sequence of total functions. Let Hi be a RE sequence of (codes) of total functions. (so the seq. Hi is from the seq. Fi) Let GBruno be defined by GBruno(n) = Hn(n) +1 Let GTom be defined by GTom(n) = Hn(n) Could GBruno belongs to the sequence Hi? If GBruno belongs to the Hi, it means there is a number kbr such that GBruno = Hkbr, thus GBruno(kbr) = Hkbr(kbr) = Hkbr(kbr)+1. So I can be sure that GBruno does not belong to the sequence Hi. OK? (the usual simple subtraction would lead to 0 = 1) Does GTom belongs to Hi? If GTom belongs to the Hi, it means there is a number kto such Gtom = Hkto, thus Gtom(kto) = Hkto(kto), which is the case by definition of "your" Gtom. No contradiction occurs, so in principle the total function Gtom could belongs to the list, and indeed is equal to the sequence Hi, despite self-reference. The same could be true for the partial recursive Fi. I don't see any reason why, if G(n) is defined by Fn(n), G should be necessarily undefined on its own index. Your argument could rely on the way you implement G. Actually I could perhaps build an ad hoc counterexample working for some particular enumeration of the Fi, but I need some time to do it, if it is possible.... So I propose we come back on this after a while. Probably you will figure out what is happening by yourself. Actually your intuition is right: something happens with self-application (see below). If I try to explain all of it here, this could be a little confusing. What you need to be sure of is the fact that when G(n) is defined by Fn(n)+1, then G(k) will be necessarily undefined on all k such that G = Fk. (Independently of the fact that you could be right that G'(k') is also undefined when G' (n) is defined by Fn(n), and k' is a code or index of G'; but your argument is not a proof because it depends on the precise way G is implemented). I must think ... 2) K, the Master set Emil Post, the founder of Recursion Theory, introduced the following set (of numbers) which will appears to be fundamental. It will correspond, in term of set, to the universal machine. K will be an universal RE set, capable of "generating" all RE sets. I recall the code of the RE sets are generable, and the RE sets are the domain Wi of the Fi. Definition: K is the set of numbers x such that Fx(x) is defined. So K is the set of natural number x such that the xth programs in the enumeration of the codes of all programs does stop when apply on itself. I prefer to talk about self-application instead of self-reference (to follow standard terminology). I give exercises (if only because my office is an oven and my brain is boiling hot): 1) Is K an RE set? Answer: yes (why?) 2) Is N \ K an RE set? Answer: no (why? Hint: diagonalization) 3) From this conclude that the halting problem is insoluble. 4) try to justify that someone having an algorithm for generating K will be able to generate any Wi. Put in another way, from a mechanical solution to the problem "does Fx(x) stop" we can construct an algorithm solving the apparent more general problem "does Fx(y)" stop. 5) From "2)" show that N \ K is productive (like the set of codes of the computable growing functions). That is N \ K is not only not-RE, but is constructively not-RE. You need to find an algorithm A such that for any Wi included in N \ K, A(i) will give an element in N \ K which is not in Wi. If you look at that Wi as an attempt to enumerate all N \ K, you can see the algorithm A as providing a counter-example. Conclude that N \ K can be better and better approximated by iterations in the constructive transfinite (like we done with the fairy). MAIN DEFINITION (Emil Post): A set E (of numbers) is called CREATIVE if 1) E is RE 2) N \ E is productive So the exercise can be sum up into: show that K is a creative set. There are deep relations between creative sets, universal machines, and lobian "theories/machines" which we will exploit soon or later. Take all your time, and (to all) don't hesitate to ask any question or to make any remarks. 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@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 -~----------~----~----~----~------~----~------~--~---
