A function is time constructible if there is a deterministic Turing machine (with alphabet ) such that when receives as input the a series of ones, it halts after exactly steps. Similarly is space constructible if there is a similar Turing machine which halts after using exactly cells.
Most ’natural’ functions are both time and space constructible, including constant functions, polynomials, and exponentials, for example.
|Date of creation||2013-03-22 13:03:20|
|Last modified on||2013-03-22 13:03:20|
|Last modified by||Henry (455)|