Computability and Creative Sets
Dick
Theory" by Cooper. I am stuck on the concept of Creative Set.
A creative set, A is defined as:-
A is creative if
1. A is c.e.
2. There exists f(e) s.t.
W(e) belongs ^A => f(e) belongs ^A-W(e)
K = {e st e belongs W(e) is given as an example with creative function
f(x) = x
It is stated that naturally occurring non computable sets ar usually
creative.
Is K(k) = { W(e) st (k belongs to W(e)} creative?
The creative function should be f(e) = k. However for some values of
k , { k belongs W(K) and so f(k) belongs K(k) and the set is not
creative.
What have I misunderstood?
Can you give an example of a creative set with creative function
different from f(x) = x?
Dick Batchelor
David C. Ullrich
wrote:
>I am trying to understand computability by reading "Computability
>Theory" by Cooper. I am stuck on the concept of Creative Set.
>A creative set, A is defined as:-
>A is creative if
>1. A is c.e.
What does "c. e." mean?
>2. There exists f(e) s.t.
> W(e) belongs ^A => f(e) belongs ^A-W(e)
What is W? Is ^A supposed to be the complement of A?
>K = {e st e belongs W(e) is given as an example with creative function
>f(x) = x
>It is stated that naturally occurring non computable sets ar usually
>creative.
>
>Is K(k) = { W(e) st (k belongs to W(e)} creative?
>The creative function should be f(e) = k. However for some values of
>k , { k belongs W(K) and so f(k) belongs K(k) and the set is not
>creative.
>
>What have I misunderstood?
>Can you give an example of a creative set with creative function
>different from f(x) = x?
>
>Dick Batchelor
David C. Ullrich
"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
Dick
> On Fri, 4 Jul 2008 10:21:13 -0700 (PDT), Dick <DBatche...@aol.com>
> wrote:
>
> >I am trying to understand computability by reading "Computability
> >Theory" by Cooper. I am stuck on the concept of Creative Set.
> >A creative set, A is defined as:-
> >A is creative if
> >1. A is c.e.
>
> What does "c. e." mean?
which can (eventually) come up with any member that is in A. The set
of "Turing machines that stop" is c.e. If machine e stops after n
steps you can demonstrate it by running the machine for n steps.The
set "Turing machines that do not stop" is not c.e. Machine e may never
stop but there may be no way to be sure of this.
If A and ^A are both c.c then A is a computable set. You can make a
list with all its elements in order.
>
> >2. There exists f(e) s.t.
> > �W(e) belongs ^A � => � f(e) belongs ^A-W(e)
>
> What is W? Is ^A supposed to be the complement of A?
W(e) is the "halting set" of e. Thus W(k) = {1,2,3} means "Turing
machine k halts if it is started with 1, 2, or 3 on its tape and NOT
OTHERWISE.
^A is the complement of A (I think; I may have misunderstood the
notation)
The critical statement is f(e) belong to ^A - W(e) which I take to
mean:-
f(e) does not belong to A
and f(e) does not belong to W(e)