Previous Year Questions: Turing Machine | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Q1: Which of the following is/are undecidable?  (2022)
(a) Given two Turing machines M₁ and M₂, decide if L(M₁) = L(M₂).
(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.
Ans: (a, b, c)
Sol:
Concept:
Option 1, option 2 and option 3 are all non-trivial properties of recursively enumerable language (recursively enumerable language means are the language of Turing machine) are not proved by Rice's theorem. So all the options are UNDECIDABLE.
Option 4: Given a Turing machine M, decide if M takes more than 1073 steps on every string. 
Turing Machine M decide if language L takes more than 1073 steps. Language L' takes almost 1073 steps, So, it is decidable. Then its complement is also decidable. Hence, L is decidable. A Turing Machine sees only at most the first 1073 symbols of input in its first 1073 steps. Hence whether it stops on the first 1073 steps depends only on the first 1073 symbols of input.
Since the number of strings of length 1073 is finite, it gives a way to decide this. Run the input machine M on all inputs of length 1073 and check whether any of them stops within 1073 steps. If so, reject, otherwise accept.
Hence the correct answer is option 1, option 2 and option 3.

Q2:  For a Turing machine M, < M > denotes an encoding of M. Consider the following two languages.
L₁ = {⟨M⟩ | M takes more than 2021 steps on all inputs}
L₂ = {⟨M⟩ | M takes more than 2021 steps on some input}
Which one of the following options is correct?  (2021 SET-1)
(a) Both L₁ and L₂ are decidable.
(b) L₁ is decidable and L₂ is undecidable.
(c) L₁ is undecidable and L₂ is decidable.
(d) Both L₁ and L₂ are undecidable.
Ans: (a)
Sol:
L₁ = {⟨M⟩ | M takes more than 2021 steps on all inputs}
L₂ = {⟨M⟩ | M takes more than 2021 steps on some input}
Here, both L₁ and L₂ are decidable as we can have a systematic procedure in deciding them (correctly saying if an input is in L or not)
For both L₁ and L₂ we have to monitor the TM for 2021 + 1 steps for all possible inputs of size 2021 (if the input set is having k alphabets we will have k²⁰²⁰ possible strings which is still a finite number.)
If for all the inputs M is taking more than 2021 steps, then it means for all larger strings also it must take more than 2021 steps and we can answer "yes" for L₁ or else "no".
If for none of the inputs M is taking more than 2021 steps then it means even for any larger string M won't be taking more than 2021 steps. So, we can answer "no" for L₂ or else "yes".
Thus we correctly decided both L₁ and L₂.
NOTE: There is intersection between

• "yes" case of L₁ and "yes" case of L₂
• "no" case of L₁ and "yes" case of L₂
• "no" case of L₂ and "no" case of L₁

but not between the "yes" case of L₁ and "no" case of L₂.
Correct Option: A.

Q3: Which of the following languages are undecidable? Note that ⟨M⟩ indicates encoding of the Turing machine M.  (2020)
L₁ = {⟨M⟩ ∣ L(M) = ∅}
L₂ = {⟨M, w, q⟩ ∣ M on input w reaches state q in exactly 100 steps}
L₃ = {⟨M⟩ ∣ L(M) is not recursive}
L₄ = {⟨M⟩ ∣ L(M) contains at least 21 members}
(a) L₁, L₃ and L₄ only
(b) L₁ and L₃ only
(c) L₂ and L₃ only
(d) L₂, L₃ and L₄ only
Ans: (a)
Sol:
We can answer this question just using Rice's theorem which states as follows:
Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable
Trivial property of a set: For all instances of the set the property evaluates to True or for all instances of the set the property evaluates to False. i.e., without inspecting the “given instance” we can say whether it has the property or not. For example, “Language accepted by a TM is recursively enumerable”. This is always true as any language accepted by a TM is called recursively enumerable by definition (it can also be recursive or context-sensitive or context-free or regular or finite also).
Non-trivial property of a set: For some instances of the set the property evaluates to True and for some it evaluates to False. For example,: “Language accepted by a TM is context free language”. This is true if the language can also be accepted by some PDA but is false if no such PDA exists like for
L = {ww | w ∈ {0, 1}*}.
L₁ = {⟨M⟩ | L(M) = ∅}

• L₁ is emptiness problem and is non-trivial because we can have two Turing machines M₁ and M₂ with
  L(M₁) = ∅ and L(M₂) = {0} (something non-empty).
• So, L₁ is undecidable.

L₃ = {⟨M⟩ | L(M) is not recursive}

• L₃ is also describing a non-trivial property (of the language of Turing machines) as the language of not all
  the Turing machines is recursive. For example, we can have a Turing machine for halting problem and its language is recursively enumerable but not recursive.

L₄ = {⟨M⟩ | L(M) contains at least 21 members}

• L₄ is also describing a non-trivial property as we can have two Turing machines M₁ and M₂ with say L(M₁) = {0} and L(M₂) = {0²ⁿ | n ≥ 0}, where the property holds for L(M₂) but not for L(M₁).
  So, L₄ is also undecidable.

L2 = {⟨Μ, w, q⟩ | M on input w reaches state q in exactly 100 steps}

• This is actually a property of Turing machine and not its language. Obviously this is a non-trivial property (but of TM and not its language and hence Rice's theorem is not applicable). Here, we have to check if the given TM on given input w reaches state q in exactly 100 steps - certainly decidable as we just need to monitor the working of Turing machine for 100 steps which should happen in a finite amount of time. But if instead of 100 steps the question is modified to reaching state q ever, then the problem becomes state reachability problem and there is no guarantee that we can answer this problem in finite amount of time (we can answer "yes" but not necessarily "no"), and the problem becomes undecidable (but is still semi-decidable).

So A is correct.

Q4: Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.  (2018)
(I) For an unrestricted grammar G and a string w, whether w E L(G)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammars G₁ and G₂, whether L(G₁) = L(G₂)
(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
Ans: (d)
Sol:

4^th Statement: Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language
Is Decidable because We can Always say that There will definitely be a DPDA (and for that matter PDA too) which will accept the same language that NFA N is accepting. But Careful, Saying that (From other answers for this question) "PDA (accepting CFL) having more power than NFA (accepting regular) so we can decide whether both will accept the same language or not." is WRONG.

"Given a <PDA> P and a NFA N, Deciding Whether they both accept the same language or not" is Undecidable. "
"Given a <DPDA> D and a NFA N, Deciding Whether they both accept the same language or not" is Decidable. "

3^rd Option (Third Statement): Given two grammars G₁ and G₂, whether L(G₁) = L(G₂)
is Undecidable. Because When nothing is mentioned about the type of the Grammar, It, by default, should be taken as A Valid Grammar i.e. Type 0 Grammar which itself covers All the Grammars.
So, Now the given problem is nothing but "Equivalence of two RE Grammars i.e. Equality of Two RE languages" Problem. Which is Undecidable.

Many students are confusing this statement with that of "Propositional Logic" statements. Which is not the case here. Let me elaborate: We all know that Equivalence of RE languages is Undecidable... But One could argue that Some RE languages are Regular also and for Regular languages, Equivalence Problem is Decidable. So Saying that "Equivalence of RE languages is Undecidable" would seem wrong. But We Know that It is NOT.
And This is because When we say "Decidable", It means that there is an Algorithm (Automation) to solve that problem and If that Problem is really decidable then You should be able to give an Algorithm for that, which for All Valid Instances should Halt and Say Yes/No

"Equality" and "Equivalence" are two different things. Equality of Grammars (Type 0-3 Grammars) is Decidable, But Equivalence is NOT Because Equivalence of Two Grammars is a relation defined by "Equality of Their Corresponding Languages", Which is Undecidable for Type-0 Grammars.
From the Comments on the question "In order to prove a statement wrong, we need only one counter example. Statement was " L1 = L2 is undecidable". It should not be true as it is decidable in case of regular languages.''"..
See, "In order to prove a statement wrong, we need only one counter example" is a Generalized statement (Not a Theorem or A Proven Fact) usually used in Logic.. But "Generalization" is the Enemy/opposite of "Specification / particularization / Specific ".
Correct Answer: D

Q5: 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 ∈ A*, always halts with f(x) on its tape. Let L_f denote the language {x # f(x) | x ∈ A*}. Which of the following statements is true:  (2017 SET-1)
(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.
Ans: (a)
Sol:
The question asks what is the reason being f computable.
Since x belongs to A* is a total function, therefore, every alphabet in x will yield some alphabet from B*(in simple words f(x)) if given to a Turing machine.
The question itself says that f is computable if there exists a Turing machine which always halts with output f(x). If any Turing machine has to be always halting that means the language accepted by the Turing machine must be recursive.
In other words A) f is computable if and only if L(f) is recursive.
Option C would have been correct "If f is computable then L(f) is recursive" but due to "but not conversely" sentence it became false.

Q6: Consider the following languages.
L₁ = {<M> |M takes at least 2016 steps on some input},
L₂ = {<M> | M takes at least 2016 steps on all inputs g} and
L₃ = {<M | M accepts ε},
where for each Turing machine M, <M> denotes a specific encoding of M. Which one of the following is TRUE?  (2016 SET-2)
(a) L₁ is recursive and L₂, L₃ are not recursive
(b) L₂ is recursive and L₁, L₃ are not recursive
(c) L₁, L₂ are recursive and L₃ is not recursive
(d) L₁, L₂, L₃ are recursive
Ans: (c)
Sol:
L₃ is not recursive as it asks if L(M) contains e which is a non-trivial property of r.e. languages and hence undecidable as per Rice's theorem.
L₁ and L₂ are slightly trickier as these are not describing properties of recursively enumerable languages, but rather of Turing machines. So, we can see if there is some procedure for deciding these.
For L₁ we can give the TM an input of length 2016. Now, it should at least make 2016 steps or reach the halt state before completing the input processing. The second case is possible only if the TM reaches a halt state before reaching the end of string (blank) of input, for all possible inputs of length at least 2016 and can be decided. So, we can be sure that otherwise TM will have at least 2016 steps making L₁ recursive.
L₂ is recursive and it is more easier to prove. For the complement of L₂ we need M to make less than 2016 steps for some input and we can just give it all possible inputs of length less than 2016 and see if it reaches a halt state within 2016 steps.
Thus complement of L₂ is recursive ⇒ L₂ is recursive.
So, answer here is C.

Q7: 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?  (2015 SET-2)
(a) Only II
(b) Only III
(c) Only I and II
(d) Only I and III
Ans: (d)
Sol: 
I. is true. The solution to a decision problem is either "yes" or "no", and hence if we can decide a problem, we have also decided its complement- just reverse "yes" and "no". (This is applicable for decidability and not for acceptance)
II. is false. Because NP class is defined as the class of languages that can be solved in polynomial time by a non-deterministic Turing machine. So, none of the NP class problems is undecidable.
III. is true for same reason as II.
So, answer is D.

Q8: Let <M> be the encoding of a Turing machine as a string over Σ={0,1}.  (2014 SET-2)
Let L = {<M> |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
Ans: (b)
Sol:
There are only a finite number of strings of length 2014. So, we can give all those strings to TM simulating each string for 1 step, then 2 step and so on (dovetailing), and if the TM accepts any of them ("yes" case of TM), we can say "yes". So, L is recursively enumerable.
(If the TM doesn't accept any string of length 2014, it can go to an infinite loop ("no" case of TM), and hence we can't say the method is decidable).
Now, to prove whether the problem is decidable or not we can make use of Rice's theorem. Rice's theorem (1) states that any non-trivial property of L(TM) is undecidable. L(TM) has a string of length 2014 is a non- trivial property as there are TMs whose language contains such a string and there are TMs whose language doesn't have such a string. So, the given problem is undecidable.

Q9: Which of the following statements is/are FALSE?  (2013)
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
Ans: (c)
Sol:
Recursive enumerable languages are not closed under complement while recursive languages are.
Both Recursive and Recursive enumerable languages are closed under intersection, union, and kleene star.
Non-Deterministic TM is equivalent to DTM
Only 2 is false. Option C is correct.
Note: Turing decidable language mean Recursive language and Turing recognizable language mean recursive enumerable language.