UGC NET CSE | June 2019 | Part 2 | Question: 79

Question

Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing machine $M$?

1. $G$ is a CFG with $L(G)=\phi$
2. There exist two TMs $M_1$ and $M_2$ such that $L(M) \subseteq \{L(M_1) \cup L(M_2)\} = $ language of all TMs​​​​​.
3. $M$ is a TM that accepts $\omega$ using at most $2^{\mid \omega \mid}$ cells of tape

• A. i and ii only
• B. i only
• C. i, ii and iii
• D. iii only

Comments

C) a,b and c is correct option

a): L(G)=∅ is a emptiness problem and emptiness problem for context free languages is decidable.

(b): Recursive: The reason is we can assume L(M2)=∑* and hence any TM (M1) will be definitely subset of L(M2). So we only need to see that M1 is a valid Turing machine and no need to check whether it is subset of L(M2) as it is obviously subset of L(M2)=∑*. Checking validity of Turing machine is always a halting process, hence it is recursive.

(c): L={(M,w)|M is a TM that accepts w using at most 2|w| squares of its tape}.
Recursive: Let m be he number of states in M, and k be the size of the alphabet that M uses, and r=|w|. If M uses at most 2r squares of its tape, then there are at most Alpha=mK2r 2r configurations(why?). If M runs on w for more than α steps, and does not use more than 2r squares of its tape, then M must be in the one configuration at least twice(pigeonhole principle), in which case M would enter an infinite loop on input w. Based on this, we design a machine M* that decides L that works as follows:
M* runs M on w for at most α+1 steps.
If M accepts w which steps with using at most 2r squares, M* halts and accepts.
If M rejects w within α steps with using at most 2r squares, M* halts and rejects.
If M goes beyond 2r squares, M* halts and rejects.
If M does not halt and does not go beyond 2r squares, M* rejects.
Note: To know the definition of configurations and the details, reader may refer to "Introduction to theory of computation Michael Sipser, Chapter 8 Space complexity)

Answer 1

B is the answer according to me. 

a) is decidable because emptiness problem for Context free languages is decidable. L(G)=ϕ, where G is CFG is decidable.

b) is the subset problem for Turing machines. Since M1 and M2 are TMS so {L(M1) U L(M2)} is also accepted by a  TM (closed under union). Hence, L(M) ⊆ {L(M1) U L(M2)} is undecidable because subset problem is only decidable for regular languages.

c) is the membership problem for Turing machines, hence undecidable.  We cannot say whether w∈M or not. 

Comments

But C is the official answer by NTA

---

what is it then?