# Turing Machine

 Question 1
Which of the following is/are undecidable?
MSQ
 A Given two Turing machines M1 and M2 , decide if L(M1 ) = L(M2 ). B Given a Turing machine M , decide if L(M ) is regular. C Given a Turing machine M , decide if M accepts all strings. D Given a Turing machine M , decide if M takes more than 1073 steps on every string.
GATE CSE 2022   Theory of Computation
Question 1 Explanation:
 Question 2
For a Turing machine M, < M > denotes an encoding of M. Consider the following two languages.

$\begin{array}{ll} L1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}$

Which one of the following options is correct?
 A Both L1 and L2 are decidable. B L1 is decidable and L2 is undecidable. C L1 is undecidable and L2 is decidable. D Both L1 and L2 are undecidable.
GATE CSE 2021 SET-1   Theory of Computation
Question 2 Explanation:

 Question 3
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine $M$.

$L_1=\{\left \langle M \right \rangle|L(M)=\varnothing \}$
$L_2=${$\left \langle M,w,q \right \rangle|M$ on input w reaches state q in exactly 100 steps}
$L_3=\{\left \langle M \right \rangle|L(M) \;is \; not \; recursive\}$
$L_4=\{\left \langle M \right \rangle|L(M) \;contains \; at \; least\; 21 \; members\}$
 A $L_1,L_3 \; and \; L_4 \; only$ B $L_1 \; and \; L_3 \; only$ C $L_2 \; and \; L_3 \; only$ D $L_2,L_3 \; and \; L_4 \; only$
GATE CSE 2020   Theory of Computation
Question 3 Explanation:
 Question 4
Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.

(I) For an unrestricted grammar G and a string w, whether w$\in$L(G)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammars G1 and G2, whether L(G1) = L(G2)
(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language.

Which one of the following statements is correct?
 A Only I and II are undecidable B Only III is undecidable C Only II and IV are undecidable D Only I, II and III are undecidable
GATE CSE 2018   Theory of Computation
Question 4 Explanation:
 Question 5
Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B*. We say f is computable if there exists a Turning machine M which given an input x in A*, always halts with f(x) on its tape. Let $L_{f}$ denote the language {x#f(x)|x$\in$A*}. Which of the following statements is true:
 A f is computable if and only if $L_{f}$ is recursive. B f is computable if and only $L_{f}$ recursively enumerable. C If f is computable then $L_{f}$ is recursive, but not conversely. D If f is computable then $L_{f}$ is recursively enumerable, but not conversely.
GATE CSE 2017 SET-1   Theory of Computation
Question 5 Explanation:

There are 5 questions to complete.