Constructible Function
In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f(n) can be constructed from n by a Turing machine in the time of order f(n). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.
Read more about Constructible Function: Time-constructible Definitions, Space-constructible Definitions, Examples, Applications
Famous quotes containing the word function:
““... The state’s one function is to give.
The bud must bloom till blowsy blown
Its petals loosen and are strown;
And that’s a fate it can’t evade
Unless ‘twould rather wilt than fade.””
—Robert Frost (1874–1963)