Question

i) Show that there is no algorithm for deciding if any two Turing machines M1 and M2 accept the same language.

ii) How is the conclusion of ii affected if M2 is a finite automaton?

Answer 1

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

i) Let us consider an algorithm A which decides L(M1) = L(M2) when it is input M1 and M2

Consider a Turing machine  M2 which rejects every string of the language ,hence L(M) =

Example : we can construct M2 by taking the start state to be the rejecting state.

Feed M and M2 to algorithm A. If L(M) = L(M2), concludes that M accepts the empty language. If L(M) L(M2).concludes that language that the language accepted by M is not empty.

Another explanation: If two Turing machines are given, they can be easily converted to C programs. The C programs can store a variable that will give the state of the Turing machine, an array that represents the tape of the Turing machine and an integer that gives the position of the head on the tape.

If it is possible to decide if two C programs do the same task, then it is possible to say that two Turing machine accepts the same language. But it is impossible to decide using an algorithm if two Turing machines accept the same language. So it is impossible to decide if two C programs do the same task.

ii) If M2 is a finite automaton, then also the above statement holds good because finite automaton accepts the regular language, and it will not contradict with the above statement.