Prove that the language L = { <T> : T is a Turing machine that runs in polynomial time } is not Turing-recognizeable

• 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.

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

• 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}}$? Apr 22 at 15:35
• @jcora Is my updated answer clear enough? Apr 22 at 15:53
• Yes it is thanks :D Apr 22 at 17:08

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

• 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)? Apr 22 at 15:23