1
$\begingroup$
  • By "$T$ runs in polynomial time", I mean that $T$ halts for every input of length $n$ in $O(n^k)$ steps for some $k$.
  • By Turing-recognizable, I mean that there exists a Turing machine that halts in the accept state iff the input $w = \langle T\rangle \in L$.

I'm not really sure how to approach this problem. It seems like I should reduce from $A_{\text{TM}}$ (or $HALT_{\text{TM}}$ depending on convenience). (Edit: wrong, both of these are Turing-recognizable.)

I also tried to directly do a running time variant of the diagonalization proof that $A_{\text{TM}}$ is undecidable. I began by assuming that $L$ is Turing-recognizable by some $M$. Then we can create a TM $D$ that reads $\langle T\rangle$ and simulates $M$ on it. Towards contradiction we then make $D$ run in a loop (or do $2^{|\langle T\rangle|}$ additional steps) if $\langle T\rangle \in L$, or halt immediately otherwise. But this doesn't work as we don't know the complexity of $M$. More precisely I can get a contradiction only if $\langle M\rangle \in L$.

Rice's theorem doesn't seem to be of much help either. If I could prove that (1) $L$ is undecidable and (2) $L^C$ is recognizable, then I would obtain $L$ is unrecognizable. But Rice doesn't help with (1) (because for $L(T_1) = L(T_2)$ says nothing about the running times), and (2) seems to be straight-up false.

$\endgroup$

2 Answers 2

1
$\begingroup$

The simplest example of a non-Turing-recognizable language is the complement of $A_{\text{TM}}$, $$\overline{A_\text{TM}}=\{\langle M,w\rangle\mid M\text{ is a TM and }M\text{ does not accepts }w\}.$$

Let us reduce $\overline{A_\text{TM}}$ to $L$.


Given a TM $M$ and a string $w$, construct the following TM.

$M'$= "On input $s$:

  1. Simulate $M$ on input $w$ for $|s|$ steps using less than $|s|^3+159759$ steps.
  2. If the simulated $M$ has accepted, possibly before $|s|$ steps, run forever. Else halt."

Here $3$ and $159759$ just mean some large-enough numbers independent of $M$ so that the simulation for $|s|$ steps can be done.

Let us verify that $\langle M,w\rangle\in \overline{A_\text{TM}}$ iff $\langle M'\rangle\in L$.

  • If $\langle M,w\rangle\in \overline{A_\text{TM}}$, i.e., $M$ does not accept $w$, then on input $s$, $M'$ will always halt in $|s|^3+159759$ steps. Hence $\langle M'\rangle\in L$.
  • If $\langle M,w\rangle\notin \overline{A_\text{TM}}$, i.e., $M$ accepts $w$, then for input $s$ that is long enough, the simulated $M$ will have accepted after step 1. Hence $M'$ will run forever on those input. Hence $\langle M'\rangle\notin L$.

Since $\overline{A_{\text{TM}}}$ is not Turing recognizable, neither is $L$.

$\endgroup$
3
  • $\begingroup$ Can you elaborate a bit on why is it sufficient to only simulate $|s|$ steps of $M$? What if $M$ would've accepted $s$ in $|s|+1$ steps? Also, didn't you mean $\langle M, s \rangle \in \overline{A_\text{TM}}$? $\endgroup$
    – jcora
    Apr 22, 2023 at 15:35
  • 1
    $\begingroup$ @jcora Is my updated answer clear enough? $\endgroup$
    – John L.
    Apr 22, 2023 at 15:53
  • $\begingroup$ Yes it is thanks :D $\endgroup$
    – jcora
    Apr 22, 2023 at 17:08
0
$\begingroup$

Suppose $L$ is decidable with a Turing machine $T$. Now we will show $\sim HALT\leq L$.

Create a Turing machine $\mathcal{M}$ from $\langle M,x\rangle$ which on any input runs $M$ on $x$ for $|x|$ many steps. If $M$ halts within $|x|$ many steps then $\mathcal{M}$ goes on a loop and halts after $2^{|x|^c}$ many steps for some constant $c>1$ and if $M$ does not halt within that many steps $\mathcal{M}$ halts.

Now it is easy to see that $\mathcal{M}$ is a polynomial time Turing Machine if $M$ halts within $|x|$ steps. Therefore $$\langle M,x\rangle\in\ \sim HALT\iff \mathcal{M}\in L$$Since $T$ can decide $L$, $T$ can decide if $\mathcal{M}$ is in $L$ or not, i.e. $T$ can decide the set $\sim HALT$. Which is not decidable. Hence contradiction. Hence $L$ is not decidable

$\endgroup$
1
  • $\begingroup$ Would you mind defining what $\sim HALT$ is? Also, the problem asks about Turing-recognizability of $L$, not its decidability. Would you mind editing your answer for completeness in that respect (showing that $L$ is not Turing-recognizable)? $\endgroup$
    – jcora
    Apr 22, 2023 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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