Constructible Function

A function f(x) is said to be constructible if some algorithm F computes it, in binary, within volume O(f(x)), i.e., V_(F(x))=O(f(x)). Here, the volume V_(A(x)) is the combined number of active edges during all steps, which is the number of state-changes needed to run a certain Turing machine on a particular input.

See also

Computable Function, Rabin's Compression Theorem

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Constructible Function." From MathWorld--A Wolfram Web Resource.

Subject classifications