細かい相違
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/26 07:11 UTC 版)
次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。 字母 Γ {\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}} への写像とし、状況の定義も適切に変更する。
※この「細かい相違」の解説は、「チューリングマシン」の解説の一部です。
「細かい相違」を含む「チューリングマシン」の記事については、「チューリングマシン」の概要を参照ください。
- 細かい相違のページへのリンク
