9,950 views
34 votes
34 votes

Which one of the following is not decidable?

  1. Given a Turing machine $M$, a string $s$ and an integer $k$, $M$ accepts $s$ within $k$ steps
  2. Equivalence of two given Turing machines
  3. Language accepted by a given finite state machine is not empty
  4. Language generated by a context free grammar is non-empty

4 Answers

Best answer
39 votes
39 votes

Option B. Equivalence of two TMs is undecidable.

Option (A) is not halting problem. In Halting problem no. of steps can go up to 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.

For Options (C) and (D) we do have well defined algorithms making them decidable.

edited by
16 votes
16 votes

(A)M can either accept, go into loop or halt within K steps(which are finite). So within K steps, we are guaranteed to get an answer whether a string will be accepted or not. So this is Decidable.

(B)Equivalence of two Turing machines would require for any two machines M1 and M2 we must be able to check

 L(M1) = L(M2).

Even if two machines halt on every input that is given to them, we cannot keep checking this indefinitely over ∑*.

   So, this is undecidable.

(C)This is decidable. Given a finite state machine we can look for a path from initial state to final state. If such a path exists, we can say language accepted by a given FA is not empty.

(D)Decidable : Given a Context-Free grammar G, we can look for useless symbols in grammar. If all the symbols of a production of grammar are useless, surely the language generated by the Context-free Grammar is empty, otherwise not.

edited by
0 votes
0 votes

opt A: They are saying about Halting Turing Machine which is decidable because it halts within a certain amount of steps. It is decidable.

opt C:Emptiness problem is decidable with a finite state machine.

opt D:CFG is decidable with emptiness problem

opt B: equality theorem fails in turning machine.so it is undecidable

 

Answer:

Related questions

25 votes
25 votes
4 answers
1
25 votes
25 votes
2 answers
3
21 votes
21 votes
3 answers
4
Kathleen asked Sep 29, 2014
4,971 views
The correct matching for the following pairs is$$\begin{array}{ll|ll}\hline \text{A.} & \text{All pairs shortest path} & \text{1.} & \text{Greedy} \\\hline \text{B.} & \...