チューリングマシン
次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。
字母 Γ {\displaystyle {\mathit {\Gamma }}} の大きさ(それが Σ {\displaystyle {\mathit {\Sigma }}} を含む有限集合であるかぎり)。
遷移函数が着目位置を左右に必ず動かすか、同じ位置に留まる事を許すか。
文字列を受理するさい、テープ上の記号をすべて b {\displaystyle b} にする必要があるか、受理状態へ移るだけでよいか。
テープが両方向に無限であるか、片側に終端があるか。
さらに、記憶領域が一次元のテープであるか、より複雑な形状をしているか。
テープの本数。
空間計算量を細かく調べるときには、書き換えできない入力専用テープを設けて、そこでの使用領域量を無視することがある。すなわち、遷移函数 δ {\displaystyle \delta } を Q × Γ 2 {\displaystyle Q\times {\mathit {\Gamma }}^{2}} から Q × Γ × { l e f t , r i g h t } 2 {\displaystyle Q\times {\mathit {\Gamma }}\times \{\mathrm {left} ,\mathrm {right} \}^{2}} への写像とし、状況の定義も適切に変更する。
状態集合 Q のある元 qacc を受理状態(accepting state)と定める。