UGC NET June-2019 CS Paper-2

(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 2^r squares of its tape, then there are at most Alpha=mK^2r 2^r configurations(why?). If M runs on w for more than α steps, and does not use more than 2^r 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 2^r squares, M* halts and accepts.
If M rejects w within α steps with using at most 2^r squares, M* halts and rejects.
If M goes beyond 2^r squares, M* halts and rejects.

If M does not halt and does not go beyond 2^r 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)