Turing Machine Problem
in [Theory]
|
Prev: Workaround for halting problem
Next: Constructing Tethered Strands Causative but non-deterministic in any traditonal sense of the word when 1. For GET and HAVE: We compute
From: BJS on 23 Jun 2010 22:25 Taken from Michael Sipser's Theory of Computation: "4.28 Let A be a Turing-recognizable language consisting of descriptions of Turing machines , {<M(1)*>, <M(2)>, ...}, where every M(i) is a decider. Prove that some decidable language D is not decided by any decider M(i) whose description appears in A. (Hint: You may find it helpful to consider an enumerator for A.)" So my attempt at this is to let some enumerator E match the Turing- recognizable language A, but the description of A seems rather vague: "Let A be a Turing-recognizable language consisting of descriptons of Turing machines...." Does that mean A is *all* descriptions of Turing machines, or just some? But from here I'm not sure how to go from a Turing-recognizable enumerator. *Note: M(n) is "M sub n". Anyone have any hints/suggested approaches? Thanks in advance, Ben
From: Ben Bacarisse on 27 Jun 2010 08:52 BJS <bschilke(a)gmail.com> writes: > Taken from Michael Sipser's Theory of Computation: > > "4.28 Let A be a Turing-recognizable language consisting of > descriptions of Turing machines , {<M(1)*>, <M(2)>, ...}, where every > M(i) is a decider. Prove that some decidable language D is not > decided by any decider M(i) whose description appears in A. (Hint: You > may find it helpful to consider an enumerator for A.)" > > So my attempt at this is to let some enumerator E match the Turing- > recognizable language A, but the description of A seems rather vague: > "Let A be a Turing-recognizable language consisting of descriptons of > Turing machines...." Does that mean A is *all* descriptions of Turing > machines, or just some? It means just some, but an arbitrary "some". The effect is that no such A exists that includes all decidable languages because for any A you will show that a language D exists that is not decided by any M (whose description is) in A. > But from here I'm not sure how to go from a > Turing-recognizable enumerator. I think you are supposed to construct an argument that is similar to diagonalisation. Does that help? <snip> -- Ben.
From: BJS on 28 Jun 2010 23:26
On Jun 27, 8:52 am, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > BJS <bschi...(a)gmail.com> writes: > > Taken from Michael Sipser's Theory of Computation: > > > "4.28 Let A be a Turing-recognizable language consisting of > > descriptions of Turing machines , {<M(1)*>, <M(2)>, ...}, where every > > M(i) is a decider. Prove that some decidable language D is not > > decided by any decider M(i) whose description appears in A. (Hint: You > > may find it helpful to consider an enumerator for A.)" > > > So my attempt at this is to let some enumerator E match the Turing- > > recognizable language A, but the description of A seems rather vague: > > "Let A be a Turing-recognizable language consisting of descriptons of > > Turing machines...." Does that mean A is *all* descriptions of Turing > > machines, or just some? > > It means just some, but an arbitrary "some". The effect is that no such > A exists that includes all decidable languages because for any A you > will show that a language D exists that is not decided by any M (whose > description is) in A. > > > But from here I'm not sure how to go from a > > Turing-recognizable enumerator. > > I think you are supposed to construct an argument that is similar to > diagonalisation. Does that help? > > <snip> > -- > Ben. Ah... Thanks! That does help. |