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. 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?
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 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.)
On Jul 5, 10:19 am, David C. Ullrich <dullr...@sprynet.com> wrote:
> 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?
"c.e" means "computability enumerable". There is a Turing machine 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.
> 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)
> >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.)
