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 

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 

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).


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.



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 

Reply via email to