チューリングマシン

オートマタのクラス

チューリングマシンは、テープ上の記号を規則表に従って操作する抽象的な機械を記述する計算の数学的モデルです^{[ 1 ] 。 [ 2 ]}このモデルは単純ですが、あらゆるコンピュータアルゴリズムを実装することができます^{[ 3 ]。}

この機械は、離散的なセルに分割された無限の[4]メモリテープ上で動作し^、各セル^には、機械^のアルファベットと呼ばれる有限の記号セット^から抽出された単一の記号が格納されます。機械には「ヘッド」があり、機械の動作中のどの時点でも、これらのセルのいずれかの上に配置され、有限の状態セットから選択された「状態」を持ちます。動作の各ステップで、ヘッドはセル内の記号を読み取ります。次に、記号と機械自身の現在の状態に基づいて、機械は同じセルに記号を書き込み、ヘッドを左または右に1ステップ移動させるか^{[ 6 ]}、計算を停止します。どの置換記号を書き込むか、ヘッドをどちらの方向に移動させるか、停止するかどうかの選択は、現在の状態と読み取られた記号の各組み合わせに対して何を行うかを指定する有限のテーブルに基づいています。実際のコンピュータプログラムと同様に、チューリングマシンが停止しない無限ループに陥る可能性もあります。

チューリングマシンは1936年にアラン・チューリングによって発明され、^{[ 7 ] [ 11 ]}彼はそれを「aマシン」（自動機械）と呼んだ。^{[ 12 ]}後に「チューリングマシン」という用語を考案したのは、チューリングの博士課程指導教官であるアロンゾ・チャーチであった。 ^{[ 13 ]}このモデルにより、チューリングは2つの質問に否定的に答えることができた。

• テープ上の任意のマシンが「循環的」（例えば、フリーズしたり、計算タスクを継続できなかったりする）かどうかを判定できるマシンは存在するだろうか？
• テープ上の任意の機械が特定のシンボルを印刷したことがあるかどうかを判定できる機械は存在するか？^{[ 14 ] [ 15 ]}

このように、任意の計算が可能な非常に単純な装置の数学的記述を提供することにより、彼は計算の一般的な性質、特に決定問題（すべての数学的命題が証明可能か反証可能か）の計算不可能性を証明することができた。 ^{[ 16 ]}

チューリングマシンは、機械的計算能力には根本的な限界があることを証明した。^{[ 3 ]}

チューリングマシンは任意の計算を表現できるものの、そのミニマルな設計のため、実際の計算には速度が遅すぎる。現実世界のコンピュータは、チューリングマシンとは異なり、ランダムアクセスメモリを使用する異なる設計に基づいている。

チューリング完全性とは、計算モデルまたは命令体系がチューリングマシンをシミュレートできる能力のことである。チューリング完全なプログラミング言語は、理論的にはコンピュータが実行可能なすべてのタスクを表現できる。有限メモリの制約を無視すれば、ほぼすべてのプログラミング言語がチューリング完全である。

チューリングマシンは、コンピュータが行うすべてのデータ操作を制御する中央処理装置（CPU）の理想化されたモデルであり、標準的なチューリングマシンはデータを格納するためにシーケンシャルメモリを使用します。通常、シーケンシャルメモリは、マシンが読み書き操作を実行できる無限長のテープとして表現されます。

形式言語理論の文脈において、チューリングマシン（オートマトン）は、アルファベットの有効な文字列の任意の部分集合を列挙することができる。このように列挙可能な文字列の集合は、再帰的に列挙可能な言語と呼ばれる。チューリングマシンは、出力文字列を列挙するのではなく、有効な入力文字列を認識するモデルとして定義することもできる。

チューリングマシンMと任意の文字列sが与えられた場合、 Mが最終的にsを生成するかどうかを判定することは一般に不可能である。これは停止問題が解けないことに起因するものであり、計算の理論的限界に大きな影響を与える。

他のチューリングマシンをシミュレートできるチューリングマシンは、ユニバーサルチューリングマシン（UTM、または単にユニバーサルマシン）と呼ばれます。同様の「普遍性」を持つ別の数学的形式体系であるラムダ計算は、アロンゾ・チャーチによって導入されました。チャーチの研究はチューリングの研究と結びつき、チャーチ＝チューリングのテーゼの基礎を形成しました。このテーゼは、チューリングマシン、ラムダ計算、およびその他の同様の計算形式体系は、論理学と数学における効果的な方法の非形式的な概念を実際に捉えており、特定の形式体系に縛られることなく、数学的に正確な方法でアルゴリズムまたは「機械的手順」について推論できるモデルを提供すると述べています。 チューリングマシンの抽象的な特性を研究することで、コンピュータ科学、計算可能性理論、複雑性理論に関する多くの洞察が得られました。

