<p><em>[EDIT: This result was already observed in Corollary 4.6 of the following paper:</em></p>
<p><em>Gajser, David</em>, <a href="https://doi.org/10.1016/j.tcs.2015.07.028" rel="nofollow noreferrer"><strong>Verifying time complexity of Turing machines</strong></a>, Theor. Comput. Sci. 600, 86-97 (2015). <a href="https://zbmath.org/?q=an:1329.68111" rel="nofollow noreferrer">ZBL1329.68111</a>.]</p>
<hr />
<hr />
<p>Theorem 3.3 in [1] shows that the language of any 1-tape <span class="math-container">$o(n\log n)$</span>-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].)</p>
<p>Let <span class="math-container">$M$</span> be any 1-tape DTM.  Let <span class="math-container">$f(n)$</span> be its worst-case run time on inputs of length <span class="math-container">$n$</span>.</p>
<p><strong>Lemma 1.</strong> <em>If <span class="math-container">$f(n) = o(n\log n)$</span>, then <span class="math-container">$f(n) = O(n)$</span>.</em></p>
<p><em>Proof sketch.</em>
Assume that <span class="math-container">$f(n) = o(n\log n)$</span>.
Apply the proof of Theorem 3.3 of [1] to <span class="math-container">$M$</span>.
(Just to use the proof in [1],
assume WLOG that <span class="math-container">$L(M) = \Sigma^*$</span>;
if not make it so by replacing
every undefined (i.e. halting)
transition in <span class="math-container">$M$</span> by a transition to
an accept state.)</p>
<p>For some constant <span class="math-container">$c_M$</span> depending only on <span class="math-container">$M$</span>,
that proof shows that</p>
<blockquote>
<p>The length of any <a href="https://en.wikipedia.org/wiki/Crossing_sequence_(Turing_machines)" rel="nofollow noreferrer">crossing sequence</a> of <span class="math-container">$M$</span> for any input <span class="math-container">$x$</span> with <span class="math-container">$|x|\ge 2$</span> is at most <span class="math-container">$c_M$</span>.</p>
</blockquote>
<p>This immediately implies that, on any input of length <span class="math-container">$n$</span>,
the number of steps that <span class="math-container">$M$</span> takes
with its tape head over the first <span class="math-container">$n-1$</span> tape cells
is <span class="math-container">$O(c_M n) = O(n)$</span>.
To finish, we observe that the number of steps that <span class="math-container">$M$</span> takes
with its tape head over the remaining cells is <span class="math-container">$O(1)$</span>.</p>
<p>Indeed, let <span class="math-container">$\mathcal X$</span>
be the set of possible crossing sequences
that can occur between cells <span class="math-container">$n-1$</span> and <span class="math-container">$n$</span>
in any execution of <span class="math-container">$M$</span> on any input.
Let <span class="math-container">$\Sigma$</span> be <span class="math-container">$M$</span>'s tape alphabet.
Note that <span class="math-container">$|X|$</span> and <span class="math-container">$|\Sigma|$</span> are both <span class="math-container">$O(1)$</span>, as <span class="math-container">$M$</span> is fixed
and every sequence in <span class="math-container">$X$</span> has length at most <span class="math-container">$c_M$</span>.</p>
<p>For <span class="math-container">$(X, a) \in \mathcal X \times \Sigma$</span>,
let <span class="math-container">$T(X, a)$</span>
be the the time spent by <span class="math-container">$M$</span>
over tape cells <span class="math-container">$n, n+1, n+2, \ldots$</span>
given that
the crossing sequence between tape cells <span class="math-container">$n-1$</span> and <span class="math-container">$n$</span> is <span class="math-container">$X$</span>,
and tape cell <span class="math-container">$n$</span> initially holds <span class="math-container">$a$</span> (that is, <span class="math-container">$x_n=a$</span>).
Note that the behavior of <span class="math-container">$M$</span> beyond tape cell <span class="math-container">$n$</span>
is fully determined by this <span class="math-container">$X$</span> and <span class="math-container">$a$</span>,
and each <span class="math-container">$T(X, a)$</span> is finite because <span class="math-container">$M$</span> always terminates.</p>
<p>Then, on any input, the time spent by <span class="math-container">$M$</span>
over tape cells <span class="math-container">$n+1, n+2, \ldots$</span>
is at most
<span class="math-container">$\max_{(X, a) \in \mathcal X \times \Sigma } T(X, a)$</span>.
This is <span class="math-container">$O(1)$</span>, as the maximum
is over <span class="math-container">$O(1)$</span> values, each of which is <span class="math-container">$O(1)$</span>.
<span class="math-container">$~~~~\Box$</span></p>
<p><strong>Remark.</strong> I wonder whether the proof
(in particular, the proof of [1])
can be made to work assuming only <span class="math-container">$t(n) \ne O(n\log n)$</span>.</p>
<hr />
<p>[1] <em>Kobayashi, Kojiro</em>, <a href="https://doi.org/10.1016/0304-3975(85)90165-3" rel="nofollow noreferrer"><strong>On the structure of one-tape nondeterministic Turing machine time hierarchy</strong></a>, Theor. Comput. Sci. 40, 175-193 (1985). <a href="https://zbmath.org/?q=an:0603.68047" rel="nofollow noreferrer">ZBL0603.68047</a>.</p>
<p>[2] <em>Hennie, F. C.</em>, <a href="https://doi.org/10.1016/S0019-9958(65)90399-2" rel="nofollow noreferrer"><strong>One-tape, off-line Turing machine computations</strong></a>, Inform. and Control 8 (1965), 553-578 (1966); Russian translation in Probl. Mat. Logiki. Slozn. Algoritm. Klassy Vychisl. Funkcii, 223-248 (1970). <a href="https://zbmath.org/?q=an:0231.02048" rel="nofollow noreferrer">ZBL0231.02048</a>.</p>

