Types of Time Inconstructible Functions

Question

So Wikipedia gives me notions of time and space constructibility and as far as I can tell, the two general definitions used are:

Functions $f: \mathbb{N} \to \mathbb{N}$ such that for all $n \geq n_0 \; \exists$ a Turing machine $M$ such that

1. $M(1^n)$ halts after exactly $f(n)$ steps/using $f(n)$ memory cells
2. $M(1^n) = f(n)$ (binary/unary representation) and $M$ halts (with)in $O(f(n))$ steps/space

Sublinear functions are not time constructible because the function won't be able to process the input string.

Some might still be space constructible (e.g. $\log n$).

Busy Beaver is not time constructible because it's uncomputable so there's no Turing machine that outputs the Busy Beaver number for n bit strings/alternatively there's no single Turing machine that always halts after exactly the $BB(n)$ steps on inputs of size $n$ (if one did it could compute the busy beaver number and thus solve the halting problem).

Are uncomputable functions and sublinear functions a jointly noexhaustive list of the functions that are not time constructible?

---

I guess some non-monotonic superlinear functions might be the best candidates.

Are there any non-contrived examples?

Preferably naturally occurring such functions (functions that organically arise in pure mathematics count as "natural" for my purposes).

Answer 1

A candidate for a computable but non-time-constructible function could be based on the Collatz conjecture.

Let $C: \mathbb{N} \to \mathbb{N}$ be defined as the median value (or other appropriate statistic e.g. the 1st quartile) reached by the Collatz sequence starting from $x$, where the sequence is defined by the rules:

1. If $x$ is even, divide it by 2ドル: x \mapsto \frac{x}{2}$,
2. If $x$ is odd, multiply it by 3ドル$ and add 1ドル$: $x \mapsto 3x + 1$.

If we assume the Collatz conjecture (or at least even if Collatz sequences don't eventually stabilise at the 1ドル$ loop they stabilise at some other loop), then $C(x)$ is computable.

Computing $C(x)$ is non-trivial. The Turing machine would need to simulate the entire sequence and track its trajectory, including any potentially large intermediate values or cycles, before determining $C(x)$. The time it takes to compute $C(x)$ for an input of size $n \; (n = \lceil\log_2 x\rceil)$ could far exceed the actual value of $C(n)$, especially if the sequence grows large before stabilising/looping.

Thus, $C$ is:

• Not sublinear because the sequence can generate large values
• Not uncomputable, since a machine can simulate the process step-by-step.

However, $C$ is non-time-constructible because the running time to compute the function can grow much faster than the value of the function itself, particularly for large $n$, where the machine might take many more steps than $C(n)$ to evaluate it.

---

Other non-monotonic functions (without closed form solutions) may be promising candidates for time inconstructible functions that are neither sublinear nor uncomputable.