チューリングマシンは、テープ上で機械的に動作する機械を数学的にモデル化したものです。このテープには記号が記録されており、機械はテープヘッドを使って一度に1つずつ読み書きできます。動作は、「状態42で、検出された記号が0であれば1を書き込む。検出された記号が1であれば、状態17に遷移する。状態17で、検出された記号が0であれば1を書き込み、状態6に遷移する」などの有限個の基本命令によって完全に決定されます。チューリングは、元の論文（「計算可能な数について、決定問題への応用」、下記の参考文献も参照）の中で、機械ではなく、彼が「コンピュータ」と呼ぶ人物を想定しており、その人物はこれらの決定論的な機械的規則を忠実に（あるいはチューリングの言葉を借りれば「気まぐれに」）実行します。

より具体的に言うと、チューリングマシンは以下から構成されます。

• テープはセルに分割され、セルは隣り合って並んでいます。各セルには、有限のアルファベットから選ばれた記号が格納されています。アルファベットには、特別な空白記号（ここでは「0」と表記）と、1つ以上の他の記号が含まれています。テープは左右に任意に拡張可能であると想定されており、チューリングマシンは常に計算に必要なだけのテープを供給されます。まだ書き込まれていないセルには、空白記号が書き込まれていると想定されています。一部のモデルでは、テープの左端に特別な記号が記されており、テープは右方向に拡張可能、または無限に拡張可能です。
• テープ上の記号を読み書きし、テープを左右に1セルずつ（そして1セルだけ）移動できるヘッド。一部の機種では、ヘッドが移動し、テープは固定されている。
• チューリングマシンの状態を格納する状態レジスタ。その状態は有限個存在する。その中には、状態レジスタを初期化するための特別な開始状態が含まれる。チューリングは、これらの状態は、計算を行う人が通常抱く「精神状態」に取って代わるものだと述べた。
• 有限テーブル^{[ 19 ]}の命令^{[ 20 ]}は、マシンが現在置かれている状態(q _{i )}と、テープ上で読み取っているシンボル(a _j )(現在ヘッドの下にあるシンボル)が与えられた場合に、マシンに以下の手順を順番に実行するように指示します( 5タプルモデルの場合)。

1. 消去するか、記号を書き込む（_jをj1に置き換える）。
2. 頭を動かします（これはd _kで表され、値は「L」で左に1歩、「R」で右に1歩、「N」で同じ場所に留まります）。
3. 規定どおり、同じ状態または新しい状態を仮定します（状態 q _i1へ移動）。

4タプルモデルでは、シンボルの消去または書き込み（a _j1）とヘッドの左右移動（d _k）は別々の命令として指定されます。このテーブルは、マシンに（ia）シンボルを消去または書き込み、（ib）ヘッドを左右に移動させ、その後（ii）規定されたとおりに同じ状態または新しい状態に移行するように指示しますが、（ia）と（ib）の両方の動作を同じ命令で実行することはできません。一部のモデルでは、現在のシンボルと状態の組み合わせに対応するエントリがテーブルにない場合、マシンは停止します。他のモデルでは、すべてのエントリを埋める必要があります。

機械のあらゆる部分（つまり、その状態、シンボルコレクション、および任意の時点で使用されているテープ）とその動作（印刷、消去、テープの移動など）は有限で、離散的で、区別可能です。無限のテープ量と実行時間によって、無限の記憶容量が実現されるのです。