CC BY-SA 4.0
2024-03-15T17:43:22.013Z
I'm not sure I understand what you mean by "otherwise just make every state an accepting state". Then the machine halts in time $t(n)=1$ on every input, doesn't it? And why do you actually need the assumption $L(M)=\Sigma^*$, anyway?
Emil Jeřábek
CC BY-SA 4.0
2024-03-15T17:48:56.550Z
I don't see how "$M$ always terminates" should imply that $T(X,a)$ is finite for all $X$ and $a$. Surely it is possible that some pair $(X,a)$ cannot occur in any run of $M$? But anyway, this should not matter: simply take the maximum over those $T(X,a)$ that are finite. The infinite ones are irrelevant, as they cannot occur in the run of $M$ on any input $x$ (which is assumed to terminate, in $o(n\log n)$ steps).
Emil Jeřábek
CC BY-SA 4.0
2024-03-15T18:07:30.107Z
Yes, good catch.  I had in mind that $\mathcal X$ should be the set of crossing sequences that can actually occur there for $M$.
Neal Young
CC BY-SA 4.0
2024-03-15T18:12:49.950Z
@EmilJeřábek, re "make every state an accepting state", in the definition of TM that I am using (see e.g. Wikipedia) the TM halts when (and only when) the transition table of the TM doesn't have a suitable entry, and then (and only then) the input is accepted if the current state is an accept state.  I want every input to be in the language because the proof of Theorem 3.3 in [1] only considers inputs in $L(M)$ (although that assumption is not really used in the proof).
Neal Young
CC BY-SA 4.0
2024-03-15T19:43:52.790Z
That’s a rather unusual convention. Usual definitions make the machine halt immediately after it enters an accepting (or rejecting, in formalisms that have them) state. The definition on Wikipedia, which ostensibly comes from Hopcroft and Ullman (I haven’t checked), requires exactly that: you must have missed the indicated domain of $\delta$, and the accompanying footnote. The definition in Sipser also works this way, though it differs in other details.
Emil Jeřábek
CC BY-SA 4.0
2024-03-15T20:17:03.703Z
Indeed I did miss that.  I assumed that they were defining halting solely by not having a valid transition, and acceptance by halting _and_ being in an "accept" state.  Thanks for pointing that out, I'll fix it.
Neal Young
CC BY-SA 4.0
2024-03-15T17:11:12.303Z
2024-03-20T00:38:34.387Z
2024-03-20T00:38:34.387Z
Neal Young
<h4>The question:</h4>
<p>Is there an <span class="math-container">$f$</span> in
<span class="math-container">$\omega(n) \cap o(n \log n)$</span>
that is <a href="https://en.wikipedia.org/wiki/Constructible_function#Time-constructible_definitions" rel="nofollow noreferrer">time-constructible</a> on a 1-tape DTM?</p>
<p>I.e. <span class="math-container">$f$</span> such that <span class="math-container">$\lim_{n\to\infty} \frac{n}{f(n)} = \lim_{n\to\infty} \frac{f(n)}{n \log n} = 0$</span>?</p>
<h4>Discussion:</h4>
<p>Consider 1-tape deterministic TM's that take inputs of the form <span class="math-container">$1^n$</span>.</p>
<p>It is easy to design such a TM with running time <span class="math-container">$\Theta(n)$</span>:
just scan the input once.</p>
<p>It is easy to design such a TM with running time <span class="math-container">$\Theta(n\log n)$</span>:
make repeated passes over the tape,
each pass replacing every other 1 with a 0,
and halting if the pass finds no 1's.</p>
<p>The question is, is there a TM whose asymptotic running time
<span class="math-container">$t(n)$</span> is strictly between these two?
That is, <span class="math-container">$t(n)$</span> is <span class="math-container">$\omega(n)$</span> but <span class="math-container">$o(n\log n)$</span>?
Eg. <span class="math-container">$t(n) = \Theta(n\log \log n)$</span>?</p>
<h3>Answer (added in an edit):</h3>
<p>The answer (posted below) is no.
The proof is an adaption of the proof of <a href="https://doi.org/10.1016/j.tcs.2009.08.031" rel="nofollow noreferrer">a closely related result</a>:
that any 1-tape TM that runs in <span class="math-container">$o(n\log n)$</span> time accepts a regular language.  The proof uses a crossing-sequence argument.</p>
<hr />
<p><em>[EDIT: This result was observed in Corollary 4.6 of the following paper:</em></p>
<p><em>Gajser, David</em>, <a href="https://doi.org/10.1016/j.tcs.2015.07.028" rel="nofollow noreferrer"><strong>Verifying time complexity of Turing machines</strong></a>, Theor. Comput. Sci. 600, 86-97 (2015). <a href="https://zbmath.org/?q=an:1329.68111" rel="nofollow noreferrer">ZBL1329.68111</a>.]</p>
<hr />
<h3>Context:</h3>
<p>This question comes up in trying to answer another question,
namely, the complexity of deciding (for fixed <span class="math-container">$f$</span> and <span class="math-container">$g$</span> with <span class="math-container">$g(n) \not\in O(f(n)$</span>) whether a given 1-tape TM <span class="math-container">$M$</span> that is promised to run in time <span class="math-container">$O(g(n))$</span> in fact runs in time <span class="math-container">$O(f(n))$</span>).
Variants of this are considered <a href="https://cstheory.stackexchange.com/q/5004/8237">here</a>, <a href="https://cs.stackexchange.com/questions/12518/are-runtime-bounds-decidable-for-anything-nontrivial">here</a>, and <a href="https://mathoverflow.net/q/28056">here</a>.
In the cases where <span class="math-container">$g(n) = O(f(n)\log n)$</span>,
or when <span class="math-container">$f(n) = \Theta(n)$</span>,
for 1-tape TM's this logarithmic gap presents an apparent obstacle to proving undecidability via diagonalization.</p>
<p><a href="https://math.stackexchange.com/a/51084/48535">This answer</a> claims &quot;<em>most functions that we deal with in practice turn out to be time constructible.&quot;</em>
On the other hand, it is not hard to see that there is no time-constructible function
in <span class="math-container">$\omega(1) \cap o(n)$</span>, because, if a TM doesn't take more than <span class="math-container">$n_0$</span> steps given input <span class="math-container">$1^{n_0}$</span>, then it doesn't look past the final input cell <span class="math-container">$n_0$</span>, so, given any larger input, the TM also doesn't look past tape cell <span class="math-container">$n_0$</span>, and its behavior must be the same as on input <span class="math-container">$1^{n_0}$</span>.  So its run time never exceeds <span class="math-container">$O(\max_{n\le n_0} t(n)) = O(1)$</span> (where <span class="math-container">$t(n)$</span> is the run time on inputs of size <span class="math-container">$n$</span>).</p>
<p>The <a href="https://en.wikipedia.org/wiki/Gap_theorem#Gap_theorem" rel="nofollow noreferrer">Gap Theorem</a> says that, for any function <span class="math-container">$f$</span> with <span class="math-container">$f(n)\ge n$</span>, there is a <span class="math-container">$g$</span> such that <span class="math-container">$\textsf{DTIME}(g(n)) = \textsf{DTIME}(f(g(n))$</span>, although if <span class="math-container">$g$</span> is required to be <em>time constructible</em>, the <a href="https://en.wikipedia.org/wiki/Time_hierarchy_theorem" rel="nofollow noreferrer">Time Hierarchy Theorem</a> says that
<span class="math-container">$\textsf{DTIME}(o(g(n))) \ne \textsf{DTIME}(g(n)\log n)$</span>.</p>
<p>As Emil points out, it is easy to show that, e.g., <span class="math-container">$n\log\log n$</span> is time-constructible using <em>multi-tape</em> TMs, which as Chandra points out are usually the basis for definitions of space/time complexity, <a href="https://en.wikipedia.org/wiki/DTIME#Machine_model" rel="nofollow noreferrer">especially</a> for low complexity classes.  Here the question is specifically about 1-tape TM's.</p>

CC BY-SA 4.0
2024-03-14T22:05:41.350Z
Just like cutting in half gets you a log factor, cutting down to sqrt should get you a log log factor.
Joshua Grochow
CC BY-SA 4.0
2024-03-15T01:16:52.380Z
But how to cut down to sqrt in one (linear time) pass, @JoshuaGrochow?
Neal Young
CC BY-SA 4.0
2024-03-15T01:46:27.507Z
Yeah I was thinking about that - that's why I wrote it as a comment instead of an answer ;).
Joshua Grochow
CC BY-SA 4.0
2024-03-15T02:14:47.910Z
Don't we normally use multi-tape TMs when defining time/space complexity? Do you specifically want to restrict attention to 1-tape TMs?
Chandra Chekuri
CC BY-SA 4.0
2024-03-15T07:53:07.843Z
Probably not important, but is the condition $f \in \omega(n)$ or $f \not \in O(n)$?
mathworker21
CC BY-SA 4.0
2024-03-15T08:30:07.040Z
On a 2-tape TM, it's straightforward: using a binary counter, compute the binary representation of $n$ in one $O(n)$ pass over the input, compute the binary representation of $f(n)$ in time, say, $n^\epsilon$ for $\epsilon<1$ (any remotely sensible function you'd want to use as a time bound should be computable in subexponential time), and convert it back to unary in time $O(f(n))$.
Emil Jeřábek
CC BY-SA 4.0
2024-03-15T13:16:38.213Z
@ChandraChekuri - I do specifically have in mind 1-tape TM's.  For multi-tape TM's I agree there is no issue, and I agree that it seems to be customary to use multi-tape TM's for defining time/space complexity , e.g. [per Wikipedia](https://en.wikipedia.org/wiki/DTIME#Machine_model) DTIME is usually defined w.r.t. multi-tape TMs.
Neal Young
CC BY-SA 4.0
2024-03-15T13:23:50.297Z
@mathworker21, either would be okay.  The strongest positive result would have $f\in \omega(n)$, the strongest negative result would show there is no $f$ such that $f\not\in O(n)$.
Neal Young
CC BY-SA 4.0
2024-03-15T17:13:10.817Z
@EmilJeřábek, yes, I just finished it. :-)
Neal Young
<turing-machines><undecidability><time-hierarchy>
Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?
Neal Young
# Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

