1
$\begingroup$

The language that determines if two Turing machines are equivalent is not recursively enumerable because you can reduce it to the emptiness problem (does a Turing machine take no input).

Then for the complement of this language (ie. if two Turing machines are not equivalent) would you be able to reduce that to the non-emptiness problem (a Turing machine takes some input)?

And thus this language would be recursively enumerable.

However, I thought the Turing machine equality language is an example where both a language and its complement are not recursively enumerable.

$\endgroup$
  • $\begingroup$ I assume that by "equivalent", you mean that the machines have the same outcome (accept/reject/loop) for every input? $\endgroup$ – David Richerby Nov 8 '17 at 21:59
  • $\begingroup$ Right, sorry if that wasn't clear. $\endgroup$ – user79943 Nov 8 '17 at 22:56
3
$\begingroup$

The language that determines if two Turing machines are equivalent is not recursively enumerable because you can reduce it to the emptiness problem (does a Turing machine take no input).

You have the reduction the wrong way around. You're saying "Telling if two Turing machines are equivalent is impossible because, if I could solve some impossible problem, I could solve this one." Well, that's like saying, "Lifting a can of beans is impossible because lifting a truck is impossible and, if I could lift a truck, I could lift a can of beans."

Rather, you want to reduce the known-hard problem to TM equivalence: "If I could solve this problem, I'd be able to solve this impossible problem." Specifically, if you could solve the TM equivalence problem, you could solve the TM emptiness problem by asking, "Is the machine I'm interested in equivalent to this machine that immediately rejects every input?"

Then for the complement of this language (ie. if two Turing machines are not equivalent) would you be able to reduce that to the non-emptiness problem (a Turing machine takes some input)?

Again, you mean the reduction to be the other way around. So, we need to show that the non-equivalence problem being RE would make the non-emptiness problem RE. But the non-emptiness problem is RE: just dovetail simulations of the machine on all inputs and accept if it accepts one of them. So there's no contradiction available, here.

However, I thought the Turing machine equality language is an example where both a language and its complement are not recursively enumerable.

Correct. Intuitively, you can't enumerate the language of inequivalent TMs because to do that would require you to definitively say "This machine loops on some input that this other machine accepts." And, indeed, we can turn this intuition into a formal proof.

First, observe that the Turing machine non-halting problem (given a description of a Turing machine $M$ and an input $x$, does $M(x)$ loop?) is not RE. This is the complement of the halting problem so, if it were RE, then both the halting problem and its complement would be RE. But if a language and its complement are both RE, they're both recursive, and we know that the halting problem isn't recursive.

Now, observe that, if we could solve the TM inequivalence problem, we could solve the non-halting problem. To determine if $M$ loops on input $x$, just ask if it is inequivalent to the machine "If the input is $x$, halt; otherwise, do the same as $M$."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy