Time-Constructible Functions
The time
hierarchy theorem promises something almost too clean: give a Turing machine
asymptotically more time and it decides strictly more languages. But read the theorem's fine print and
you keep meeting the same three-word hypothesis — "time-constructible". Drop it and the
theorem is not merely harder to prove; it becomes false. There are (bizarre) time
bounds for which squaring, cubing, even exponentiating your whole budget buys you no new power
at all.
So what is this condition, and why does the whole edifice of hierarchy theorems rest on it? The short
answer: a diagonalising machine must be able to count out its own time budget — to
build an alarm clock it can afford to wind. A function that lets it do so is
time-constructible. This page defines the notion precisely, shows that every honest
running time you will ever name qualifies, and exhibits the pathological monsters that do not — the
ones the gap theorem weaponises.
The definition
Intuitively, t(n) is time-constructible if a machine can compute the
number t(n) — or equivalently, mark off
t(n) tape cells — without spending more than a constant factor over
t(n) steps doing it. The clock must be affordable: winding it up may not
cost more than the time it is meant to measure.
A function t : \mathbb{N} \to \mathbb{N} with
t(n) \ge n is time-constructible if some deterministic
Turing machine, given the input 1^n (the number
n in unary), does either of these equivalent jobs in
O(t(n)) steps:
- Computes the value t(n) and writes it (say in binary)
on a tape; or
- Marks off exactly t(n) cells — halting with a
"counter" of length t(n) laid out on the tape.
The two formulations coincide up to the model's usual constant factors, and it is the second — a block
of t(n) cells — that the hierarchy proof actually consumes. The companion
notion for space, space-constructible, asks the same of memory: a machine that lays
out s(n) tape cells using O(s(n)) space, powering
the space hierarchy theorem in exactly the same way.
The clock is what makes diagonalisation finite
Recall the diagonal machine \mathrm{Diag} at the heart of the hierarchy
proof. On input w = \langle M\rangle it simulates
M and then does the opposite of whatever
M answers. But a raw simulation of an arbitrary machine can run
forever — that is precisely the halting problem. The only thing standing between
"separation theorem" and "undecidability" is a stopwatch: simulate for at most
t(|w|) steps, and if the budget runs out, stop and decide by default.
To enforce "at most t(|w|) steps", the machine must know that
number — and building it must be cheap, or the clock itself would blow the budget it is trying to
police. Marking off t(n) cells and decrementing one per simulated step is
the mechanism; time-constructibility is exactly the guarantee that the mechanism fits inside
O(t(n)). Watch the clock get built and then counted down:
First the input 1^n arrives; then the constructible clock lays out a block
of t(n) cells at a cost of O(t(n)); then the
diagonaliser burns one clock cell per simulated step of M. When the cells
run out, time is up — the simulation halts, and \mathrm{Diag} stays
decidable. Remove constructibility and the machine cannot even tell when to stop.
Everything you'd call a running time qualifies
The reassuring news is that the class of time-constructible functions is enormous. Every function you
would ever write down as an honest complexity bound is time-constructible:
| Function t(n) | Constructible? | Why (sketch) |
|---|
| n | yes | copy the input; O(n) |
| n^2 | yes | multiply n\times n in O(n^2) |
| n^3,\; n^k | yes | repeated multiplication |
| n\log n | yes | compute \lceil\log n\rceil, then a product |
| 2^n | yes | write a 1 followed by n zeros; O(2^n) |
| n! | yes | iterated multiplication, well within O(n!) |
| a wild, uncomputable-jump g | no | the machine can't even name g(n) in time |
The closure properties help too: sums, products, and compositions of constructible functions are
constructible, and any t(n) \ge n\log n that you can compute in
O(t(n)) time is in the club. Only pathologically irregular
functions — ones that leap around unpredictably, faster than any machine can track within their own
budget — are excluded. They never arise as the running time of an actual algorithm, which is why the
hypothesis feels invisible in practice.
Counting out the budget, in code
Here is the "clock" made concrete. For each candidate bound we compute
t(n) and then simulate laying out and burning down the counter,
tallying the work. The tally never exceeds a constant times t(n) — that is
constructibility in action. A binary down-counter from t(n) to
0 does O(t(n)) total bit-flips (amortised
O(1) per tick), so the clock is genuinely affordable.
// A time bound as a function of n, plus a human-readable name.
interface Bound { name: string; t: (n: number) => number; }
const bounds: Bound[] = [
{ name: "n", t: (n) => n },
{ name: "n^2", t: (n) => n * n },
{ name: "n log n",t: (n) => Math.ceil(n * Math.log2(n)) },
{ name: "2^n", t: (n) => 2 ** n },
];
// "Wind up and burn down" a binary counter of size B: total bit-flips is O(B).
function counterWork(B: number): number {
let flips = 0;
for (let v = B; v > 0; v--) {
// decrementing flips the trailing run of set bits + one more: amortised O(1).
let x = v;
do { flips++; } while ((x & 1) === 0 && (x >>= 1) > 0);
}
return flips;
}
console.log("n | t(n) | clock work | work / t(n) (must stay O(1))");
for (const n of [4, 6, 8, 10]) {
for (const b of bounds) {
const T = b.t(n);
const w = counterWork(T);
const ratio = (w / T).toFixed(2);
console.log(`${n} | ${String(T).padStart(8)} | ${String(w).padStart(10)} | ${ratio} (${b.name})`);
}
}
console.log("\nEvery ratio is bounded by a constant — each clock costs O(t(n)) to run.");
console.log("So n, n^2, n log n and 2^n are all time-constructible.");
The monsters: non-constructible bounds and the gap theorem
Why insist on constructibility at all — surely "more time = more power" is just obvious? The stunning
answer is that without it, the intuition is wrong. Trakhtenbrot and Borodin's
gap theorem builds a (necessarily non-constructible) time bound with a vast dead zone
above it, where an enormous increase in budget decides not one extra language.
- For any computable "gap" function g(n) \ge n (say
g(m) = 2^m), there exists a computable, monotone time bound
f(n) such that
\mathrm{DTIME}\!\big(f(n)\big) \;=\; \mathrm{DTIME}\!\big(g(f(n))\big).
- Concretely there is an f with
\mathrm{DTIME}(f) = \mathrm{DTIME}(2^{f}): exponentiating the entire
budget buys nothing.
The trick is that f is engineered to skip over every "interesting"
running-time value — it lands only in a wasteland where no machine's runtime falls between
f(n) and g(f(n)). Such an f
cannot be time-constructible (if it were, the hierarchy theorem would contradict the gap). This is the
sharpest possible statement of why the hierarchy theorem needs the hypothesis: constructibility
is exactly the property that rules the gap monsters out. The theorem is not being
fussy — its hypothesis is doing indispensable work.
Because "budget increase" and "extra languages decided" are only linked when you can build a clock
to spend the budget precisely. The hierarchy theorem separates
\mathrm{DTIME}(o(f)) from \mathrm{DTIME}(f\log f)
by a diagonal machine that meters exactly f steps — impossible if
f is not constructible. The gap theorem lives in that impossibility: it
hand-picks an f so ill-behaved that no problem has a runtime in
the whole interval [f,\,2^{f}], so widening the budget across that empty
interval adds no deciders. The moral: the resource is time, but the currency is a
constructible clock. No clock, no purchase.
Constructible is more than computable
A subtle but crucial distinction: time-constructibility is not the same as "the
function is computable". A non-constructible f in the gap theorem is
perfectly computable — you can write a program that outputs f(n).
What fails is the budget: you cannot compute f(n) within
O(f(n)) steps. Constructibility is computability with a self-imposed
deadline, and that deadline is the entire point. It is what lets a machine measure its own time
without a meta-clock, avoiding an infinite regress.
Two traps snare newcomers. First, do not read "time-constructible" as merely "the running time is a
reasonable function" — the definition has teeth: the machine must produce
t(n) (or mark off t(n) cells) within
O(t(n)) steps. A function you can only compute in, say,
2^{t(n)} time is computable but not time-constructible, and it is
exactly such functions the gap theorem exploits. Second, do not confuse the roles: the diagonal
machine's constructible clock is a tool inside the proof, not a hypothesis about the
languages being separated. And note the mild floor — the standard definition assumes
t(n) \ge n (often t(n) \ge n\log n), since a
machine cannot even read all of an n-bit input, let alone diagonalise,
in sub-linear time. State the notion without the budget clause and you have said nothing that keeps
the hierarchy theorem true.