可构函数

有两种不同的方式去定义时间可构函数。第一种定义里，函数${\displaystyle f}$ 时间可构，当且仅当存在正整数${\displaystyle n_{0}}$ 和图灵机${\displaystyle M}$ ，使得对所有${\displaystyle n\geq n_{0}}$ ，在输入字串${\displaystyle 1^{n}}$ （${\displaystyle n}$ 个1）后，该图灵机恰好${\displaystyle f(n)}$ 步后停机。第二种定义里，函数${\displaystyle f}$ 时间可构，当且仅当存在图灵机${\displaystyle M}$ ，在输入字串${\displaystyle 1^{n}}$ （${\displaystyle n}$ 个1）后，它会在${\displaystyle O(f(n))}$ 时间内输出${\displaystyle f(n)}$ 的二进制（亦可以用输出一进制，两种表示的定义等价，因为可以用${\displaystyle O(f(n))}$ 时间转换两种表示）。^[1]

另外，还有整体时间可构函数：函数${\displaystyle f}$ 时间全可构当且仅当存在图灵机${\displaystyle M}$ ，对所有自然数${\displaystyle n}$ ，输入字串${\displaystyle 1^{n}}$ 后，恰好在${\displaystyle f(n)}$ 步后停机。这个定义比前两个定义更狭窄，但在多数应用里，使用哪种定义都无伤大雅^{[来源请求]}。

类似地，函数${\displaystyle f}$ 空间可构，当且仅当存在正整数${\displaystyle n_{0}}$ 和图灵机${\displaystyle M}$ ，使得对所有${\displaystyle n\geq n_{0}}$ ，在输入字串${\displaystyle 1^{n}}$ 后，该图灵机恰好在使用了${\displaystyle f(n)}$ 个格子后停机。等价地，函数${\displaystyle f}$ 空间可构，当且仅当存在图灵机${\displaystyle M}$ ，在输入字串${\displaystyle 1^{n}}$ （${\displaystyle n}$ 个1）后，它会在O(f(n))空间内输出${\displaystyle f(n)}$ 的二进制（或一进制）。^[1]。

另外，函数${\displaystyle f}$ 空间全可构当且仅当存在图灵机${\displaystyle M}$ ，对所有自然数${\displaystyle n}$ ，在输入字串${\displaystyle 1^{n}}$ 后，恰好在使用了${\displaystyle f(n)}$ 个格子后停机^{[来源请求]}。

所有满足${\displaystyle f(n)\geq cn}$ （其中${\displaystyle c>0}$ 是常数）的常见函数（例如${\displaystyle n,n^{k},2^{n}}$ ）都是时间和空间可构的。除了最终是常数的函数，${\displaystyle o(n)}$ 里的函数都不时间可构，因为图灵机甚至没有时间完整读入${\displaystyle n}$ 。不过${\displaystyle \log(n)}$ 是空间可构的。

复杂度理论的结论，例如时间阶层定理使用了时间可构函数去刻划复杂度层级。这是因为时间层级能成立的基石是能在O(f(n))时间内判断其他算法是否已经用了超过${\displaystyle f(n)}$ 步的图灵机。假若${\displaystyle f(n)}$ 不能在这么多步以内计算，该图灵机当然不可能存在。类似的复杂度定理一般对所有自然的函数${\displaystyle f}$ 都成立，但不一定对人为构造的${\displaystyle f}$ 成立。时间可构函数的严谨定义成功准确刻划了这些满足时间阶层定理的函数。

空间可构函数在空间阶层定理里亦有类似的应用。

本条目含有来自PlanetMath《constructible》的内容，版权遵守知识共享协议：署名-相同方式共享协议。