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 ?

  • $\begingroup$ " 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. $\endgroup$ – Raphael Mar 6 '18 at 12:24
  • 1
    $\begingroup$ Closely related question; note also the links there. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – Itamar Silverstein Mar 6 '18 at 11:45
  • 1
    $\begingroup$ 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$? $\endgroup$ – Shaull Mar 6 '18 at 12:23

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.