Decidability-and-Undecidability

Question 1

Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.

    L1 = | L(M) = Φ}
    L2 = {| M on input w reaches state q in exactly 100 steps}
    L3 = {| L(M) is not recursive}
    L4 = {| L(M) contains at least 21 members}
A
L2 and L3 only
B
L1 and L3 only
C
L2, L3 and L4 only
D
L1, L3 and L4 only
Theory-of-ComputationDecidability-and-UndecidabilityGATE 2020Video-Explanation
Question 1 Explanation: 
L1 is undecidable as emptiness problem of Turing machine is undecidable. L3 is undecidable since there is no algorithm to check whether a given TM accept recursive language. L4 is undecidable as it is similar to membership problem.
Only L3 is decidable. We can check whether a given TM reach state q in exactly 100 steps or not. Here we have to check only upto 100 steps, so here is not any case of going to infinite loop.
Question 2

Which of the following statements is false?

A
The Halting problem of Turing machines is undecidable.
B
Determining whether a context-free grammar is ambiguous is undecidbale.
C
Given two arbitrary context-free grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
D
Given two regular grammars G1 and G2 it is undecidable whether L(G1) = L(G2).
Theory-of-ComputationDecidability-and-UndecidabilityGATE 1996
Question 2 Explanation: 
Equivalence of regular languages is decidable under
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1st for CSL and REC.
→ None for RE.
Question 3

Which one of the following is not decidable?

A
Given a Turing machine M, a stings s and an integer k, M accepts s within k steps
B
Equivalence of two given Turing machines
C
Language accepted by a given finite state machine is not empty
D
Language generated by a context free grammar is non empty
Theory-of-ComputationDecidability-and-UndecidabilityGATE 1997
Question 3 Explanation: 
(A) It is not halting problem. In halting problem number of steps can go upto infinity and that is the only reason why it becomes undecidable.
In (A) the number of steps is restricted to a finite number 'k' and simulating a TM for 'k' steps is trivially decidable because we just go to step k and output the answer.
(B) Equivalence of two TM's is undecidable.
For options (C) and (D) we do have well defined algorithms making them decidable.
Question 4

Consider the following decision problems:

    (P1) Does a given finite state machine accept a given string
    (P2) Does a given context free grammar generate an infinite number of stings

Which of the following statements is true?

A
Both (P1) and (P2) are decidable
B
Neither (P1) nor (P2) are decidable
C
Only (P1) is decidable
D
Only (P2) is decidable
Theory-of-ComputationDecidability-and-UndecidabilityGATE 2000
Question 4 Explanation: 
For P1, we just need to give a run on the machine. Finite state machines always halts unlike TM.
For P2, check if the CFG generates any string of length between n and 2n−1, where n is the pumping lemma constant. If So, L (CFG) is infinite, else finite. Finding the pumping lemma constant is not trivial. So both P1, P2 are decidable.
Question 5

Consider two languages L1 and L2 each on the alphabet ∑. Let f: ∑ → ∑ be a polynomial time computable bijection such that (∀ x)[x ∈ L1 iff f(x) ∈ L2]. Further, let f-1 be also polynomial time computable.

Which of the following CANNOT be true?

A
L1 ∈ P and L2 is finite
B
L1 ∈ NP and L2 ∈ P
C
L1 is undecidable and L2 is decidable
D
L1 is recursively enumerable and L2 is recursive
Theory-of-ComputationDecidability-and-UndecidabilityGATE 2003
Question 5 Explanation: 
L1 is polynomial time reducible to L2.
Now if L2 is decidable then L1 should also be decidable. Hence, option (c) is wrong.
Question 6

Choose the correct alternatives (More than one may be correct).

It is undecidable whether:
A
An arbitrary Turing machine halts after 100 steps.
B
A Turing machine prints a specific letter.
C
A Turing machine computes the products of two numbers.
D
None of the above.
E
Both (B) and (C).
Theory-of-ComputationDecidability-and-UndecidabilityGATE 1990Video-Explanation
Question 6 Explanation: 
A) An arbitrary TM halts after 100 steps is decidable. We can run TM for 100 steps and conclude that.
B) A TM prints a specific letter is undecidable.
C) A TM computes the products of two numbers is undecidable. Eventhough we can design a TM for calculation product of 2 numbers but here it is asking whether given TM computes product of 2 numbers, so the behavior of TM unknown hence, undecidable.
Question 7

Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

A
P3 is decidable if P1 is reducible to P3
B
P3 is undecidable if P3 is reducible to P2
C
P3 is undecidable if P2 is reducible to P3
D
P3 is decidable if P3 is reducible to P2's complement
Theory-of-ComputationDecidability-and-UndecidabilityGATE 2005
Question 7 Explanation: 
Option A: If P1 is reducible to P3 then P3 is atleast as hard as P1. So there is no guarantee if P3 is decidable.
Option B: If P3 is reducible to P2, then P3 cannot be harder than P2. But P2 being undecidable, this can't say P3 is undecidable.
Option C: If P2 is reducible to P3, then P3 is atleast as hard as P2. Since, P2 is undecidable. This means P3 is also undecidable.
There are 7 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access