3
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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}$.

Improve this answer
$\endgroup$
1
  • $\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$ Commented Apr 2, 2016 at 12:42

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.