We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ steps and for each $n$ there exists some input of length $n$ on which $M$ makes exacltly $f(n)$ steps.We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is fully time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes exactly $f(n)$ steps.Q1: Does there exist a function which is time-construcible and not fully time-constructible?The answer is yes (see this answer), if $EXP-TIME \neq NEXP-TIME$. Can the condition for yes be strengthened to $P\neq NP$? Can yes be proven?Q2: Does the class of (fully) time-constuctible functions changes if we allow only 2-tape Turing machines in the definition?Q3: What are the provable reasons for believing that all nice functions are fully time-constructible?The paperKojiro Kobayashi: On Proving Time Constructibility of Functions. Theor. Comput. Sci. 35: 215-225 (1985)partially answers Q3. The partial summary and upgrade of it is in this answer. I take Q3 as answered.Historically, the notion of real-time countable function was used instead of (fully) time-constructible. See this question for more.
Equivalent definitions of time constructibility
cc.complexity theory;time complexity;terminology