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

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.

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.