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 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 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 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 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\inA*}. 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


There are 5 questions to complete.

1 thought on “Turing Machine”

Leave a Comment