^{Hopcroft & Ullman (1979) [ 21 ]}に従って、 (1テープ)チューリングマシンは、7タプルとして形式的に定義できる。${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$どこ

• ${\displaystyle Q}$は有限で空でない状態の集合である。
• ${\displaystyle \Gamma }$は、有限で空でないテープアルファベット記号の集合です。
• ${\displaystyle b\in \Gamma }$は空白記号（計算中のどの段階でもテープ上に無限回出現することが許される唯一の記号）です。
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$は入力シンボルの集合、つまり初期テープ内容に出現することが許されるシンボルの集合です。
• ${\displaystyle \delta$ :(Q\setminus F)\times \Gamma \rightharpoonup Q\times \Gamma \times \{L,R\}} は 遷移関数と呼ばれる部分関数であり、L は左シフト、R は右シフトです。${\displaystyle \delta }$現在の状態と現在のテープシンボルで定義されていない場合、マシンは停止します。^{[ 22 ]}直感的には、遷移関数は現在の状態から遷移する次の状態、ヘッドが指す現在のシンボルを上書きするシンボル、および次のヘッドの動きを指定します。
• ${\displaystyle q_{0}\in Q}$初期状態です。
• ${\displaystyle F\subseteq Q}$は最終状態または受理状態の集合です。初期テープの内容は、によって受理されたと言われます。${\displaystyle M}$最終的にある状態から停止した場合${\displaystyle F}$。

別のバリエーションでは、方向セットの3番目の要素として「シフトなし」（Nなど）を指定できる。${\displaystyle \{L,R\}}$。

3状態ビジービーバーの7タプルは次のようになります（このビジービーバーの詳細については、チューリングマシンの例を参照してください）。

• ${\displaystyle Q=\{{\mbox{A}},{\mbox{B}},{\mbox{C}},{\mbox{HALT}}\}}$（州）
• ${\displaystyle \Gamma =\{0,1\}}$（テープのアルファベット記号）
• ${\displaystyle b=0}$（空白記号）
• ${\displaystyle \Sigma =\{1\}}$（入力シンボル）
• ${\displaystyle \delta =}$下記の状態遷移表（遷移関数）を参照してください。
• ${\displaystyle q_{0}={\mbox{A}}}$（初期状態）
• ${\displaystyle F=\{{\mbox{HALT}}\}}$（最終状態）

最初はすべてのテープセルにマークが付けられています${\displaystyle 0}$。

ファン・エムデ・ボアス（1990）の言葉を借りれば、「集合論的対象（上記と同様の形式的な7タプル記述）は、機械がどのように動作し、その計算がどのようなものになるかについての部分的な情報しか提供しない」^{[ 23 ] 。}

例えば、

• 記号が実際にどのような形になるかについては多くの決定が必要であり、記号を永続的に読み書きするための確実な方法も必要となるだろう。
• 左シフトと右シフトの操作ではテープヘッドをテープ上で移動させることができますが、実際にチューリングマシンを構築する際には、テープをヘッドの下で前後にスライドさせる方が実用的です。
• テープは有限長で、必要に応じて自動的に空白が追加される（これが数学的な定義に最も近い）場合もあるが、テープヘッドが位置する明示的に指定された有限部分を除いて、片端または両端で無限に伸び、あらかじめ空白で埋められていると考える方が一般的である（もちろん、これは実際には実装できない）。テープの長さを固定することはできない。なぜなら、固定長にすると、与えられた定義に合致せず、テープの長さが入力サイズに比例する場合は機械が実行できる計算の範囲が線形限定オートマトンに、厳密に固定長の場合は有限状態機械に著しく制限されてしまうからである。

「状態」図

右側：上記の表を「状態遷移」図として表したもの。

通常、大きな表は表のままにしておく方が良い（Booth、p.  74）。表形式であれば、コンピュータによるシミュレーションも容易である（Booth、p.  74）。しかし、特定の概念、例えば「リセット」状態を持つ機械や繰り返しパターンを持つ機械（HillとPeterson、p.  244以降を参照）などは、図として見た方が理解しやすい場合がある。

図面がその表の改良版であるかどうかは、読者が特定の文脈において判断しなければならない。

読者は、このような図は、時間と空間を通じた計算の過程（「軌跡」）ではなく、ある時点における表の状態を捉えたスナップショットであることに改めて注意する必要がある。ビジービーバーマシンは実行されるたびに常に同じ状態軌跡をたどるが、可変入力「パラメータ」を与えることができる「コピー」マシンではそうではない。

図「計算の進行」は、3状態ビジービーバーの「状態」（命令）が計算の開始から終了までどのように進行するかを示しています。右端には、各ステップにおけるチューリングの「完全な構成」（クリーネの「状況」、ホップクロフト＝ウルマンの「瞬間的な記述」）が示されています。マシンが停止され、「状態レジスタ」とテープ全体が消去された場合、これらの「構成」を使用して、計算の進行状況のどこからでも計算を再開できます。^{[ 38 ]}

単純な万能チューリングマシンよりも計算能力が高いと思われる多くの機械は、実際にはそれ以上の能力を持たないことが証明されている（Hopcroft and Ullman p.  159、cf. Minsky (1967)）。それらの機械は、計算速度が速かったり、メモリ使用量が少なかったり、命令セットが小さかったりするかもしれないが、より強力な計算能力（つまり、より多くの数学関数）を持つことはできない。（チャーチ＝チューリングのテーゼは、あらゆる種類の機械について、つまり「計算可能」なものはすべて何らかのチューリングマシンで計算できるという仮説を立てている。）

チューリングマシンは、スタックのLIFO（後入れ先出し）要件を緩和することで、より柔軟かつ簡潔に設計されたシングルスタックプッシュダウンオートマトン（PDA）に相当します。さらに、チューリングマシンは、ヘッドの左側のテープを一方のスタックで、右側のテープをもう一方のスタックでモデル化することにより、標準的なLIFOセマンティクスを持つ2スタックPDAにも相当します。

その一方で、非常に単純なモデルの中には、チューリングマシンと同等、つまりチューリングマシンモデルと同じ計算能力を持つものもある。

一般的な同等のモデルとしては、マルチテープチューリングマシン、マルチトラックチューリングマシン、入出力のあるマシン、および決定性チューリングマシン（DTM ）とは対照的に、アクションテーブルに記号と状態の組み合わせごとに最大で1つのエントリしかない非決定性チューリングマシン（NDTM）などがある。

読み取り専用の右移動チューリングマシンは、DFAと同等である（ NFAからDFAへの変換アルゴリズムを使用すればNFAとも同等になる）。

実用的かつ教育的な目的においては、同等のレジスタマシンを通常のアセンブリプログラミング言語として使用することができます。

関連する疑問は、具体的なプログラミング言語によって表現される計算モデルがチューリング等価であるかどうかです。実際のコンピュータの計算は有限状態に基づいているため、チューリングマシンをシミュレートすることはできませんが、プログラミング言語自体には必ずしもこの制限があるわけではありません。Kirner ら (2009) は、汎用プログラミング言語の中にはチューリング完全なものとそうでないものがあることを示しました。たとえば、ANSI C はチューリング完全ではありません。ANSI C のすべてのインスタンス化 (標準ではレガシーの理由から特定の動作を意図的に未定義にしているため、異なるインスタンス化が可能です) は有限空間メモリを意味します。これは、ポインタと呼ばれるメモリ参照データ型のサイズが言語内でアクセス可能であるためです。しかし、Pascalのような他のプログラミング言語にはこの機能がないため、原理的にはチューリング完全です。プログラミング言語ではメモリ割り当てが失敗することが許容されるため、プログラミング言語は失敗したメモリ割り当てを無視すればチューリング完全になりますが、実際のコンピュータで実行可能なコンパイル済みプログラムはそうではありません。

チューリングは論文（1936年）の冒頭で、「自動機械」（その「動作は構成によって完全に決定される」）と「選択機械」を区別している。

… その動作は構成によって部分的にしか決定されない…このような機械が曖昧な構成のいずれかに到達すると、外部のオペレータによって何らかの任意の選択が行われるまで、先に進むことができない。これは、公理系を扱うために機械を使用する場合に当てはまる。

チューリング（1936）は、選択マシンを使用する代わりに a マシンを使用して「[ヒルベルト] 計算のすべての証明可能な式を見つける」方法を説明した脚注を除いて、それ以上詳しく説明していません。彼は「選択は常に 0 と 1 の 2 つの可能性の間にあると仮定します。各証明は、選択のシーケンス i ₁、 i ₂、 ...、 i _n (i ₁ = 0 または 1、 i ₂ = 0 または 1、 ...、 i _n = 0 または 1) によって決定され、したがって、数 2 ⁿ + i ₁ 2 ^n-1 + i ₂ 2 ^n-2 + ... +i _nによって証明が完全に決定されます。自動マシンは、証明 1、証明 2、証明 3、... を順次実行します」^{[ 39 ]}

これはまさに、決定論的（つまり非決定論的）チューリングマシンを用いて非決定論的チューリングマシンの動作を模倣する手法である。チューリングはこの問題を脚注で解決し、それ以上の検討対象から除外したようである。

オラクルマシンまたはoマシンは、チューリングaマシンの一種で、計算を完了するために「オラクル」の「決定」を待つ間、状態「o 」で計算を一時停止する。オラクルとは、チューリングが「機械ではない」と述べる以外には特定していない存在である（チューリング（1939））。^{[ 40 ]}

チューリングは『決定不能なもの』の中で次のように書いています（強調追加）：^{[ 41 ]}

任意の計算可能な数列を計算できる単一の機械を発明することは可能である。この機械Uに、ある計算機Mのセミコロンで区切られた 5 組の文字列が先頭に書き込まれたテープを与えると、U はMと同じ数列を計算する。

チューリングが「ユニバーサルマシン」（略して「 U 」）と呼んだ計算モデルは、一部の人々 ^{[ 42 ]}によって、プログラム内蔵型コンピュータの概念につながった根本的な理論的ブレークスルーであると考えられている。

チューリングの論文には、本質的に現代のコンピュータの発明と、それに伴うプログラミング技術の一部が含まれている。

計算複雑性の観点から言えば、マルチテープ万能チューリングマシンは、シミュレートするマシンと比較して対数係数だけ遅くなればよい。この結果は、1966 年に FC Hennie とRE Stearnsによって得られた。^{[ 44 ] [ 45 ]}

チューリングマシンは、有限状態機械やプッシュダウンオートマトンなど、他の種類のオートマトンよりも強力です。チャーチ＝チューリングのテーゼによれば、チューリングマシンは実機と同等の能力を持ち、実機プログラムが実行できるあらゆる操作を実行できます。しかし、この主張で見落とされているのは、実機は有限個の構成しか持たないため、有限状態機械に過ぎないのに対し、チューリングマシンは計算に利用できる記憶領域が無限にあるということです。

チューリングマシンが実際のコンピュータの有用なモデルである理由を説明する方法はいくつかあります。

• 実際のコンピュータが計算できるものはすべて、チューリングマシンでも計算できます。例えば、「チューリングマシンは、再帰的な手続きや既知のパラメータ渡しメカニズムなど、プログラミング言語に見られるあらゆる種類のサブルーチンをシミュレートできます」（Hopcroft and Ullman、 157ページ）。十分な大きさの有限状態オートマトン（FSA）であれば、入出力（IO）を無視すれば、実際のコンピュータをモデル化することもできます。したがって、チューリングマシンの限界に関する記述は、実際のコンピュータにも当てはまります。
• 違いは、チューリングマシンが無制限の量のデータを操作できるという点のみにある。しかし、有限の時間という制約の下では、チューリングマシン（実際の機械と同様に）は有限量のデータしか操作できない。
• チューリングマシンと同様に、実際の機械も必要に応じて、ディスクやその他の記憶媒体を追加することで、記憶容量を拡張することができる。
• より単純な抽象モデルを用いた実機プログラムの記述は、チューリングマシンを用いた記述よりもはるかに複雑になることが多い。例えば、アルゴリズムを記述するチューリングマシンは数百の状態しか持たないのに対し、実機上の同等の決定性有限オートマトン（DFA）は数千兆の状態を持つ。そのため、DFA表現の解析は不可能となる。
• チューリングマシンは、使用するメモリ量に関係なくアルゴリズムを記述します。現在のどのマシンにもメモリ容量には限界がありますが、この限界は時間とともに任意に増加させることができます。チューリングマシンを用いることで、従来のコンピュータアーキテクチャの進歩に関わらず、（理論的には）永続的に成り立つアルゴリズムに関する記述が可能になります。
• チューリング等価な抽象マシン上で実行されるアルゴリズムは、任意精度データ型を利用でき、予期せぬ状況（メモリ不足を含むが、これに限定されない）に対処する必要がない。

計算の算術モデルは、チューリングモデルとは2つの点で異なります。^{[ 46 ]}

• 算術モデルでは、すべての実数に単一のメモリセルが必要であるのに対し、チューリングモデルでは、実数の記憶容量は、それを表現するために必要なビット数によって決まる。
• 算術モデルでは、実数に対する基本的な算術演算（加算、減算、乗算、除算）はすべて1ステップで実行できますが、チューリングモデルでは、各算術演算の実行時間はオペランドの長さに依存します。

あるアルゴリズムは、一方のモデルでは多項式時間で実行されるが、もう一方のモデルではそうではない。例えば、次のようになる。

• ユークリッドアルゴリズムはチューリングモデルでは多項式時間で実行されるが、算術モデルではそうではない。
• n個の数値を読み込んで計算するアルゴリズム${\displaystyle 2^{2^{n}}}$算術モデルでは、繰り返し二乗演算を行うことで多項式時間で実現できるが、チューリングモデルではそうではない。これは、結果を表すために必要なビット数が入力サイズに対して指数関数的に増加するためである。

しかし、アルゴリズムが算術モデルにおいて多項式時間で実行され、かつ、関連するすべての数値の2進数の長さが入力の長さの多項式である場合、そのアルゴリズムはチューリングモデルにおいても常に多項式時間で実行されます。このようなアルゴリズムは、強多項式時間で実行されると言われます。