Why is the language of TMs that have some quadratic time bound undecidable?

Question

The language in question is $L = \{M : M \text{ is a Turing machine that halts in } 100n^2 + 200 \text{ time}\}$.

Attempt 1

Suppose $L$ is decidable. Let $M_1, M_2, \ldots$ be the Turing machines in $L$. Now construct a new Turing machine $M$ that works as follows:

• on input of length $n$ run $M_n$ and output the opposite answer

On the one hand, $M \in L$ since it halts in the appropriate time. On the other hand, $M \notin L$ because it is different from every machine in $L$. Therefore $L$ is undecidable.

Is this correct?

Something that bothers me: I think I am only using the fact that there are countably many Turing machines; I never used the fact that there is some TM that decides $L$.

Attempt 2

As suggested, here's a new Turing machine $M'$:

M'(M,x,1^n):
    if M is not a valid Turing machine then halt
    otherwise
        run M(x) for 100n^2+200 steps
        if it halts, then run forever
        otherwise halt

Ask oracle: does $M'(M,x, 1^n)$ halt on all inputs within $100n^2+200$ steps?

If yes, then $M$ doesn't halt on input $x$.

If no, then some input causes it to loop forever, which means $M$ halted on $x$ in a certain amount of time.

This would allow us to decide the halting problem, which we know is undecidable.

Is this correct? If so, I still think of the details are a bit fuzzy... For example, it's a bit unclear to me as to what happens with the inputs $M$ and $x$ are very large...

Answer 1

The fundamental reason for this is because your function $100n^2+200$ is $\Omega(n)$. Additionally, this result holds for any function $f\in\Omega(n)$.

Your problem is that you can't just "run $M_n$". It's possible to describe a turing machine that runs a specific machine, but to have the turing machine depend on the input requires that you actually compute the machine you're using. This is actually equivalent to the negation of what you are trying to prove, and additionally makes $M$ take longer so that it won't halt in the correct amount of time in the case that $M_n$ does even if you had an algorithm to find $M_n$.

Assuming you are using $M$ in your second attempt as a general TM rather than the one for attempt one, then the problem here is the same (except it's caused by the fact that the machine has to use some extra time to compute which step it's one rather than compute the machine it will simulate). Normally, this problem wouldn't come into play if you do $O(f(n))$ analysis because your new TM $M'$ would still run within a constant time factor of the old one, but in your problem you have to be a bit more clever.

If you know a bit of complexity theory, you can do that by using the linear speedup theorem, which basically says that given a TM which runs in at least linear time $f(n)$ you can create one with a constant factor $r>0$ as small as you'd like that runs in time $r\cdot f(n)$. The drawback is that the tape input is no longer just $0$'s and $1$'s but will also include some added symbols, but the same methods can prove this for any $f\in\Omega(n)$, so it's still a pretty neat result.

Answer 2

You can simply apply Rice's theorem, since the class of languages

$$\mathcal{S} = \{ L \mid L \; \text{is a language decided by a TM with time complexity } 100n^2 + 200 \}$$

is non-trivial.