Decidability and Recursive Enumerability

Question

Say there exist Turing Machines M1, M2, M3, the languages they recognize being L(M1), L(M2), and L(M3), respectively. The following language L = {(M1, M2, M3) : L(M1), L(M2), and L(M3) are not equal} Is the language decidable? Recursively enumerable? Or neither?

Answer 1

Let M_Mi,I be a machine that simulates running some other machine M_i on input I and returns true if M_i eventually halts on I, and loops forever otherwise.

Let M_∞ be a trivial machine that simply loops forever.

Then, (M_Mi,I, M_∞, M_∞) is in L iff M_i halts on input I.

This reduces decidability of the halting problem to decidability of L, so therefore L is undecidable.

=============

Next, let's prove that L is not recursively enumerable by contradiction.

Assume that L is recursively enumerable, so there exists a Turing Machine M such that if M_i, M_j, and M_k are three Turing Machines whose respective languages are not equal, then M will eventually spit out the triple (M_i, M_j, M_k).

Now let's consider a modification to M, called M', that's defined by taking M and adding the value (M, M', M') to L(M'). The important question to ask is if (M, M', M') is in L? Well, if (M, M', M') is in L, then L(M) must not be equal L(M') (otherwise it wouldn't fit the definition to be in L), so L(M) must not include (M, M', M') (since that's the only modification we made). Conversely, if (M, M', M') is not in L, then L(M) != L(M') (because we added that tripe to L(M')), so it must therefore be in L(M), because the languages are not equal.

Thus, we've reached a paradox which implies that M cannot exist, and therefore L is not recursively enumerable.