Time-constructible definitions
There are two different definitions of a time-constructible function. In the first definition, a function ''f'' is called time-constructible if there exists a positive integer ''n''0 and Turing machine ''M'' which, given a string 1''n'' consisting of ''n'' ones, stops after exactly ''f''(''n'') steps for all ''n'' ≥ ''n''0. In the second definition, a function ''f'' is called time-constructible if there exists a Turing machine ''M'' which, given a string 1''n'', outputs the binary representation of ''f''(''n'') in '' O''(''f''(''n'')) time (a unary representation may be used instead, since the two can be interconverted in ''O''(''f''(''n'')) time). There is also a notion of a fully time-constructible function. A function ''f'' is called fully time-constructible if there exists a Turing machine ''M'' which, given a string 1''n'' consisting of ''n'' ones, stops after exactly ''f''(''n'') steps. This definition is slightly less general than the first two but, for most applications, either definition can be used.Space-constructible definitions
Similarly, a function ''f'' is space-constructible if there exists a positive integer ''n''0 and a Turing machine ''M'' which, given a string 1''n'' consisting of ''n'' ones, halts after using exactly ''f''(''n'') cells for all ''n'' ≥ ''n''0. Equivalently, a function ''f'' is space-constructible if there exists a Turing machine ''M'' which, given a string 1''n'' consisting of ''n'' ones, outputs the binary (or unary) representation of ''f''(''n''), while using only '' O''(''f''(''n'')) space. Also, a function ''f'' is fully space-constructible if there exists a Turing machine ''M'' which, given a string 1''n'' consisting of ''n'' ones, halts after using exactly ''f''(''n'') cells.Examples
All the commonly used functions ''f''(''n'') (such as ''n'', ''nk'', 2''n'') are time- and space-constructible, as long as ''f''(''n'') is at least ''cn'' for a constant ''c'' > 0. No function which is '' o''(''n'') can be time-constructible unless it is eventually constant, since there is insufficient time to read the entire input. However, is a space-constructible function.Applications
Time-constructible functions are used in results from complexity theory such as theReferences
{{Reflist Computational complexity theory Types of functions