is L = {<M> | M is a tm such that t(n) = O(n^2) } in R? RE? CO-RE? CO-RE / RE?

L is the language of all turing machines that its computing time on all inputs is O(n^2). my thoughts is that the language is in CO-RE / RE. the language cannot be accepted because in order to make sure that there is no word W such that M halts on it after n^2 steps, you need to scan all words in the universe - infite search.... However, is the language in CO-RE ?

• " you need to scan all words in the universe - infite search.... " -- there is no reason to believe an algorithm has to work that way. You're committing an unfortunate (and popular) fallacy. – Raphael Mar 6 '18 at 12:24
• Closely related question; note also the links there. – Raphael Mar 6 '18 at 12:25

This problem is not in RE nor in coRE.

First, your intuition that it's not in RE is correct, although note that very crucially - it's just an intuition, and not a direction for a proof! However, your intuition breaks down for co-RE due to the specification being $O(n^2)$ and not $n^2$ exactly.

Let's start by proving that the language is not in coRE, by a reduction from $HALT_{TM}=\{\langle M,w \rangle: M$ halts on $w\}$.

Given input $\langle M,w \rangle$, the reduction outputs $\langle D \rangle$, where $D$ is a TM that given input $x$, ignores it and simulates $M$ on $w$. I'll leave it to you to prove correctness, but note that if $M$ halts on $w$, then it does so in constant time (i.e. independent of $x$, of course). Use this and the asymptotic notation $O(n^2)$ to conclude correctness.

Proving that the language is not in RE is a bit trickier. The reduction itself is quite standard. We reduce from $HALT_{\overline{TM}}=\{\langle M,w \rangle: M$ does not halt on $w\}$.

Given input $\langle M,w \rangle$, the reduction outputs $\langle K \rangle$, where $K$ is a TM that given input $x$, computes the length $|x|$, and then simulates the run of $M$ on $w$ for $|x|$ steps. If $M$ halts on $w$ during this time, $K$ goes into a non-halting loop. Otherwise, $K$ halts.

The correctness of this reduction is based on the observation that computing $n=|x|$ can be done in time $O(n\log n)$, and that simulating $M$ on $w$ for $n$ steps also takes $O(n\log n)$ time. This is not trivial, and follows by a clever use of a universal TM.

• I understand what you are saying and the reduction. I still find it alittle difficult to understand why the complement is not in RE. I only need to find one word W such that the computation of M on W takes longer than O(n^2) and that's it. if <M> does not belong to language L there must be such word W that the computation will not halt in O(n^2) steps but longer – Itamar Silverstein Mar 6 '18 at 11:45
• This argument works for $n^2$. But what does "longer than $O(n^2)$" mean? Suppose you have input of length 5, and the machine runs for 100 steps. Is that longer than $O(n^2)$? Maybe the runtime is just $100 n^2$? – Shaull Mar 6 '18 at 12:23