5

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?

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
Glen Marek
  • 75
  • 4

1 Answers1

2

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

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

Then, (MMi,I, M∞, M∞) is in L iff Mi 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 Mi, Mj, and Mk are three Turing Machines whose respective languages are not equal, then M will eventually spit out the triple (Mi, Mj, Mk).

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.

Ben Taitelbaum
  • 7,343
  • 3
  • 25
  • 45
  • Huh...interesting. Would you say that this language L is recursively enumerable? – Glen Marek Mar 10 '12 at 06:46
  • I updated the response to address the question of recursively enumerable. This was a really fun problem :) – Ben Taitelbaum Mar 10 '12 at 08:52
  • Oh your solution is very interesting, I am learning a lot about recursive enumerability and decidability.I am glad you had fun with it. I do have one question though, if a language is not RE, doesn't that automatically mean it's undecidable? Or am I missing something? – Glen Marek Mar 10 '12 at 09:07
  • yes, you're correct. Technically I only needed to show that it's not RE, I just couldn't figure out how to do that at first, and wanted to make sure it wasn't decidable. – Ben Taitelbaum Mar 10 '12 at 11:36
  • Your proof seems to work for the analogous question with two Turing machines. I wonder why the instructor used three? – Nemo Mar 10 '12 at 13:57
  • Okay, glad I am not missing some important concept. I have no idea why he used three, I am not sure if there is a difference. – Glen Marek Mar 11 '12 at 04:38
  • I was wondering about why this is a tripe instead of a pair all weekend as well. My only guess is that either there's a solution that uses all 3, or it's just extra information. I'm hoping I correctly understood 'not equal' to mean that 'not all of them are equal', rather than 'any two of them are not equal'. The same basic proof holds, but you have to change the third element to be something else. – Ben Taitelbaum Mar 12 '12 at 03:05
  • Does showing that an assumption leads to a paradox imply that the assumption is incorrect? If we assume the axioms of set theory, and use that to arrive at Russell's Paradox, does that negate set theory? In other words, we didn't assume M and then show that M can't exist, we assumed M and then found an element that is neither in M nor not in M. This shows the incompleteness of L(M), but I'm not sure about the recursive enumerability. – Ben Taitelbaum Mar 12 '12 at 03:12