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.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 Tue Jul 18 2006 - 10:07:44 PDT