Let S={0,1}. Suppose we have a way to code any Turing machine to w in
S^* in a way that there does not exists three consecutive ones in w.
Let M_w be the turing machine with code w in S^* and L(M_w) the
language which M_w accepts.
Consider language Lne = {w in S^* | L(M_w) is non-empty}
Lemma: Lne is recursively enumerable.
Proof: Construct machine M in following way
0) Check that w is legal code for some TM, if not then reject the
input
1) Given input w, write in the tape w followed by 111.
Non-deterministically generate arbitrary x in S^* and write it after
the 111.
2) Rewind to the start of the tape. Simulate universal TM with input
w111x generated in step 1.
Now, w in Lne <=> x in L(M_w) for some x in S^*
<=> w111x in L(U) for some x in S^* (U is universal TM)
<=> w in L(M)
and hence Lne is recursively enumerable.
This is a not-so-formal proof copied from notes (added step 0). Similar
version is in [1].
There is one thing which I don’t understand. How come we can generate
arbitrary x in step 1? I mean, if every non-deterministic TM with given
input can be emulated with deterministic TM, shouldn’t we be able to
generate random x with deterministic TM as well? If so, how it is done?
Or, if we have non-deterministic TM which can guess input what M_w
accepts then this problem would be recursive, wouldn’t it?
Does the situation change if we change x to be always 0, i.e. what is
the meaning of "arbitrary" x?
I could understand this if we, in step 1, first let x be 0, then go to
step 2 and emulate M_w with input 0 n steps. Then go to step 1 again,
add 1 to x, and go to step 2 and emulate M_w with input x n steps more
(the state reached in previous round is stored) and with input x+1 n
steps etc. If L(M_w) is non-empty M will eventually accept some
(finite) string, otherwise it is stuck.
[1] Introduction to automata theory, languages and computation, chap.
9.3.2, thm 9.8.
- Hide quoted text — Show quoted text -
un student wrote:
> Let S={0,1}. Suppose we have a way to code any Turing machine to w in
> S^* in a way that there does not exists three consecutive ones in w.
> Let M_w be the turing machine with code w in S^* and L(M_w) the
> language which M_w accepts.
> Consider language Lne = {w in S^* | L(M_w) is non-empty}
> Lemma: Lne is recursively enumerable.
> Proof: Construct machine M in following way
> 0) Check that w is legal code for some TM, if not then reject the
> input
> 1) Given input w, write in the tape w followed by 111.
> Non-deterministically generate arbitrary x in S^* and write it after
> the 111.
> 2) Rewind to the start of the tape. Simulate universal TM with input
> w111x generated in step 1.
> Now, w in Lne <=> x in L(M_w) for some x in S^*
> <=> w111x in L(U) for some x in S^* (U is universal TM)
> <=> w in L(M)
> and hence Lne is recursively enumerable.
> This is a not-so-formal proof copied from notes (added step 0). Similar
> version is in [1].
> There is one thing which I don’t understand. How come we can generate
> arbitrary x in step 1?
Run through every possible value of x.
- Hide quoted text — Show quoted text -
> I mean, if every non-deterministic TM with given
> input can be emulated with deterministic TM, shouldn’t we be able to
> generate random x with deterministic TM as well? If so, how it is done?
> Or, if we have non-deterministic TM which can guess input what M_w
> accepts then this problem would be recursive, wouldn’t it?
> Does the situation change if we change x to be always 0, i.e. what is
> the meaning of "arbitrary" x?
> I could understand this if we, in step 1, first let x be 0, then go to
> step 2 and emulate M_w with input 0 n steps. Then go to step 1 again,
> add 1 to x, and go to step 2 and emulate M_w with input x n steps more
> (the state reached in previous round is stored) and with input x+1 n
> steps etc. If L(M_w) is non-empty M will eventually accept some
> (finite) string, otherwise it is stuck.
> [1] Introduction to automata theory, languages and computation, chap.
> 9.3.2, thm 9.8.