Redirected
recategorized by
1,229 views
0 votes
0 votes

Consider the following statements( ):

$S_1$: There exist no algorithm for deciding if any two Turing machine $M_1$ and $M_2$ accept the same language

$S_2$: The problem of determining whether a Turing machine halts on any input is undecidable

Which one of the following options is correct?

  1. Both $S_1$ and $S_2$ are correct
  2. Both $S_1$ and $S_2$ are not correct
  3. Only $S_1$ is correct
  4. Only $S_2$ is correct
recategorized by

3 Answers

2 votes
2 votes

Answer : 1

$S_1$ : "There exists no algorithm for deciding if any two Turing machine M1 and M2 accept the same language."

It is the standard "Equivalence problem" for the Recursive Enumerable languages and It is Undecidable. Hence, No Algorithm possible. 

$S_2$ : "The problem of determining wether a Turing machine halts on any input is undecidable."

Yes. It is the standard "Halting problem of TM". It is Undecidable and Hence, No Algorithm possible.

 

0 votes
0 votes

Option A

S1 : Equivalence test of two TM  is undecidable
S2: Halting Problem of TM is undecidable

0 votes
0 votes
  • Statement S1 is correct.

  • • The equivalence of two Turing machines is undecidable. There exists no algorithm that can find if two Turing machines accept the same language or not.

  • • There exists a machine M2 that accepts the same language as accepted by Turing machine M1 but, if two Turing machines are equal or not, is not decidable. This is a non-trivial property in Turing machines.

  • Statement S2 is correct.

  • It is related to the halting problem of Turing machine. A recursive language is decidable if there exists a Turing machine that either halts or rejects an input. But it cannot be decided whether it halts on any input. According to the concept of rice theorem, it is undecidable.

Related questions

1 votes
1 votes
2 answers
1
Pooja Khatri asked Jul 13, 2018
15,274 views
Two finite state machines are said to be equivalent if they:Have the same number of edgesHave the same number of statesRecognize the same set of tokensHave the same numbe...
0 votes
0 votes
2 answers
2
0 votes
0 votes
6 answers
3
0 votes
0 votes
3 answers
4
Pooja Khatri asked Jul 13, 2018
3,222 views
Pushdown automata can recognize language generated by _______Only context free grammarOnly regular grammarContext free grammar or regular grammarOnly context sensitive gr...