チューリングマシン

(deterministic) Turing machine, TM

種類と計算時間, 計算空間

$ k-tape Turing machine$ M = (\Gamma, Q, \delta)

$ T(n), $ S(n)

言語$ \{\Box, \triangleright,0,1\}の$ k-tape Turing machine$ \tilde M = (\{\Box, \triangleright,0,1\}, Q, \delta)

$ \le 4\log|\Gamma|T(n), $ \le S(n)

single tape Turing machine$ M_1 = (\Gamma, Q, \delta)

$ \le 5kT(n)^2, $ \le kS(n)

2-tape oblivious TM$ M_\mathsf{Oblv} = (\Gamma, Q, \delta)

$ \le O(T(n)^2), $ \le S(n)

いずれも計算時間は高々多項式程度, 計算空間は定数倍程度しか増加しない

だからPやLなどを議論する際に上のどのTMを採用してもよい

その他