Constructible function

The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.

In the first definition, a function f is called time-constructible if there exists a positive integer n0 and Turing machine M which, given a string 1n consisting of n ones, stops after exactly f(n) steps for all n ≥ n0.

A function f is called fully time-constructible if there exists a Turing machine M which, given a string 1n consisting of n ones, stops after exactly f(n) steps.

[3] Similarly, a function f is space-constructible if there exists a positive integer n0 and a Turing machine M which, given a string 1n consisting of n ones, halts after using exactly f(n) cells for all n ≥ n0.

Equivalently, a function f is space-constructible if there exists a Turing machine M which, given a string 1n consisting of n ones, outputs the binary (or unary) representation of f(n), while using only O(f(n)) space.