ago
30 views
0 0 votes

Which of the following languages are Turing-recognizable?

  1. $\{\langle M\rangle\mid M\ \mathrm{is\ a\ deterministic\ TM\ and}\ M\ \mathrm{accepts}\ 010\}$
     
  2. $\{\langle M\rangle\mid M\ \mathrm{is\ a\ nondeterministic\ TM\ and}\ M\ \mathrm{accepts}\ 010\}$
     
  3. $\{\langle M\rangle\mid M\ \mathrm{is\ a\ TM\ and}\ M\ \mathrm{does\ not\ accept}\ 101\}$
     
  4. $\{\langle M\rangle\mid M\ \mathrm{is\ a\ TM\ and}\ L(M) = \Sigma^*\}$

1 Answer

0 0 votes

For A, given $\langle M\rangle$, simply run $M$ on $010$.

If $M$ accepts, accept.

If $M$ rejects or loops, the recognizer may reject or loop. Therefore the language is recognizable.

$\boxed{\mathrm{A}\in\mathrm{RE}}$
 

For B, nondeterministic TMs and deterministic TMs have the same recognition power. A deterministic TM can systematically simulate the computation tree of the NTM.

Hence,

$\boxed{\mathrm{B}\in\mathrm{RE}}$.


For C, notice the phrase:

$M\ \mathrm{does\ not\ accept}\ 101$.

This includes two possibilities $: \mathrm{reject}$ or $\mathrm{loop\ forever}$.

If $M$ loops on $101$, we cannot wait for some finite event that confirms that it will never accept. Thus this language is not Turing-recognizable.


For D, checking whether a TM accepts every possible string cannot be recognized simply by running strings one after another, since some simulations may loop forever.

Therefore, 

Answer : $\boxed{\mathrm{A\ and\ B}}$

ago
Answer:
Position:
Show:

Related questions

1 1 vote
1 1 answer
47
47 views
GO Classes asked 2 days ago
47 views
Which of the following languages are recognizable?$\{\langle M\rangle\mid M\ \mathrm{is\ a\ TM\ and}\ L(M)\ \mathrm{is\ finite}\}$ $\{\langle M_1,M_2,w\rangle\mid M_1\ \m...
0 0 votes
1 1 answer
30
30 views
GO Classes asked 2 days ago
30 views
Which of these statements are true for all choices of TM $M$, string $w$, and language $L$?If $M$ recognizes $L$ and $M$ rejects $w$, then $w\notin L$. If $M$ recognizes ...
0 0 votes
1 1 answer
32
32 views
GO Classes asked 2 days ago
32 views
Define, $A_{\mathrm{TM}}=\{\langle M,w\rangle\mid M\ \mathrm{is\ a\ TM\ and}\ w\in L(M)\}$.Consider the TM $N$:On input $\langle M,w\rangle$:Simulate $M$ on $w$. If $M$ a...
0 0 votes
1 1 answer
27
27 views
GO Classes asked 2 days ago
27 views
Which of these statements are true for all choices of TM $M$, string $w$, and language $L$?If $M$ decides $L$ and $M$ rejects $w$, then $w\notin L$. If $M$ decides $L$ an...