# Turing Machine

 Question 1
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 1 Explanation:
 Question 2
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 2 Explanation:
 Question 3
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 3 Explanation:
 Question 4
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 4 Explanation:
 Question 5
Consider the following languages.
L1 = {$\lt$M$\gt$ |M takes at least 2016 steps on some input},
L2 = {$\lt$M$\gt$| M takes at least 2016 steps on all inputs g} and
L3 = {$\lt$M|M accepts $\varepsilon$},
where for each Turing machine M, $\lt$M$\gt$ denotes a specific encoding of M. Which one of the following is TRUE?
 A L1 is recursive and L2,L3 are notrecursive B L2 is recursiveand L1,L3 are notrecursive C L1,L2 are recursiveand L3 is notrecursive D L1,L2,L3 are recursive
GATE CSE 2016 SET-2   Theory of Computation
Question 5 Explanation:
 Question 6
Consider the following statements.
I. The complement of every Turing decidable language is Turing decidable
II. There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable

Which of the above statements is/are true?
 A Only II B Only III C Only I and II D Only I and III
GATE CSE 2015 SET-2   Theory of Computation
Question 6 Explanation:
 Question 7
Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?
 A it may halt and accept the input B it may halt by changing the input C it may halt and reject the input D it may never halt
ISRO CSE 2014   Theory of Computation
Question 7 Explanation:
 Question 8
Let $\lt M \gt$ be the encoding of a Turing machine as a string over $\Sigma$={0,1}.
Let L = { $\lt M \gt$ |M is a Turning machine that accepts a string of length 2014}.
Then, L is
 A decidable and recursively enumerable B undecidable but recursively enumerable C undecidable and not recursively enumerable D decidable but not recursively enumerable
GATE CSE 2014 SET-2   Theory of Computation
Question 8 Explanation:
 Question 9
Which of the following statements is/are FALSE?
1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union and complementation.
3. Turing decidable languages are closed under intersection and complementation.
4. Turing recognizable languages are closed under union and intersection.
 A 1 and 4 only B 1 and 3 only C 2 only D 3 only
GATE CSE 2013   Theory of Computation
Question 9 Explanation:
 Question 10
Define languages L0 and L1 as follows :
  L0 = {< M, w, 0 > | M halts on w}
L1 = {< M, w, 1 > | M does not halts on w}   
Here $< M, w, i >$ is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit. Let $L=L0 \cup L1$. Which of the following is true ?
 A L is recursively enumerable, but L' is not B L' is recursively enumerable, but L is not C Both L and L' are recursive D Neither L nor L' is recursively enumerable
GATE CSE 2003   Theory of Computation
Question 10 Explanation:
There are 10 questions to complete.