「チューリングマシン」の版間の差分

m
原状回復 see: プロジェクト:数学/函数と関数: Reptber (会話) による ID:44391260 の版を取り消し
m
m (原状回復 see: プロジェクト:数学/函数と関数: Reptber (会話) による ID:44391260 の版を取り消し)
* b は ''Γ'' の元であり、'''空白記号'''とよばれる。
* ''Σ'' は ''Γ'' - {b} の部分集合であり、'''入力字母'''とよばれる。その元を'''入力記号'''という。
* δ は Q × ''Γ'' から Q × ''Γ'' × {left, right} への写像であり、'''遷移数'''とよばれる。δ(q, a) = (q', a', m) は、「現在の状態が q であり、着目位置にある記号が a であれば、状態を q' に移し、着目位置に記号 a' を書き込んでから、着目位置を m 方向に1つずらす」と読む。
* q<sub>init</sub> は Q の元であり、'''初期状態'''とよばれる。
* q<sub>acc</sub> は Q の元であり、'''受理状態'''とよばれる。
M の'''状況'''とは、<math>\mathit\Gamma \cup Q</math>上の(片側)無限列のうち、Q の元がちょうど1度現れ、また b 以外の記号が有限回しか現れないものをいう。遷移数 δ は、状況から状況への写像を自然に定める。M が文字列<math>x \in \Sigma ^*</math>を'''受理'''するとは、状況<math>q _{\mathrm{init}} x b b \cdots</math>にこの写像を有限回施すことで状況<math>q _{\mathrm{acc}} b b \cdots</math>が得られることをいう。その最小回数を M の x に対する'''実行時間'''とよぶ。その過程における状況中の q の最右位置を、M が x に対して使用する'''記憶領域量'''という。
 
M が言語<math>L \subseteq \mathit\Sigma ^*</math>を'''認識'''するとは、M が L の元のみをみな受理することをいう。そのようなチューリング機械 M が存在するとき、L は'''帰納可枚挙'''(recursively enumerable)あるいは'''計算可枚挙'''(computably enumerable)であるという。L と<math>\mathit\Sigma ^* \setminus L</math>がともに帰納可枚挙であるとき、Lは'''帰納的'''(recursive)あるいは'''決定可能'''(decidable)であるという。
次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。
* 字母<math>\mathit\Gamma</math>の大きさ(それが<math>\mathit\Sigma</math>を含む有限集合であるかぎり)。
* 遷移数が着目位置を左右に必ず動かすか、同じ位置に留まる事を許すか。
* 文字列を受理するさい、テープ上の記号をすべて<math>b</math>にする必要があるか、受理状態へ移るだけでよいか。
* テープが両方向に無限であるか、片側に終端があるか。
* さらに、記憶領域が一次元のテープであるか、より複雑な形状をしているか。
* テープの本数。
空間計算量を細かく調べるときには、書き換えできない入力専用テープを設けて、そこでの使用領域量を無視することがある。すなわち、遷移数<math>\delta</math>を<math>Q \times \mathit\Gamma ^2</math>から<math>Q \times \mathit\Gamma \times \{\mathrm{left}, \mathrm{right}\} ^2</math>への写像とし、状況の定義も適切に変更する。
 
=== 変換機 ===
言語を認識するだけでなく、<math>\mathit\Sigma ^*</math>から<math>\mathit\Sigma ^*</math>への部分数<math>f</math>を'''計算'''する機械を考えることもできる。すなわち機械<math>M</math>は、各<math>x \in \mathrm{dom} (f)</math>に対しては文字列<math>f (x)</math>をテープに書いてから初めて受理状態へ移り、<math>x \notin \mathrm{dom} (f)</math>に対しては決して受理状態へ移らない。このような<math>M</math>が存在するとき、<math>f</math>は'''部分帰納的'''あるいは'''[[計算可能性理論|計算可能]]'''(computable)であるという。
 
=== 決定性と非決定性 ===
1,038

回編集