Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?

Question

I expect the answer is no, but I could not actually construct a counterexample. The difference is that in $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$, we might not be able to pick an $O(n^{2+ε})$ algorithm uniformly in $ε$.

By a dovetailing argument (for example, see this question), if there is a c.e. set of Turing machines $M_i$ deciding a language $L$ such that $∀ε>0 ∃M_i ∈ O(n^{2+ε})$, then $L$ is in $\mathrm{DTIME}(n^{2+o(1)})$.

Given a Turing machine, whether the machine runs in time $n^{2+o(1)}$ is $Π^0_3$-complete. Whether a language (given a code for a machine recognizing it) is in $\mathrm{DTIME}(n^{2+o(1)})$ is $Σ^0_4$ (and $Π^0_3$-hard); whether a language is in $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$ is $Π^0_3$-complete. If we can prove $Σ^0_4$ completeness (or just $Σ^0_3$-hardness) of $\mathrm{DTIME}(n^{2+o(1)})$, that would solve the problem, but I am not sure how to do that.

The problem would also be solved if we find a sequence of languages $L_i$ such that
* $L_i$ has a natural $O(n^{2+1/i})$ decision algorithm (uniformly in $i$).
* Each $L_i$ is finite.
* Not only is the size of $L_i$ undecidable, but an algorithm cannot rule out $w∈L_i$ much faster than $O(n^{2+1/i})$ (for worst case $w$), except for finitely many $i$ (dependent on the algorithm).

I am also curious whether there any notable/interesting examples (for $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) \setminus \mathrm{DTIME}(n^{2+o(1)})$ or an analogous relation).

Answer 1

Here is a counterexample, i.e. a language with an $O(n^{2+ε})$ algorithm (using multitape Turing machines) for every $ε>0$, but not uniformly in $ε$:
Accept $0^k 1^m$ iff $k>0$ and the $k$th Turing machine halts in less than $m^{2+1/k}$ steps on the empty input. Other strings are rejected.

For every $ε$, we get an $O(n^{2+ε})$ algorithm by hardcoding all sufficiently small nonhalting machines, and simulating the rest.

Now, consider a Turing machine $M$ deciding the language.

Let $M'$ (on the empty input) be an efficient implementation of the following:
for $n$ in 1,2,4,8,...:
     use $M$ to decide whether $M'$ halts in $<n^{2+1/M'}$ steps.
     halt iff $M$ says that we do not halt but we can still halt in $<n^{2+1/M'}$ steps.

By correctness of $M$, $M'$ does not halt, but $M$ takes $Ω(n^{2+1/M'})$-steps on input $0^{M'} 1^{n-M'}$ for infinitely many $n$. (If $M$ is too fast, then $M'$ would contradict $M$. The $Ω(n^{2+1/M'})$ bound depends on $M'$ simulating $M$ in linear time and otherwise being efficient.)