The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.6k views

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
asked in Theory of Computation by Veteran (59.5k points) | 1.6k views
0
Sir please say something more about it .i mean some more info about the equivalence of TM
0

4 Answers

+22 votes
Best answer

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.

answered by Boss (14.3k points)
edited by
+1
option A is the famous Halting problem which is undecidable.
+20
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.
0
equivalance of two machine is decidable only for finite automata
+1
0

Probably not. 

http://www.sciencedirect.com/science/article/pii/S0022000077800196

I haven't read the posted article so apologies if it says something else.

+1
0
Both option A and B are unDecidable. Option A is undecidable which is the most popular problem and   TM is undecidable in Equivalence.
0
@Brij Please read above
+2

Equivalence problem for two Turing machines are not decidable because RE languages are not closed under complement.

Suppose M1 and M2 are two Turing machines, M1 and M2 are equivalent if both accepts the same language.

Suppose M1 accepts the language L1 and M2 accepts the language L2, we have to check if L1 = L2 then M1 will be equivalent to M2. Calculate symmetric difference of the languages:


L = (L1∩$L2^c$) U (L2∩$L1^c$) if L1=L2 then L will be empty language. 


RE languages are not closed under Complement and emptiness property is not decidable for RE.

0
Is trivially decidable same as partially decidable?
0
yes.
0
@Arjun sir, Can you publish this comment along with the answer in go pdf? It will be more clear because in go pdf they have mention only which option is correct no detailed explanation of this answer is given.
0
@Parth Have added.
+6 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.

answered by Boss (12.3k points)
edited by
0
Given two TMs both of which are halting for any given string, can we check their equivalence?
0
Sir, I think if both are halting for any given string, still we need to check whether they are halting on some final state for given string which is state entry problem, and this is undecidable. So we cannot check their equivalence.
0
No, I asked for "halting TMs", whose state entry problem is decidable.
0
Yes, sir in that case we can check their equivalence. Because for each string w we can decide whether it belongs to the language of TM or not.Such languages are recursive.
+1
Then that would mean equivalence of PDAs is also decidable rt?
0
But if equivalence of PDA is decidable, then it would lead to decidability of L(G1) = L(G2) for any CFG G1 and G2 anf if this happens then we would have a solution to PCP problem which is undecidable.
0
Yes, so that means your assumption is wrong. This is because even if membership problem is decidable checking equivalence may not be due to the fact that there are an infinite number of strings to be checked.
0

Ohh so that means the membership algorithm that exists for REC languages exists due to the fact that for every W our turing machine is guaranteed to halt and tell the answer whether the string W is in our L(TM) or not.

But given 2 HTM, we cannot keep checking their equivalence over ∑*   and tell that they are equivalent.

0
Is my statement correct now arjun sir?
–1 vote
Gate keeda:what i have read the halting problem is given a input to a TM tell me whether a TM will halt or not
answered by Boss (14.3k points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,440 questions
46,623 answers
139,377 comments
57,022 users