查看“︁可構函數”︁的源代码

[[計算複雜度理論|複雜度理論]]裡，函數<math>f:\mathbb{N} \to \mathbb{N}</math>'''時間可構'''（英語：time constructible），意即存在運行時間規模在<math>f(n)</math>內的[[圖靈機]]，當輸入<math>n</math>時，圖靈機輸出<math>f(n)</math>。定義此類函數是為了排除一些無法成為圖靈機運行時間上界的函數。<ref name=":0">{{Cite book|title=Computational Complexity: A Conceptual Perspective|url=https://archive.org/details/computationalcom00gold_902|last=Goldreich|first=Oded|publisher=Cambridge University Press|year=2008|isbn=978-0-521-88473-0|pages=[https://archive.org/details/computationalcom00gold_902/page/n155 130], 139}}</ref>

==時間可構函數==
有兩種不同的方式去定義時間可構函數。第一種定義裡，函數<math>f</math>'''時間可構'''，當且僅當存在正整數<math>n_0</math>和圖靈機<math>M</math>，使得對所有<math>n\ge n_0</math>，在輸入字串<math>1^n</math>（<math>n</math>個1）後，該圖靈機恰好<math>f(n)</math>步後停機。第二種定義裡，函數<math>f</math>'''時間可構'''，當且僅當存在圖靈機<math>M</math>，在輸入字串<math>1^n</math>（<math>n</math>個1）後，它會在<math>O(f(n))</math>時間內輸出<math>f(n)</math>的二進制（亦可以用輸出[[一進制]]，兩種表示的定義等價，因為可以用<math>O(f(n))</math>時間轉換兩種表示）。<ref name=":0" />

另外，還有整體時間可構函數：函數<math>f</math>'''時間全可構'''當且僅當存在圖靈機<math>M</math>，對所有自然數<math>n</math>，輸入字串<math>1^n</math>後，恰好在<math>f(n)</math>步後停機。這個定義比前兩個定義更狹窄，但在多數應用裡，使用哪種定義都無傷大雅{{Citation needed|date=May 2021}}。

==空間可構函數==
類似地，函數<math>f</math>'''空間可構'''，當且僅當存在正整數<math>n_0</math>和圖靈機<math>M</math>，使得對所有<math>n\ge n_0</math>，在輸入字串<math>1^n</math>後，該圖靈機恰好在使用了<math>f(n)</math>個格子後停機。等價地，函數<math>f</math>'''空間可構'''，當且僅當存在圖靈機<math>M</math>，在輸入字串<math>1^n</math>（<math>n</math>個1）後，它會在''[[big-O notation|O]]''(''f''(''n''))空間內輸出<math>f(n)</math>的二進制（或[[一進制]]）。<ref name=":0" />。

另外，函數<math>f</math>'''空間全可構'''當且僅當存在圖靈機<math>M</math>，對所有自然數<math>n</math>，在輸入字串<math>1^n</math>後，恰好在使用了<math>f(n)</math>個格子後停機{{Citation needed|date=May 2021}}。

==例子==
所有滿足<math>f(n) \ge cn </math>（其中<math>c>0</math>是常數）的常見函數（例如<math>n, n^k, 2^n</math>）都是時間和空間可構的。除了最終是常數的函數，<math>o(n)</math>裡的函數都不時間可構，因為圖靈機甚至没有時間完整讀入<math>n</math>。不過{{tmath|\log(n)}}是空間可構的。

==應用==
複雜度理論的結論，例如[[時間階層定理]]使用了時間可構函數去刻劃複雜度層級。這是因為時間層級能成立的基石是能在''[[big-O notation|O]]''(''f''(''n''))時間內判斷其他算法是否已經用了超過<math>f(n)</math>步的圖靈機。假若<math>f(n)</math>不能在這麼多步以內計算，該圖靈機當然不可能存在。類似的複雜度定理一般對所有自然的函數<math>f</math>都成立，但不一定對人為構造的<math>f</math>成立。時間可構函數的嚴謹定義成功準確刻劃了這些滿足時間階層定理的函數。

空間可構函數在[[空間階層定理]]裡亦有類似的應用。

{{PlanetMath attribution|id=3461|title=constructible}}

==參考文獻==
{{Reflist}}

[[Category:計算複雜性理論]]
[[Category:函數]]