CODEWITHSUNDEEP
logiccomputation-theoryturing-machinescomputability
Neil Zhang
Neil Zhang

Reputation: 11

Why do we define equivalent turing machines as two turing machines with the same accepted languages?

From many textbooks about computability, I see how we define equivalent turing machines as follows:

Two turing machines TM1 and TM2 are equivalent <=> L(TM1) = (TM2)

where L(TM1) is the languages accpeted by TM1, i.e. L(TM1) = {w | TM1(w) = accept}, and so is L(TM2).

My question is: why does the above definition totally ignore the 'rejected languages' {w | TM1(w) = reject} and 'loop languages'{w | TM1(w) goes into infinite loop}?

Intuitively, TM1 and TM2 are equivalent if and only if their input-output relation are exactly the same, which means they output the same thing, or react in the same manner for any possible input. Say, if L(TM1) = L(TM2), then it is still possible that these exists some w0 such that TM1(w0)=reject while TM2(w0) goes into infinite loop, and thus we conclude that TM1 and TM2 are indeed not equivalent. However, according to the definition on textbooks, they are equivalent, which is not intuitive.

I try to obtain some explanation of the counterintuitive definition of equivalent Turing machines on textbooks.

Upvotes: 1

Views: 652

Answers (1)

EnMag
EnMag

Reputation: 83

Generally speaking the basic definition of Turing machines does not have a (explicit) notion of reject (see https://en.wikipedia.org/wiki/Turing_machine).
Then, there are many extensions along different directions that lead to slightly different formalizations. In fact, you can label a particular state as the reject state.
Notice that this extension does not change the expressive power of the computational model (see below).
Each extension is better suited to model different scenarios and serve different goals.
In some scenarios it could make perfect sense to employ a definition of equivalence that explicitly distinguishes between accepted and rejected words as you suggest.

I would like to point out that equivalence of Turing machines is all about the accepted languages. Internally, the two machines may behave in a completely different manner. In addition, it is not completely clear what the output of a Turing machine is; they simply execute on some input and they either accept it or they don't.

Of course, in the basic case in which we define Turing machines without explicit reject states it makes sense to define the language of the machine as the set of words that the machine accepts.
In addition, this is consistent with the definition used in automata theory.

In a more formal manner you can consider the following reduction sketch to compare the two settings.

Let EM0 and EM1 be two Turing machines with an explicit reject state. Assume we want to solve the problem of deciding whether the two machines accept and reject the same words.
We can reduce this problem to deciding the equivalence of two Turing machines (without explicit reject state).
Define M0 and M1 from EM0 and EM1 respectively by extending the tape alphabet with two fresh symbols R (for reject) and A (for accept). M0 accepts the language build by all the words accepted by EM0 extended with an additional A at the beginning and all the words rejected by EM0 extended with an additional R at the end.

L(M0) := {Aw | EM0(w) = accept} U {Rw | EM0(w) = reject}

Define M1 similarly such that:

L(M1) := {Aw | EM1(w) = accept} U {Rw | EM1(w) = reject}

where, using your notation, EM(w) = v means that EM on input w terminates on a v state.

Notice that I am skipping the details about how to actually build the two Turing machines with such language.

Finally, M0 is equivalent to M1 iff EM0 and EM1 accept / reject the same words.

Therefore, the standard definition of language and equivalence of Turing machines is already expressive enough to capture the accept / reject scenario you described and it is also simpler in the sense that it does not require the extra definition of rejecting states.

Upvotes: 0

Related Questions