(Asked by: username_0 on 2024-03-14)

#### The question:

Is there an $f$ in
$\omega(n) \cap o(n \log n)$
that is [time-constructible](https://en.wikipedia.org/wiki/Constructible_function#Time-constructible_definitions) 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](https://doi.org/10.1016/j.tcs.2009.08.031):
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**](https://doi.org/10.1016/j.tcs.2015.07.028), Theor. Comput. Sci. 600, 86-97 (2015). [ZBL1329.68111](https://zbmath.org/?q=an:1329.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](https://cstheory.stackexchange.com/q/5004/8237), [here](https://cs.stackexchange.com/questions/12518/are-runtime-bounds-decidable-for-anything-nontrivial), and [here](https://mathoverflow.net/q/28056).
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](https://math.stackexchange.com/a/51084/48535) 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](https://en.wikipedia.org/wiki/Gap_theorem#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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/DTIME#Machine_model) for low complexity classes. Here the question is specifically about 1-tape TM's.

**Tags:** turing-machines, undecidability, time-hierarchy

> **Comments:**
> **username_1**: Just like cutting in half gets you a log factor, cutting down to sqrt should get you a log log factor.  
> **username_0**: But how to cut down to sqrt in one (linear time) pass, @JoshuaGrochow?  
> **username_1**: Yeah I was thinking about that - that's why I wrote it as a comment instead of an answer ;).  
> **username_2**: Don't we normally use multi-tape TMs when defining time/space complexity? Do you specifically want to restrict attention to 1-tape TMs?  
> **username_3**: Probably not important, but is the condition $f \in \omega(n)$ or $f \not \in O(n)$?  
> **username_4**: On a 2-tape TM, it's straightforward: using a binary counter, compute the binary representation of $n$ in one $O(n)$ pass over the input, compute the binary representation of $f(n)$ in time, say, $n^\epsilon$ for $\epsilon<1$ (any remotely sensible function you'd want to use as a time bound should be computable in subexponential time), and convert it back to unary in time $O(f(n))$.  
> **username_0**: @ChandraChekuri - I do specifically have in mind 1-tape TM's.  For multi-tape TM's I agree there is no issue, and I agree that it seems to be customary to use multi-tape TM's for defining time/space complexity , e.g. [per Wikipedia](https://en.wikipedia.org/wiki/DTIME#Machine_model) DTIME is usually defined w.r.t. multi-tape TMs.  
> **username_0**: @username_3, either would be okay.  The strongest positive result would have $f\in \omega(n)$, the strongest negative result would show there is no $f$ such that $f\not\in O(n)$.  
> **username_0**: @EmilJeřábek, yes, I just finished it. :-)  

