-1
$\begingroup$

$$L = \{\langle M_1 \rangle, \langle M_2 \rangle \mid \text{\(M_1\) and \(M_2\) are TMs and \(\forall X, M_1(X) = M_2(X)\)}\}$$ Is this language decidable, enumerable, or non-enumerable?

And in general, how can I tell if a language is decidable, non-decidable, semi-decidable, enumerable or non-enumerable? I am confused.

$\endgroup$
  • $\begingroup$ Not really. I have no idea where to begin. And can this be done without using reductions? $\endgroup$ – WAYA.V Feb 2 '16 at 16:06
  • 3
    $\begingroup$ While there are ways to prove that a language is undecidable without using reductions, it seems very unlikely that this is the purpose of the exercise. I suggest you start by reading a textbook that covers reductions (e.g. Sipser's "Theory of computation") $\endgroup$ – Shaull Feb 2 '16 at 16:27
  • 2
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Feb 2 '16 at 20:52
  • 2
    $\begingroup$ Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Feb 2 '16 at 20:53
1
$\begingroup$

The language TOT of all Turing machines halting on all inputs reduces to your language $L$ (take $M_2$ to be a constant machine that always halts, and ensure that both machine have the same outputs when they do halt), so $L$ is $\Pi_2$-hard. It's not difficult to write a $\Pi_2$ expression for $L$, so we conclude that $L$ is $\Pi_2$-complete. In particular, it's neither r.e. nor co-r.e.

If you don't understand these concepts, I suggest following Shaull's advice and reading a textbook on computability, and then to read some stuff on the arithmetical hierarchy.

$\endgroup$
  • 1
    $\begingroup$ Please consider not to encourage undesirable posting behaviour, especially for questions like this of which we have so many similar ones already. $\endgroup$ – Raphael Feb 2 '16 at 20:54
1
$\begingroup$

The language $E=\{\langle\,M\,\rangle\mid M \text{accepts no string}\}$ is known to be not recursively enumerable. Consider a reduction $E\le L$ defined by $$ \langle\,M\,\rangle\mapsto (\langle\,M\,\rangle,\langle\,Z\,\rangle) $$ where $Z$ is a TM that accepts no string. Then it's not hard to show that $$ \langle\,M\,\rangle\in E\Longleftrightarrow(\langle\,M\,\rangle,\langle\,Z\,\rangle)\in L $$ establishing the reduction you need.

$\endgroup$
  • 1
    $\begingroup$ Please consider not to encourage undesirable posting behaviour, especially for questions like this of which we have so many similar ones already. $\endgroup$ – Raphael Feb 2 '16 at 20:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.