Zeal Test Series 2019: Theory of Computation - Turing Machine

Question

i marked the a) answer is D)please explain it

 

Answer 1

Answer : B

---

1. $L = \left \{ <M>| M\,\,\, is\,\,\, a\,\,\, DFA \,\,\,and\,\,\, M\,\,\, accepts\,\,\, 0001 \right \}$

This is very much Decidable, Hence, RE. Just Run $DFA\,\,M$ on the input string $0001.$

"Informally and intuitively," We can design a Halting TM $T$ which will take as input $M$ and run it on string $0001,$ and will definitely Halt because $DFA\,\,M$ will definitely Halt and say Yes if $M$ accepts $0001$ Or it will definitely say No if $M$ does not accept $0001.$

Note that $M$ accepts  string $0001$ doesn't mean that $L(M) = $ {$0001$}

---

2. $L = \left \{ <M>| M\,\,\, is\,\,\, a\,\,\, TM \,\,\,and\,\,\, M\,\,\, accepts\,\,\, 1000 \right \}$

$M$ is a TM, so, $L(M)$ is a RE language. And Property $P : String\,\,\, 1000\,\,\, belongs\,\,\, to\,\,\, RE$ is a Non-trivial and  Monotone property. 

(A property $P$ of languages is monotone (w.r.t $RE$ languages) if for all RE sets $A$ and $B$, whenever $A ⊆ B$ and $P(A),$ we have $P(B).$ In Other Words, $P$ is monotone if whenever a set has the property, then all supersets of that set have it as well.)

Because of Non-trivial property, It is Undecidable (Not REC) But because of Monotone property, we can't further use Rice's theorem to check Recognizability (That is applicable only for Non-monotone properties of RE languages). So, When these fancy tools don't work for us, We use the basic definition of Recognizability which is that We should be able to Halt and say "Yes" for all the members But we say No or we may not Halt at all for Non-members. 

Here, The members are all the TM $M$ such that $1000 \in L(M).$ So, Since If we have a member $M,$ then we can build a TM $T$ which will run $M$ on $string \,\,1000$ and since $1000 \in L(M),$ $M$ will Halt on $1000$ and say Yes. So, $T$ will Halt and say Yes. But for Non-member $M'$,  $M'$ may not Halt on $string \,\,1000$ and so $T$ can't necessarily say No for all Non-members.

Hence, RE.

---

3. $L = \left \{ <M>| M\,\,\, is\,\,\, a\,\,\, TM \,\,\,and\,\,\, M\,\,\, accepts\,\,\, 1001\,\,\, but \,\,\,M\,\,\, doesn't\,\,\, accept\,\,\, 1100 \right \}$

We can apply Rice's theorem on this for Decidability as well as recognizability. It is a Non-trivial Property as well as Non-monotone property. $L(T_{Yes} )$ = {$0,11, 1001$} and $L(T_{No} )$ = {$0,11, 1001, 1100$}

Hence, Not-RE.

---

4. I'll have to read Sipser to know more about this problem. But til then you can make use of the following link :

https://math.stackexchange.com/questions/43276/minimal-turing-machines-are-not-recursively-enumerable-kolmogorov-complexity-i

But It is Not-RE.

Comments

@Deepak Poonia 

Sir, what can we say about the language $L_1$? Do every DFA which accepts 0001 have a certain pattern in their encoding that could form a regular expression? If not, then could it be possibly a CSL?

And what if $L_1$ was {<M>| M is the minimal DFA which accepts 0001}. What can we say about this language?

---

@DebRC

$\text{“M is the minimal DFA which accepts 0001”} $ doesn’t make any sense. We create Minimal DFA for a regular language, not for a string. 

$L = \{<M> | \text{ M is a DFA which accepts 0001}  \} $ Here $L$ is decidable as we have an algorithm to decide if a given DFA $M$ accepts string $0001$ or not, & that algorithm is to simply run $M$ on $0001.$

---

Got it sir. Thank you!

Answer 2

1) m is DFA m accepts 001 it is decidable you can draw DFA for it which has regular language as 001 is finite so it is RE ,so it is TM recognizable

2)m is TM m accepts 1000 according to rice theorem TM yes ={1000} and TM no ={sigma*} here TM yes is subset of TM no so it should be non RE and hence not Turing recognizable

3)M is TM m accepts 1001 and not 1100 similar to 2 it should not RE hence not Turing recognizable

4)there is no algo for Tm minimisation so not decidable and hence it not RE

I am weak in this topic so please someone check it andPlease correct me if i am wrong

Comments

Its answer is D ) please anyone check it

---

No, answer won't be D. Though as you say It is Given D. But it is Not D.

Answer 3

Read the rice's theorem on gate cse it will be helpful to solve this