For the purposes of this question, let’s focus on TMs with a unary input alphabet (say, $\{\mathtt{a}\}$) and a tape alphabet consisting of a blank symbol and the symbol $\mathtt{a}$.
Now let $M$ be such a TM that always halts. We’ll say $t_M : \mathbb{N} \to \mathbb{N}$ is the function mapping $n$ to the number of steps $M$ takes to halt on $\mathtt{N}$.
My question is what functions from naturals to naturals are realizable this way. For example:
- The function $n \mapsto n+1$ is realizable as the runtime of a TM that moves right until it sees a blank and then halts.
- More generally, $n \mapsto n+k$ is realizable for $k \ge 1$ by a TM that moves right until it sees a blank, then takes $k-1$ additional steps right before halting.
- No non-constant sublinear functions are realizable by any TM. Intuitively, TMs can’t figure out how long their inputs are if they do sublinear work, so any TM doing sublinear work would have to do a constant amount of work before halting.
- I am fairly sure that $n \mapsto \lceil \frac{3n}{2} \rceil$ is not realizable. The TM has to scan the full input to have any way of knowing what $n$ is, and at that point it can’t have left any markings behind that would let it figure out what half $n$ is.
Is this a known, studied problem? If so, what’s known about which functions are realizable?
