Deciding whether a Turing machine decides a language $L$ in at most $n^2$ steps

Question

Let $L$ be a language for which there exists some turing machine deciding it in at most $n^2$ steps.

Is it decidable whether a given turing machine $M$ decides $L$ and runs in at most $n^2$ steps?

I expect the answer to always be "No", regardless of $L$, but I fail to see exactly how.

Answer 1

This problem is indeed undecidable, assuming that $n$ is not a constant but refers to the length of the machine's input.

Consider the problem $P$ of, given a Turing machine $\mathcal{M}$, to decide if it runs in at most $|x|$ steps on every input $x$. Problem $P$ is undecidable.

For any constants $c,c' > 0$, let $Q_{L,c,c'}$ be the (promise) problem of:

• given a Turing machine $\mathcal{M}$ such that, for every $x$, either $\mathcal{M}$ halts on $x$ in at most $c\cdot |x|^2 + c'$ steps, or does not halt,
• decide if it runs in at most $c\cdot |x|^2 + c'$ steps on every input $x$ and decides $L$.

Claim: There exists $c,c'>0$ such that problem $P$ reduces to problem $Q_{L,c,c'}$.

Proof: Let $\mathcal{N_L}$ be the Turing machine which decides $L$ in at most $n^2$ steps. The reduction maps $\mathcal{M}$ to the machine $\mathcal{M}'$ which, on input $x$:

• first, it simulates $\mathcal{M}$ on input $x$ for $|x|$ steps;
• if the machine didn't stop, it loops forever;
• otherwise, it simulates $\mathcal{N}_L$ on $x$ for $|x|^2$ steps, and returns its output.

Then $\mathcal{M}$ runs in at most $|x|$ steps for every input $x$ if and only if $\mathcal{M}'$ decides $L$ and runs in at most $c\cdot |x|^2 + c'$ steps for every input $x$ for some constants $c,c'$.

Then, using the linear speadup theorem, you can show that the following problem is undecidable: given $\mathcal{M}$, does $\mathcal{M}$ decide $L$ and halts in at most
\begin{cases} |x|^2 \text{ steps} & \text{on every input $x$ of size at least $n_0$}, \\ k \text{ steps} & \text{on every input $x$ of size at most $k$}, \\ \end{cases} for some constant $n_0 \in \mathbb{N}$. This problem differs from yours only on finitely many inputs, and so your problem is undecidable.