A function f: is time constructible if there is a deterministic Turing machine T (with alphabet {0,1,B}) such that when T receives as input the a series of n ones, it halts after exactly f(n) steps. Similarly f is space constructible if there is a similarMathworldPlanetmathPlanetmath Turing machineMathworldPlanetmath which halts after using exactly f(n) cells.

Most ’natural’ functions are both time and space constructible, including constant functions, polynomials, and exponentials, for example.

Title constructible
Canonical name Constructible
Date of creation 2013-03-22 13:03:20
Last modified on 2013-03-22 13:03:20
Owner Henry (455)
Last modified by Henry (455)
Numerical id 7
Author Henry (455)
Entry type Definition
Classification msc 68Q15
Defines time constructible
Defines space constructible