時間可構造函式

時間可構造函式是圖靈機的一種停機時間函式。

時間可構造函式(time constructable function圖靈機的一種停機時間函式.設f為一個遞歸函式，如果存在一個圖靈機M，使對任何字長為n的字W，當W輸人M後，M恰好在f<n)步停機.則稱f為時間可構造的.實際上，遞歸函式f滿足條件fl a.e"<.f<n)i<1}--e) " n) (e}0為某個常數).則只要存在某個圖靈機M和常數。，使M在任何長為;的字輸入後都會在。" f<n)步之內停機，那么f必定是時間可構造的函式.對時間可構造的函式f來說，全體以f為時間界函式的圖靈機可以能行地枚舉出來:Mo,MI,…這樣，{L<M;> }tE}}恰好是以j為界函式的時間複雜性語言類(其中L<從)為由M接受的語言)，即為DTIME < f)一{L存在一個圖靈機M，以f為時間界函式接受L}.這一點，當f不是時間可構造函式時並不成立.