# 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 |