Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

Question

The question:

Is there an $f$ in $\omega(n) \cap o(n \log n)$ that is time-constructible on a 1-tape DTM?

I.e. $f$ such that $\lim_{n\to\infty} \frac{n}{f(n)} = \lim_{n\to\infty} \frac{f(n)}{n \log n} = 0$?

Discussion:

Consider 1-tape deterministic TM's that take inputs of the form $1^n$.

It is easy to design such a TM with running time $\Theta(n)$: just scan the input once.

It is easy to design such a TM with running time $\Theta(n\log n)$: make repeated passes over the tape, each pass replacing every other 1 with a 0, and halting if the pass finds no 1's.

The question is, is there a TM whose asymptotic running time $t(n)$ is strictly between these two? That is, $t(n)$ is $\omega(n)$ but $o(n\log n)$? Eg. $t(n) = \Theta(n\log \log n)$?

Answer (added in an edit):

The answer (posted below) is no. The proof is an adaption of the proof of a closely related result: that any 1-tape TM that runs in $o(n\log n)$ time accepts a regular language. The proof uses a crossing-sequence argument.

---

[EDIT: This result was observed in Corollary 4.6 of the following paper:

Gajser, David, Verifying time complexity of Turing machines, Theor. Comput. Sci. 600, 86-97 (2015). ZBL1329.68111.]

---

Context:

This question comes up in trying to answer another question, namely, the complexity of deciding (for fixed $f$ and $g$ with $g(n) \not\in O(f(n)$) whether a given 1-tape TM $M$ that is promised to run in time $O(g(n))$ in fact runs in time $O(f(n))$). Variants of this are considered here, here, and here. In the cases where $g(n) = O(f(n)\log n)$, or when $f(n) = \Theta(n)$, for 1-tape TM's this logarithmic gap presents an apparent obstacle to proving undecidability via diagonalization.

This answer claims "most functions that we deal with in practice turn out to be time constructible." On the other hand, it is not hard to see that there is no time-constructible function in $\omega(1) \cap o(n)$, because, if a TM doesn't take more than $n_0$ steps given input $1^{n_0}$, then it doesn't look past the final input cell $n_0$, so, given any larger input, the TM also doesn't look past tape cell $n_0$, and its behavior must be the same as on input $1^{n_0}$. So its run time never exceeds $O(\max_{n\le n_0} t(n)) = O(1)$ (where $t(n)$ is the run time on inputs of size $n$).

The Gap Theorem says that, for any function $f$ with $f(n)\ge n$, there is a $g$ such that $\textsf{DTIME}(g(n)) = \textsf{DTIME}(f(g(n))$, although if $g$ is required to be time constructible, the Time Hierarchy Theorem says that $\textsf{DTIME}(o(g(n))) \ne \textsf{DTIME}(g(n)\log n)$.

As Emil points out, it is easy to show that, e.g., $n\log\log n$ is time-constructible using multi-tape TMs, which as Chandra points out are usually the basis for definitions of space/time complexity, especially for low complexity classes. Here the question is specifically about 1-tape TM's.

Answer 1

[EDIT: This result was already observed in Corollary 4.6 of the following paper:

Gajser, David, Verifying time complexity of Turing machines, Theor. Comput. Sci. 600, 86-97 (2015). ZBL1329.68111.]

---

---

Theorem 3.3 in [1] shows that the language of any 1-tape $o(n\log n)$-time DTM is regular. Adapting their proof gives the following negative answer to my question. (I should note that [1] in turn adapted the proof of Theorem 3 of [2].)

Let $M$ be any 1-tape DTM. Let $f(n)$ be its worst-case run time on inputs of length $n$.

Lemma 1. If $f(n) = o(n\log n)$, then $f(n) = O(n)$.

Proof sketch. Assume that $f(n) = o(n\log n)$. Apply the proof of Theorem 3.3 of [1] to $M$. (Just to use the proof in [1], assume WLOG that $L(M) = \Sigma^*$; if not make it so by replacing every undefined (i.e. halting) transition in $M$ by a transition to an accept state.)

For some constant $c_M$ depending only on $M$, that proof shows that

The length of any crossing sequence of $M$ for any input $x$ with $|x|\ge 2$ is at most $c_M$.

This immediately implies that, on any input of length $n$, the number of steps that $M$ takes with its tape head over the first $n-1$ tape cells is $O(c_M n) = O(n)$. To finish, we observe that the number of steps that $M$ takes with its tape head over the remaining cells is $O(1)$.

Indeed, let $\mathcal X$ be the set of possible crossing sequences that can occur between cells $n-1$ and $n$ in any execution of $M$ on any input. Let $\Sigma$ be $M$'s tape alphabet. Note that $|X|$ and $|\Sigma|$ are both $O(1)$, as $M$ is fixed and every sequence in $X$ has length at most $c_M$.

For $(X, a) \in \mathcal X \times \Sigma$, let $T(X, a)$ be the the time spent by $M$ over tape cells $n, n+1, n+2, \ldots$ given that the crossing sequence between tape cells $n-1$ and $n$ is $X$, and tape cell $n$ initially holds $a$ (that is, $x_n=a$). Note that the behavior of $M$ beyond tape cell $n$ is fully determined by this $X$ and $a$, and each $T(X, a)$ is finite because $M$ always terminates.

Then, on any input, the time spent by $M$ over tape cells $n+1, n+2, \ldots$ is at most $\max_{(X, a) \in \mathcal X \times \Sigma } T(X, a)$. This is $O(1)$, as the maximum is over $O(1)$ values, each of which is $O(1)$. $~~~~\Box$

Remark. I wonder whether the proof (in particular, the proof of [1]) can be made to work assuming only $t(n) \ne O(n\log n)$.

---

[1] Kobayashi, Kojiro, On the structure of one-tape nondeterministic Turing machine time hierarchy, Theor. Comput. Sci. 40, 175-193 (1985). ZBL0603.68047.

[2] Hennie, F. C., One-tape, off-line Turing machine computations, Inform. and Control 8 (1965), 553-578 (1966); Russian translation in Probl. Mat. Logiki. Slozn. Algoritm. Klassy Vychisl. Funkcii, 223-248 (1970). ZBL0231.02048.