I already know, that the language $$L_0 = \{m \mid \text{the Turing machine $m$ does not stop on an empty tape}\}$$ is not decidable. If I want to know, if $$EQ = \{\langle m, n \rangle \mid L(m) = L(n)\}$$ is decidable I can reduce $L_0$ to $EQ$. Because $(L_1 \setminus L_2) \cup (L_2 \setminus L_1) = \emptyset$ iff $L_1 = L_2$, $EQ$ is also not decidable.

But what happens if a limit is added? For example the language $$EQ_{\lim} = \{\langle m, n \rangle \mid \exists x_0 \in \mathbb{N}\colon \forall x > x_0\colon m(x) = n(x)\}.$$

Is it (semi-)decidable? I also try to reduce from the halting problem (more specifically the inverse of the halting problem to proof also semi-decidability), but without success.


You can still reduce $L_0$ to $EQ_{\lim}$. Given a Turing machine $m$, construct a Turing machine $m'$ which deletes its input and then transfers control to $m$, and let $n'$ denote a (fixed) Turing machine which halts on no input. Then $m \in L_0$ iff $\langle m',n' \rangle \in EQ_{\lim}$.

| cite | improve this answer | |
  • $\begingroup$ Thank you, I thought a little bit to complicated, but this should indeed work. And also thanks for formatting my question. Now I know how to do this for my next question (respectively answer). $\endgroup$ – Querenker Apr 2 '16 at 12:42

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.