# constructible

A function $f:\mathbb{N}\rightarrow\mathbb{N}$ 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 similar Turing machine 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 Constructible 2013-03-22 13:03:20 2013-03-22 13:03:20 Henry (455) Henry (455) 7 Henry (455) Definition msc 68Q15 time constructible space constructible