---

## 1 answers

### Answer by username_0 on 2024-03-15. Score: 5 | Accepted answer

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

*Gajser, David*, [**Verifying time complexity of Turing machines**](https://doi.org/10.1016/j.tcs.2015.07.028), Theor. Comput. Sci. 600, 86-97 (2015). [ZBL1329.68111](https://zbmath.org/?q=an:1329.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](https://en.wikipedia.org/wiki/Crossing_sequence_(Turing_machines)) 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**](https://doi.org/10.1016/0304-3975(85)90165-3), Theor. Comput. Sci. 40, 175-193 (1985). [ZBL0603.68047](https://zbmath.org/?q=an:0603.68047).

[2] *Hennie, F. C.*, [**One-tape, off-line Turing machine computations**](https://doi.org/10.1016/S0019-9958(65)90399-2), Inform. and Control 8 (1965), 553-578 (1966); Russian translation in Probl. Mat. Logiki. Slozn. Algoritm. Klassy Vychisl. Funkcii, 223-248 (1970). [ZBL0231.02048](https://zbmath.org/?q=an:0231.02048).

> **Comments:**
> **username_4**: I'm not sure I understand what you mean by "otherwise just make every state an accepting state". Then the machine halts in time $t(n)=1$ on every input, doesn't it? And why do you actually need the assumption $L(M)=\Sigma^*$, anyway?  
> **username_4**: I don't see how "$M$ always terminates" should imply that $T(X,a)$ is finite for all $X$ and $a$. Surely it is possible that some pair $(X,a)$ cannot occur in any run of $M$? But anyway, this should not matter: simply take the maximum over those $T(X,a)$ that are finite. The infinite ones are irrelevant, as they cannot occur in the run of $M$ on any input $x$ (which is assumed to terminate, in $o(n\log n)$ steps).  
> **username_0**: Yes, good catch.  I had in mind that $\mathcal X$ should be the set of crossing sequences that can actually occur there for $M$.  
> **username_0**: @EmilJeřábek, re "make every state an accepting state", in the definition of TM that I am using (see e.g. Wikipedia) the TM halts when (and only when) the transition table of the TM doesn't have a suitable entry, and then (and only then) the input is accepted if the current state is an accept state.  I want every input to be in the language because the proof of Theorem 3.3 in [1] only considers inputs in $L(M)$ (although that assumption is not really used in the proof).  
> **username_4**: That’s a rather unusual convention. Usual definitions make the machine halt immediately after it enters an accepting (or rejecting, in formalisms that have them) state. The definition on Wikipedia, which ostensibly comes from Hopcroft and Ullman (I haven’t checked), requires exactly that: you must have missed the indicated domain of $\delta$, and the accompanying footnote. The definition in Sipser also works this way, though it differs in other details.  
> **username_0**: Indeed I did miss that.  I assumed that they were defining halting solely by not having a valid transition, and acceptance by halting _and_ being in an "accept" state.  Thanks for pointing that out, I'll fix it.  

---

