constructible

A function $f:\mathbb{N}\to \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
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