Constructible function

In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that there exists a Turing machine M which, given a string 1ⁿ consisting of n ones, stops in O(f(n)) steps and outputs a string 1^f(n) consisting of f(n) ones.

All the commonly used functions f(n) (such as n, n^k, 2ⁿ) are time-constructible, as long as f(n) is at least cn for a constant c>0.

Time-constructible functions are used in complexity theory results such time hierarchy theorem. Such results are typically true for all natural functions f but not necessarily true for artificially constructed f. To formulate them precisely, it is necessary to have a precise definition for a natural function f for which the theorem is true. Time-constructible functions are often used to provide such definition.