チューリングマシン

Mike Davey 氏が構築した物理的なチューリングマシンモデル。真のチューリングマシンでは、必要に応じてより多くのメモリ（テープ）を搭載する必要があります。物理モデルではメモリ容量に限りがあります。

オートマトンの種類

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

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

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

• テープ上の任意のマシンが「循環的」であるかどうか (たとえば、フリーズするか、計算タスクを続行できないか) を判断できるマシンは存在しますか?
• テープ上の任意のマシンが特定のシンボルを印刷するかどうかを判断できるマシンは存在するでしょうか？^{[ 14 ] [ 15 ]}

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

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

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

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

概要

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

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

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

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

身体的特徴

チューリングは 1948 年のエッセイ「インテリジェント マシナリー」の中で、彼のマシンは次のような構成になっていると書いています。

…無限の記憶容量は、正方形に区切られた無限のテープという形で得られ、それぞれのテープには記号が印刷できる。機械には常に1つの記号が存在している。それはスキャン記号と呼ばれる。機械はスキャン記号を変更でき、機械の動作はその記号によって部分的に決定されるが、テープ上の他の場所にある記号は機械の動作に影響を与えない。しかし、テープは機械内を前後に動かすことができ、これは機械の基本操作の一つである。したがって、テープ上のどの記号も最終的にはイニングを持つ可能性がある。^{[ 17 ]}

— チューリング 1948 ^{[ 18 ]}

説明

チューリングマシンは、テープ上で機械的に動作する機械を数学的にモデル化したものです。このテープには記号が記録されており、機械はテープヘッドを用いて記号を1つずつ読み書きすることができます。動作は、「状態42において、記号が0であれば1を書き込む。記号が1であれば状態17に遷移する。状態17において、記号が0であれば1を書き込んで状態6に遷移する」といった、有限の基本命令の集合によって完全に決定されます。原著論文（「計算可能数について、計算問題への応用」、以下の参考文献も参照）では、チューリングは機械ではなく、これらの決定論的な機械的規則を奴隷のように（あるいはチューリング自身の言葉を借りれば「散漫なやり方で」）実行する「コンピュータ」と呼ぶ人物を想像しています。

ヘッドは常にテープ上の特定のマス目上にあり、マス目は有限の範囲のみで表示されます。機械の状態（q ₄）は、処理対象のマス目上に表示されます。（Kleene (1952) p. 375 に基づく図）

ここでは、内部状態 (q ₁ ) がヘッド内部に示されており、図ではテープが無限大で「0」があらかじめ入力されており、記号は空白として機能していることを示しています。システムの完全な状態（「完全な構成」）は、内部状態、テープ上の空白以外の記号（この図では「11B」）、そして空白を含む記号に対するヘッドの相対的な位置（つまり「011B」）で構成されます。（ミンスキー (1967) p. 121 に基づく図）

より具体的に言えば、チューリング マシンは次の要素で構成されます。

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

1. シンボルを消去するか書き込みます ( _jをj1に置き換えます)。
2. 頭を移動します (これは d _kで表され、次の値を取ることができます: 左に 1 歩の場合は 'L' 、右に1 歩の場合は 'R' 、同じ場所に留まる場合は 'N')。
3. 規定どおりに同じ状態または新しい状態を想定します（状態 q _i1に進みます）。

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

マシンのあらゆる部分 (つまり、その状態、シンボル コレクション、特定の時点での使用済みテープ) とそのアクション (印刷、消去、テープ動作など) は、有限で、個別かつ区別可能です。無制限の量のテープと実行時間によって、マシンに無制限の量のストレージ スペースが提供されます。

正式な定義

ホップクロフトとウルマン（1979）に従って、^{[ 21 ]}（1テープ）チューリングマシンは、7つの組 で定義され、 ${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$

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

3 ステートのビジービーバー。黒いアイコンはヘッドの位置と状態を表します。四角い色は 1（オレンジ）と 0（白）を表します。時間は上から下に向かって垂直に進み、下のHALT状態まで続きます。

変形では、方向セットの 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 q_{0}={\mbox{A}}}$ （初期状態）
• ${\displaystyle F=\{{\mbox{HALT}}\}}$ （最終状態）
• ${\displaystyle \delta =}$ 下記の状態表（遷移関数）を参照してください。

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

3状態、2シンボルのビジービーバーの状態表

テープ記号	現在の状態A			現在の状態B			現在の状態C
	記号を書く	テープを移動する	次の州	記号を書く	テープを移動する	次の州	記号を書く	テープを移動する	次の州
0	1	R	B	1	L	あ	1	L	B
1	1	L	C	1	R	B	1	R	停止

チューリングマシンを視覚化または実装するために必要な追加の詳細

ファン・エムデ・ボアズ（1990）の言葉を借りれば、「集合論的オブジェクト（上記と同様の7組の形式的記述）は、マシンがどのように動作するか、その計算がどのようになるかについて部分的な情報しか提供しない。」^{[ 23 ]}

例えば、

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

代替定義

文献における定義は、議論や証明を分かりやすくするために、多少異なる場合もありますが、これは常に、結果として得られるマシンの計算能力が同じになるように行われます。例えば、集合を から に変更することができます。ここで、N（「なし」または「操作なし」）は、マシンが左または右に移動するのではなく、同じテープセルに留まることを意味します。これにより、マシンの計算能力は向上しません。 ${\displaystyle \{L,R\}}$ ${\displaystyle \{L,R,N\}}$

最も一般的な慣例は、チューリング/デイビスの慣例（チューリング（1936）^{[ 24 ]}およびデイビス（2000）^{[ 25 ]}）に従って、「チューリングテーブル」内の各「チューリング命令」を9つの5組のうちの1つで表すものである。

（定義1）: （q _i、S _j、S _k /E/N、L/R/N、q _m）

(現在の状態q _i、スキャンされたシンボルS _j、印刷シンボルS _k /消去E /なしN 、テープを1マス左に移動L /右R /なしN 、新しい状態q _m )

他の著者（ミンスキー（1967）、^{[ 26 ]}ホップクロフトとウルマン（1979）、^{[ 27 ]}ストーン（1972）、^{[ 28 ]）}は異なる規則を採用しており、新しい状態q _mはスキャンされたシンボルS _jの直後にリストされます。

（定義2）: （q _i、S _j、q _m、S _k /E/N、L/R/N）

(現在の状態q _i、スキャンされたシンボルS _j、新しい状態q _m、印刷シンボルS _k /消去E /なしN 、テープを1マス左に移動L /右R /なしN )

この記事の残りの部分では、「定義 1」(チューリング/デイビス規則) を使用します。

例: 3状態2シンボルビジービーバーの状態表を5タプルに縮小

現在の状態	スキャンされたシンボル	印刷記号	テープを移動する	最終（つまり次の）状態	5タプル
あ	0	1	R	B	（A、0、1、R、B）
あ	1	1	L	C	（A、1、1、L、C）
B	0	1	L	あ	（B、0、1、L、A）
B	1	1	R	B	（B、1、1、R、B）
C	0	1	L	B	（C、0、1、L、B）
C	1	1	北	H	（C、1、1、N、H）

次の表では、チューリングのオリジナルモデルでは最初の3行のみが許可されており、彼はこれをN1、N2、N3と呼んでいました。^{[ 29 ]}彼は、0番目のシンボルS0を「消去」または「空白」などと名付けることで、「スキャンされた正方形」の消去を_許可しました。しかし、印刷しないことは許可しなかったため、すべての命令行には「印刷シンボルSk _」または「消去」が含まれています。^{[ 31 ]}略語はチューリングによるものです。^{[ 32 ]}チューリングの1936年から1937年のオリジナル論文以降、マシンモデルでは5組の可能な9つのタイプすべてが許可されています。

	現在のm構成（チューリング状態）	テープ記号	印刷操作	テープモーション	最終的なm構成（チューリング状態）	5タプル	5タプルコメント	4タプル
N1	q i	S j	印刷(S k )	左L	q m	（q i、S j、S k、L、q m）	「空白」= S 0、1=S 1など。
N2	q i	S j	印刷(S k )	右R	q m	（q i、S j、S k、R、q m）	「空白」= S 0、1=S 1など。
N3	q i	S j	印刷(S k )	なし N	q m	（q i、S j、S k、N、q m）	「空白」= S 0、1=S 1など。	（q i、S j、S k、q m）
4	q i	S j	なし N	左L	q m	（q i、S j、N、L、q m）		（q i、S j、L、q m）
5	q i	S j	なし N	右R	q m	（q i、S j、N、R、q m）		（q i、S j、R、q m）
6	q i	S j	なし N	なし N	q m	（q i、S j、N、N、q m）	直接的な「ジャンプ」	（q i、S j、N、q m）
7	q i	S j	消去	左L	q m	（q i、S j、E、L、q m）
8	q i	S j	消去	右R	q m	（q i、S j、E、R、q m）
9	q i	S j	消去	なし N	q m	（q i、S j、E、N、q m）		（q i、S j、E、q m）

任意のチューリングテーブル（命令のリスト）は、上記の9つの5組から構成できます。技術的な理由により、3つの非印字命令（「N」）（4、5、6）は通常省略できます。例については、チューリングマシンの例を参照してください。

あまり頻繁ではないが、4タプルの使用も見られる。これはチューリング命令のさらなる細分化を表している。^{[ 33 ]}

「国家」

チューリングマシンの文脈で使われる「状態」という言葉は、二つの意味を持つため、混乱を招く可能性があります。チューリング以降の多くの評論家は、「状態」を現在実行されている命令の名前／指示子、つまり状態レジスタの内容の意味で用いてきました。しかし、チューリング（1936）は、彼が「m-構成」と呼んだ機械の記録と、計算過程における機械（または人間）の「進行状態」、つまりシステム全体の現在の状態を明確に区別しました。チューリングが「状態式」と呼んだものには、現在の命令とテープ上のすべてのシンボルの両方が含まれます。

このように、計算の進行状態は、どの段階においても、テープ上の指示記号と記号によって完全に決定されます。つまり、システムの状態は、テープ上の記号、Δ（他の場所には現れないことが想定されています）、そして指示記号からなる単一の式（記号列）で記述できます。この式は「状態式」と呼ばれます。

— 『The Undecidable』、139～140ページ、^{[ 34 ]}強調追加

チューリングは論文の前半でこれをさらに進め、現在の「m構成」のシンボル（命令のラベル）を、テープ上のすべてのシンボルとともにスキャンした四角形の下に配置した例を挙げています。^{[ 35 ]}彼はそれを「完全な構成」と呼んでいます。^{[ 36 ]}「完全な構成」を1行に印刷するために、彼は状態ラベル/m構成をスキャンしたシンボルの 左側に配置しています。

この変種はクリーネ（1952）に見られる。クリーネは、機械の「状況」のゲーデル数の書き方を示している。彼は「m構成」記号q ₄を、テープ上の6つの非空白マス目のほぼ中央に位置するスキャンされたマス目の上に置き（本稿のチューリングテープ図を参照）、スキャンされたマス目の右側に配置する。^{[ 37 ]}しかし、クリーネは「q ₄」自体を「機械状態」と呼んでいる。ホップクロフトとウルマンはこの複合体を「瞬間記述」と呼び、「現在の状態」（命令ラベル、m構成）をスキャンされた記号の左側に置くというチューリングの慣例に従っている（p. 149）。つまり、瞬間記述は、左側の非空白記号、機械の状態、ヘッドによってスキャンされた現在の記号、そして右側の非空白記号の複合体である。

例: 3 回の「移動」後の 3 状態 2 シンボルのビジー ビーバーの合計状態(下の図の「実行」例から抜粋):

1 A 1

これは、3回移動した後、テープには ... 000110000 ... が記録され、ヘッドは右端の 1 をスキャンしており、状態はAであることを意味します。空白（この場合は「0」で表されます）は、以下の例のように全体の状態の一部となる場合があります：B 01; テープには 1 が 1 個記録されていますが、ヘッドはその左側の 0（「空白」）をスキャンしており、状態はBです。

チューリング マシンのコンテキストにおける「状態」は、現在の命令が記述されているのか、現在の命令と一緒にテープ上のシンボルのリストが記述されているのか、スキャンされたシンボルの左側またはスキャンされたシンボルの右側に配置された現在の命令と一緒にテープ上のシンボルのリストが記述されているのかを明確にする必要があります。

「状態」図

3 状態ビジー ビーバーのテーブル (「P」=「1」を印刷/書き込み)

テープ記号	現在の状態A			現在の状態B			現在の状態C
	記号を書く	テープを移動する	次の州	記号を書く	テープを移動する	次の州	記号を書く	テープを移動する	次の州
0	P	R	B	P	L	あ	P	L	B
1	P	L	C	P	R	B	P	R	停止

有限状態表現における「3状態ビジービーバー」チューリングマシン。各円は表の「状態」（「m構成」または「命令」）を表す。状態遷移の「方向」は矢印で示される。出力状態（矢印の「末尾」）の近くのラベル（例：0/P,R ）は、特定の遷移を引き起こすスキャンされたシンボル（例： 0）とそれに続くスラッシュ（ / ）を示し、その後にマシンの「動作」（例：「P印刷」、次にテープ「R右へ」）が続く。一般に受け入れられている形式は存在しない。示されている表記法は、McClusky (1965)、Booth (1967)、Hill、およびPeterson (1974)に従っている。

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

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

図面がその表の改良点を表すかどうかは、特定のコンテキストに応じて読者が判断する必要があります。

忙しいビーバーの計算の進化は上から始まり、下へと進みます。

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

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

同等のモデル

単純な汎用チューリングマシンよりも高い計算能力を持つと考えられる多くのマシンは、実際にはそれ以上の能力を持たないことが示されています (Hopcroft and Ullman p. 159、Minsky (1967) 参照)。それらのマシンは、おそらくより高速に計算したり、メモリ使用量を少なくしたり、命令セットを小さくしたりすることはできるかもしれませんが、より強力な計算能力（つまり、より多くの数学的関数）を持つことはできません。(チャーチ＝チューリングのテーゼは、あらゆる種類のマシンについてこれが成り立つと仮定しています。つまり、「計算」できるものはすべて、何らかのチューリングマシンで計算できるということです。)

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

その反対に、非常に単純なモデルの中にはチューリングと同等、つまりチューリング マシン モデルと同じ計算能力を持つものがあることが判明しています。

一般的な同等のモデルとしては、マルチテープ チューリング マシン、マルチトラック チューリング マシン、入力と出力を持つマシン、およびアクション テーブルにシンボルと状態の組み合わせごとに最大 1 つのエントリが含まれる決定性チューリング マシン(DTM ) とは対照的な非決定性チューリング マシン (NDTM) などがあります。

読み取り専用の右向きのチューリング マシンは、DFAと同等です( NFA から DFA への変換アルゴリズムを使用して変換するとNFAと同等になります)。

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

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

チョイスCマシン、オラクルOマシン

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

…その動作は構成によって部分的にしか決定されない…このような機械がこうした曖昧な構成のいずれかに達すると、外部の操作者によって何らかの恣意的な選択が行われるまで動作を続けることはできない。これは、機械を用いて公理系を扱う場合に当てはまる。

— 『決定できないもの』118ページ^{[ 36 ]}

チューリング（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 ]。}

これはまさに、決定論的 (つまり a-) チューリング マシンを使用して非決定論的チューリング マシンの動作を模倣する手法です。チューリングは脚注でこの問題を解決し、それ以上の検討は行わないようです。

オラクルマシンまたはoマシンは、計算を状態「o」で一時停止し、計算を完了するために「オラクル」の「決定を待つ」チューリングaマシンです。オラクルとは、チューリングによって「マシンではないと述べていること以外は」明確にされていない実体です（チューリング（1939））。^{[ 40 ]}

ユニバーサルチューリングマシン

チューリングマシンの実装

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

任意の計算可能なシーケンスを計算できる単一のマシンを発明することは可能です。このマシンUに、ある計算機Mのセミコロンで区切られた5つの要素からなる文字列が先頭に書き込まれたテープが供給された場合、U はMと同じシーケンスを計算します。

この発見は今では当然のこととされていますが、当時（1936年）は驚くべきものでした。チューリングが「万能機械」（略して「U 」）と呼んだ計算モデルは、一部の人々 ^{[ 42 ]}によって、プログラム内蔵型コンピュータの概念につながる根本的な理論的ブレークスルーであったと考えられています。

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

— ミンスキー（1967）^{[ 43 ]}

計算量の観点から言えば、マルチテープ型汎用チューリングマシンは、シミュレートするマシンと比較して対数係数だけ遅くなるだけで十分である。この結果は1966年にFC HennieとR.E. Stearnsによって得られた。^{[ 44 ] [ 45 ]}

実機との比較

レゴピースを使ったチューリングマシンの実現

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

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

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

制限事項

計算複雑性理論

チューリングマシンの限界は、特定の構成の長所をうまくモデル化できないことです。例えば、現代のプログラム内蔵型コンピュータは、実際にはランダムアクセスプログラム内蔵型マシン、あるいはRASPマシンモデルと呼ばれる、より具体的な抽象マシンのインスタンスです。汎用チューリングマシンと同様に、RASPは「プログラム」を有限状態マシンの「命令」とは別の「メモリ」に格納します。汎用チューリングマシンとは異なり、RASPは識別可能で番号が付けられているものの境界のない無限数の「レジスタ」、つまり任意の整数を格納できるメモリ「セル」を備えています（Elgot and Robinson (1964)、Hartmanis (1971)、特にCook-Rechow (1973)を参照。ランダムアクセスマシンの参考文献を参照）。RASPの有限状態マシンは間接アドレス指定機能を備えています（例えば、あるレジスタの内容を別のレジスタを指定するためのアドレスとして使用できます）。したがって、RASPの「プログラム」はレジスタシーケンス内の任意のレジスタをアドレス指定できます。この区別の結果、メモリインデックスに基づいて実行できる計算最適化が存在することになりますが、これは一般的なチューリングマシンでは不可能です。したがって、チューリングマシンを計算時間の制限の基準として使用すると、特定のアルゴリズムの実行時間について「誤った下限」が証明される可能性があります（チューリングマシンの誤った単純化仮定による）。その一例が二分探索です。このアルゴリズムは、チューリングマシンモデルではなくRASP計算モデルを使用した場合、より高速に実行できることが示されています。

交流

コンピュータの黎明期には、コンピュータの利用は典型的にはバッチ処理、つまり与えられた入力データから出力データを生成する非対話型タスクに限られていました。入力から出力への関数の計算可能性を研究する計算可能性理論は、チューリングマシンの発明の源であり、この慣習を反映しています。

1970年代以降、コンピュータのインタラクティブな利用ははるかに一般的になりました。原理的には、チューリングマシンのように外部エージェントがテープからの読み取りと書き込みを同時に行うことでこれをモデル化することは可能ですが、これが実際のインタラクションの仕組みと一致することは稀です。そのため、インタラクティブ性を記述する際には、I/Oオートマトンなどの代替手段が一般的に好まれます。

計算の算術モデルとの比較

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

• 算術モデルでは、すべての実数に 1 つのメモリセルが必要ですが、チューリングモデルでは、実数のストレージサイズは、それを表すために必要なビット数によって決まります。
• 算術モデルでは、実数に対するすべての基本的な算術演算 (加算、減算、乗算、除算) を 1 ステップで実行できますが、チューリング モデルでは、各算術演算の実行時間はオペランドの長さに依存します。

一部のアルゴリズムは、あるモデルでは多項式時間で実行できるものの、別のモデルでは実行できないことがあります。例えば、

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

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

歴史

歴史的背景: 計算機

アラン・チューリング（1912年 - 1954年）の弟子であり、生涯の友人でもあったロビン・ガンディ（1919年 - 1995年）は、「計算機」という概念の系譜をチャールズ・バベッジ（1834年頃）まで遡り、「バベッジのテーゼ」を提唱しています。

分析の開発と操作のすべてが機械によって実行可能になったこと。

— （バベッジの引用、ガンディによる強調）^{[ 47 ]}

ガンディによるバベッジの解析エンジンの分析では、次の 5 つの操作が説明されています (52 ～ 53 ページを参照)。

1. 算術関数 +、−、×。ここで、− は「適切な」減算を示します。y ≥ xの場合、 x − y = 0 となります。
2. 一連の操作はすべて操作です。
3. 操作の反復（操作 P を n 回繰り返す）。
4. 条件付き反復 (テスト T の「成功」を条件として操作 P を n 回繰り返す)。
5. 条件付き転送（つまり、条件付き「goto」）。

ガンディは「(1)、(2)、(4)で計算できる関数はまさにチューリング計算可能な関数である」と述べている。^{[ 48 ]}彼は「汎用計算機」に関する他の提案として、パーシー・ラドゲート（1909年）、レオナルド・トーレス・ケヴェド（1914年）、^{[ 49 ] [ 50 ]}モーリス・ドカーニュ（1922年）、ルイ・クフィニャル（1933年）、ヴァネヴァー・ブッシュ（1936年）、ハワード・エイケン（1937年）らの提案を挙げている。しかしながら、

… 固定された反復可能な算術演算シーケンスのプログラミングに重点が置かれています。計算機の一般理論における条件付き反復と条件付き転送の根本的な重要性は認識されていません…

— ガンディ^{[ 51 ]}

決定問題（Entscheidungsproblem）：1900年のヒルベルトの10番目の問題

1900年に著名な数学者ダヴィド・ヒルベルトが提起したヒルベルトの問題に関して言えば、問題10のある側面は、正確に定式化されるまでほぼ30年間議論されていました。ヒルベルトによる問題10の元の表現は次のとおりです。

10. ディオファントス方程式の可解性の判定。任意の数の未知数と有理整数係数を持つディオファントス方程式が与えられた場合、その方程式が有理整数で解けるかどうかを有限回の演算で判定できる手順を考案する。一階述語論理における判定問題（Entscheidungsproblem ）は、任意の論理式について有限回の演算でその妥当性または充足可能性を判定できる手順が分かれば解決される。… Entscheidungsproblemは数理論理学の主要問題とみなされなければならない。

— この翻訳とオリジナルのドイツ語は、Dershowitz and Gurevich, 2008 ^{[ 52 ]に引用されている。}

1922年までにこの「Entscheidungsproblem」という概念は少し発展し、H.ベーマンは次のように述べた。

... Entscheidungsproblem の最も一般的な形式は次のとおりです。

与えられた純粋に論理的な主張が真であるか偽であるかを有限の数のステップで判断できるようにする、非常に明確で一般に適用可能な処方箋が必要です...

— ガンディ^{[ 53 ]}ベーマンの言葉を引用

ベーマンは、...一般的な問題は、どの数学的命題が真であるかを決定する問題と同等であると述べています。

— 同上

Entscheidungsproblem を解くことができれば、「多くの (またはすべての) 数学的問題を解く手順」が得られることになります。

— 同上^{[ 54 ]}

1928年の国際数学者会議までに、ヒルベルトは「疑問をかなり明確にした。第一に、数学は完全か...第二に、数学は矛盾がないか...そして第三に、数学は決定可能か?」^{[ 55 ] [ 56 ]}最初の2つの疑問は、1930年にクルト・ゲーデルによって、ヒルベルトが引退演説を行ったまさにその会議で答えられた(ヒルベルトにとっては大変残念なことだった)。3番目の疑問、すなわち決定問題(Entscheidungsproblem)は、1930年代半ばまで待たなければならなかった。

問題は、答えを出すにはまず「明確で一般的に適用可能な処方箋」の正確な定義が必要だったことであり、プリンストン大学のアロンゾ・チャーチ教授はこれを「実効計算可能性」と呼ぶことになるが、1928年当時はそのような定義は存在しなかった。しかしその後6～7年かけて、エミール・ポストは、作業員が部屋から部屋へと移動しながら指示リストに従って印をつけたり消したりするという定義を発展させた^{[ 57 ]。}チャーチと彼の2人の学生、スティーブン・クリーネとJBロッサーも、チャーチのラムダ計算とゲーデルの再帰理論を用いて同様の定義を発展させた（1934年）。チャーチの論文（1936年4月15日発表）は、決定問題がまさに「決定不能」であることを示し^{[ 58 ]}、チューリングよりほぼ1年も早く結論を出した（チューリングの論文は1936年5月28日提出、1937年1月発表）。その間に、エミール・ポストが1936年秋に短い論文を提出したため、チューリングは少なくともポストよりも優先権を得た。チャーチがチューリングの論文を査読している間、チューリングはチャーチの論文を検討し、付録にチャーチのラムダ計算と彼のマシンが同じ関数を計算できることの証明を概説した。

しかし、チャーチがやったことはかなり違ったもので、ある意味ではより弱いものだった。...チューリングの構築はより直接的で、第一原理からの議論を提供し、チャーチの証明のギャップを埋めた。

— ホッジス^{[ 9 ]}

そしてポストは計算可能性の定義を提案し、チャーチの「定義」を批判しただけで、何も証明していなかった。

アラン・チューリングのa-マシン

1935 年の春、ケンブリッジ大学キングス・カレッジの若き修士課程の学生として、チューリングは挑戦を受けました。彼は論理学者MHA ニューマンの講義に刺激を受け、「ゲーデルの研究と『結論問題』について学びました...ニューマンは「機械的な」という言葉を使いました...1955 年のチューリングの死亡記事で、ニューマンは次のように書いています。

「『機械的な』プロセスとは何か？」という質問に対して、チューリングは「機械で実行できるもの」という特徴的な答えを返し、計算機の一般的な概念を分析するという非常に興味深い作業に着手しました。

— ガンディ^{[ 59 ]}

ガンディ氏は次のように述べています。

チューリングは研究の当初から、決定問題の決定不可能性を証明することを目標としていたのではないかと推測しますが、確証はありません。彼は私に、論文の「主要なアイデア」は1935年の夏、グランチェスターの牧草地に横たわっていた時に思いついたと言っていました。その「主要なアイデア」とは、計算の分析だったのかもしれませんし、あるいは万能機械の存在、そしてそれゆえに解決不可能性を証明するための対角線論法の存在に気づいたことだったのかもしれません。

— 同上^{[ 60 ]}

ガンディはニューマンの上記の発言は「誤解を招く」と考えていたが、この意見は必ずしもすべての人に当てはまるわけではない。チューリングは生涯にわたって機械に興味を持っていた。「アランは少年時代、タイプライターを発明することを夢見ていた。[彼の母]チューリング夫人はタイプライターを持っていた。そして彼は、タイプライターを『機械式』と呼ぶことの意味を自問することから始めたのかもしれない」(Hodges p. 96)。プリンストン大学で博士号取得を目指していた頃、チューリングはブール論理乗算器を製作した(下記参照)。彼の博士論文「順序数に基づく論理体系」には、「計算可能な関数」の以下の定義が含まれている。

上で「関数は、その値が何らかの純粋に機械的なプロセスによって求められる場合、実効的に計算可能である」と述べた。この記述を文字通りに解釈し、純粋に機械的なプロセスとは、機械によって実行可能なプロセスであると理解することができる。これらの機械の構造は、ある標準的な形式で数学的に記述することができる。これらの概念を発展させることで、著者は計算可能関数を定義し、計算可能性と実効的計算可能性を同一視する。これらの3つの定義（3つ目はλ計算）が同等であることを証明するのは、多少骨の折れるものではあるが、難しくはない。

— チューリング（1939年、166ページ）^{[ 61 ]}

アラン・チューリングは1936年に「a-マシン」（自動機械）を発明した。^{[ 7 ]}チューリングは1936年5月31日にロンドン数学会の会報に論文を提出したが^{[ 62 ]}、それが出版されたのは1937年初頭で、抜刷りが1937年2月に入手可能になった。^{[ 63 ]}後に「チューリングマシン」という用語を作ったのは、チューリングの博士課程の指導教官であったアロンゾ・チャーチであった。^{[ 13 ]}このモデルによって、チューリングは以下の2つの疑問に否定的な答えを出すことができた。

• テープ上の任意のマシンが「循環的」であるかどうか (たとえば、フリーズするか、計算タスクを続行できないか) を判断できるマシンは存在しますか?
• テープ上の任意のマシンが特定のシンボルを印刷するかどうかを判断できるマシンは存在するでしょうか？^{[ 14 ] [ 15 ]}

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

チューリングは英国に戻ると、最終的に「エニグマ」と呼ばれる暗号機によって生成されたドイツの秘密暗号解読の共同責任者となった。また、ACE（自動計算エンジン）の設計にも関わった。「[チューリングの]ACE提案は事実上自己完結的であり、その根源はEDVAC （米国の構想）ではなく、彼自身の汎用機械にあった」（Hodges p. 318）。クリーネ（1952）の「チューリングのテーゼ」で名付けられたものの起源と性質については、現在も議論が続いている。しかし、チューリングが自身の計算機械モデルで証明したことは、論文「計算可能数について、そして計算問題への応用」（1937）に記されている。

ヒルベルトの証明問題には解が存在しない...したがって、関数計算 K の特定の式 U が証明可能かどうかを判断する一般的なプロセスは存在しないこと、つまり、これらの式のいずれか 1 つの U を供給されたときに、U が証明可能かどうかを最終的に判断する機械は存在しないことを示すことを提案します。

— チューリングの論文より転載、The Undecidable、p. 145 ^{[ 64 ]}

チューリングの例 (彼の 2 番目の証明): 「このマシンは 0 を出力することがあるか」を判断するための一般的な手順を求める場合、その質問は「決定不可能」です。

1937年～1970年：「デジタルコンピュータ」、コンピュータサイエンスの誕生

1937年、プリンストン大学で博士論文に取り組んでいたチューリングは、独自の電気機械式リレーを用いて、デジタル（ブール論理）乗算器をゼロから構築しました（Hodges p. 138）。「アランの課題は、チューリングマシンの論理設計をリレー駆動スイッチのネットワークに具体化することだった…」（Hodges p. 138）。チューリングは当初、単なる好奇心と実験にとらわれていたかもしれませんが、ドイツではコンラート・ツーゼ（1938年）、アメリカ合衆国ではハワード・エイケンとジョージ・スティビッツ（1937年）が、同じ方向への真剣な研究を進めていました。彼らの研究成果は、第二次世界大戦において枢軸軍と連合軍の両方で使用されました（Hodges p. 298–299参照）。 1950年代初頭から中期にかけて、ハオ・ワンとマービン・ミンスキーはチューリングマシンをより単純な形（マーティン・デイヴィスのポスト・チューリングマシンの前身）に縮小しました。同時に、ヨーロッパの研究者たちは、当時まだ新しかった電子計算機を、現在「チューリングマシン」と呼ばれているものに相当するコンピュータ的な理論的対象へと縮小していきました。1950年代後半から1960年代初頭にかけて、メルザックとラムベック（1961年）、ミンスキー（1961年）、シェパードソンとスタージス（1961年）による偶然にも同時進行した開発によって、ヨーロッパの研究はさらに進展し、チューリングマシンはカウンタマシンと呼ばれる、より扱いやすくコンピュータ的な抽象モデルへと縮小されました。エルゴットとロビンソン（1964年）、ハートマニス（1971年）、クックとレックハウ（1973年）は、レジスタマシンとランダムアクセスマシンのモデルを用いてこの研究をさらに進めましたが、基本的にはすべて、算術演算のような命令セットを備えたマルチテープ・チューリングマシンに過ぎません。

1970年～現在: 計算モデルとして

今日でも、カウンタ、レジスタ、ランダムアクセスマシン、そしてそれらの祖先であるチューリングマシンは、計算理論における問題を研究する理論家にとって、依然として最適なモデルであり続けています。特に、計算複雑性理論ではチューリングマシンが用いられています。

計算で操作したいオブジェクト（非負の整数や英数字の文字列などの数値）に応じて、機械ベースの複雑性理論では次の 2 つのモデルが支配的な地位を獲得しています。

オフライン マルチテープ チューリング マシンは、文字列指向の計算の標準モデルを表します。また、 Cook と Reckhow によって導入されたランダム アクセス マシン (RAM)は、理想的なフォン ノイマン スタイルのコンピュータをモデル化します。

— ヴァン・エムデ・ボアス (1990) ^{[ 65 ]}

アルゴリズムの分析の関連領域でのみ、この役割は RAM モデルによって引き継がれます。

— ヴァン・エムデ・ボアス (1990) ^{[ 66 ]}

参照

• 算術階層
• ベッケンシュタイン限界は、有限サイズと有限エネルギーの無限テープチューリングマシンの不可能性を示す。
• BlooPとFlooP
• 停止問題に関する情報については、チャイティン定数またはオメガ（コンピュータサイエンス）を参照してください。
• 微積分推論器
• 中華風の部屋
• コンウェイのライフゲーム、チューリング完全なセルオートマトン
• デジタル無限
• 皇帝の新たな心
• 調査員（コンピュータサイエンス）
• ジェネティクス
• ゲーデル、エッシャー、バッハ：永遠の黄金の紐、チャーチ＝チューリングのテーゼなどについて論じた有名な本
• 停止問題、詳細については
• ハーバード建築学
• 命令型プログラミング
• ラングトンのアントとターミテス、チューリングマシンの単純な2次元類似体
• アラン・チューリングにちなんで名付けられたもののリスト
• 改良されたハーバード建築
• 量子チューリングマシン
• 情報理論のもう一人の著名な思想家、クロード・シャノン
• チューリングマシンの例
• チューリングタールピット、チューリング完全であるにもかかわらず、実用的なコンピューティングには役に立たないと考えられているコンピューティングシステムまたは言語
• 非組織化機械、チューリングのニューラルネットワークに関する初期のアイデア
• フォン・ノイマン・アーキテクチャ

注記

1. ミンスキー (1967 , p. 107) 「1936年の論文で、A.M.チューリングは現在彼の名を冠する抽象機械のクラスを定義した。チューリングマシンとは、特殊な環境（テープ）に関連付けられた有限状態機械であり、そのテープに記号列を保存（そして後に復元）することができる。」また、ストーン (1972 , p. 8) でも「マシン」という言葉が引用符で囲まれている。
2. Stone (1972 , p. 8) は「この『マシン』は抽象的な数学モデルである」と述べている。また、 Sipser (2012 , p. 165ff) は「チューリングマシンモデル」について述べている。Rogers (1987 , p. 13) は「チューリングの特徴づけ」に言及しており、 Boolos, Burgess & Jeffrey (2002 , p. 25) は「特定の種類の理想化されたマシン」に言及している。
3. Sipser (2012 , p. 165) は、「チューリングマシンは実際のコンピュータが実行できることすべてを実行できます。ただし、チューリングマシンであっても特定の問題は解決できません。非常に現実的な意味で、これらの問題は計算の理論的な限界を超えています。」と述べています。
4. Sipser (2012 , p. 165)を参照。また、 Rogers (1987 , p. 13) は「両方向に無限の長さを持つ紙テープ」と表現している。Minsky (1967 , p. 118) は「テープは両方向に無限であるとみなされる」と述べている。Boolos、Burgess、Jeffrey (2002 , p. 25) は「必要に応じて空白のマス目を追加するために、両端に誰かが配置されている」可能性も示唆している。
5. Rogers (1987 , p. 13)を参照。Boolos , Burgess & Jeffrey (2002 , p. 35)、 Minsky (1967 , p. 117)、 Penrose (1989 , p. 37)など他の著者も「正方形」という。
6. Boolos、Burgess、Jeffrey (2002 , p. 25) は、機械がテープに沿って動いている様子を描いている。Penrose (1989 , pp. 36–37) は、無限のテープは「動かすのが難しいかもしれない」と述べ、「テープは、有限の装置が移動できる外部環境を表すものと考えるのを好む」と述べ、「『動き』は物事を描写するのに便利な方法だ」と指摘した上で、「装置はこの環境からすべての入力を受け取る」と示唆している。チューリングマシンモデルのいくつかのバリエーションでは、ヘッドが動いたり停止したりするのではなく、同じ位置に留まることも可能である。
7. ホッジス 2012 .
8. ホッジス 1983、93ページ。
9. ホッジス 1983、112ページ。
10. ホッジス 1983、129ページ。
11. このアイデアは1935年半ば（おそらく歴史の項を参照）、 MHAニューマンが講義で「数学的な命題に適用でき、それが証明可能かどうかを答えられる明確な方法、あるいはニューマンの言葉を借りれば『機械的なプロセス』は存在するだろうか」という問いをきっかけに思いついた。 ^{[ 8 ]}チューリングは1936年5月31日にロンドン数学会の紀要に論文を提出したが^{[ 9 ]}、は1937年初頭に出版され、抜刷は1937年2月に入手可能となった。 ^{[ 10 ]}
12. Davis (2000 , p. 151)の脚注を参照
13. Tyler & Emderton (2019)の序文を参照harvtxt エラー: ターゲットなし: CITEREFTylerEmderton2019 (ヘルプ)
14. Turing 1936 in Davis (2004 , pp. 132–134); Turingによる「循環的」の定義は119ページにあります。
15. チューリング 1936、230–265ページ。
16. チューリング 1936、デイビス（2004年、145ページ）
17. ウィクショナリーの「イニング」の定義を参照
18. チューリング（1968年、3～4ページ）
19. アクションテーブルや遷移関数と呼ばれることもあります。
20. 通常は5つ組[5組]：q _i a _j →q _i1 a _j1 d _kですが、4つ組[4組]の場合もあります。
21. ホップクロフト＆ウルマン 1979、148ページ。
22. p.149; 特にホップクロフトとウルマンは、${\displaystyle \delta}$ ${\displaystyle F}$
23. Van Emde Boas 1990、6ページ。
24. デイビス 2004、126～127頁。
25. デイビス 2000、152ページ。
26. ミンスキー 1967、119ページ。
27. ホップクロフト＆ウルマン 1979、158ページ。
28. ストーン 1972、9ページ。
29. デイヴィス（2004年、126ページ）のチューリングを参照
30. デイビス 2004、300ページ。
31. ポスト（1947）脚注12参照^{[ 30 ]}
32. デイビス 2004、119ページ。
33. Post (1947)、 Boolos & Jeffrey (1999)、 Davis, Sigal & Weyuker (1994)を参照。Post –Turing machineも参照。
34. Davis 2004、139–140 ページ。
35. デイビス 2004、121ページ。
36. デイビス 2004、118ページ。
37. クリーネ 1952、374–375ページ。
38. チューリング（1936） ^{[ 34 ]を参照}
39. 脚注‡ Davis (2004 , p. 138)
40. デイビス 2004年、166～168頁。
41. デイビス 2004、128ページ。
42. デイビス2000。
43. ミンスキー 1967、104ページ。
44. ヘニー＆スターンズ 1966年。
45. Arora & Barak 2009、定理1.9。
46. グレッチェル、ロヴァシュ、シュライフヴァー、1993 年、p. 32.
47. ガンディ 1995、54ページ。
48. ガンディ 1995、53ページ。
49. トーレス・ケベド 1914 .
50. トーレス・ケベド 1915年。
51. ガンディ 1995、55ページ。
52. ダーショウィッツ＆グレヴィッチ 2008 .
53. ガンディ 1995、57ページ。
54. ガンディ 1995、92ページ。
55. ホッジス 1983、91ページ。
56. ホーキング 2005、1121ページ。
57. 1936年以降。
58. ヒルベルトの第10問題で提起されたディオファントス方程式に関するより狭い問題は、1970年に再帰的可算集合とディオファントス集合の関係が最終的に明らかになるまで未解決のままであった。
59. ガンディ 1995、74ページ。
60. ガンディ 1995、76ページ。
61. デイビス 2004、160ページ。
62. ホッジス（1983年、112ページ）を参照
63. ホッジス（1983年、129ページ）を参照
64. デイビス 2004、145ページ。
65. Van Emde Boas 1990、4ページ。
66. Van Emde Boas 1990、16ページ。

参考文献

一次文献、再版、編集物

• アロンゾ・チャーチ（2019年4月23日）. タイラー・バージ、ハーバート・エンダートン（編）.アロンゾ・チャーチ全集. マサチューセッツ州ケンブリッジ、米国：MITプレス. ISBN 978-0-262-02564-5。
• ジャック・コープランド編 (2004). 『チューリングのエッセンシャル・ライティング：コンピューティング、論理、哲学、人工知能、そして人工生命に関する重要な著作集、そしてエニグマの秘密』オックスフォード大学出版局 (オックスフォード大学出版局). ISBN 0-19-825079-7チューリング文書、エミール・ポストへの「チューリングの慣例」批判に関する手紙の草稿、ドナルド・W・デイヴィスのチューリングの汎用計算機への訂正が含まれている。

• デイヴィス、マーティン編 (2004) [1965]. 『決定不能なもの：決定不能な命題、解決不能な問題、計算可能関数に関する基本論文』 ミネオラ、ニューヨーク州：ドーバー出版ISBN 978-0486432281。

• Hennie, FC; Stearns, RE (1966). 「マルチテープ・チューリングマシンの2テープシミュレーション」Journal of the ACM . 13 (4): 533– 546.

• ポスト、エミール(1936). 「有限組み合わせ過程―定式化1」. Journal of Symbolic Logic . 1 : 103–105 . Davis (2004 , p. 289ff)に再録

• ポスト、エミール(1947). 「Thueの問題の再帰的不解性」. Journal of Symbolic Logic . 12 : 1–11 . Davis (2004 , p. 293ff)に再録。付録にはチューリングの1936–1937年論文の訂正と解説が含まれている。特に、汎用計算機符号に関する訂正については脚注11、チューリングの第一および第二の証明に関するコメントについては脚注14を参照のこと。

• チューリング, AM (1936). 「計算可能数について、そして計算問題への応用」(PDF) .ロンドン数学会報. 2. 42 (1937年発行): 230–265 . doi : 10.1112/plms/s2-42.1.230 . S2CID  73712 .

• チューリング, AM (1938). 「計算可能数について、そして計算問題への応用：訂正」.ロンドン数学会報. 2. 43 (6): 544– 546. doi : 10.1112/plms/s2-43.6.544 .デイビス (2004) , pp. 115–154に再録

• チューリング, AM (1939). 「順序数に基づく論理体系」.ロンドン数学会報. s2-45 (1): 161– 228. doi : 10.1112/plms/s2-45.1.161 . hdl : 21.11116/0000-0001-91CE-3 .

• チューリング、アラン(1968) [1948].「知能機械」. エヴァンス, CR; ロバートソン, ADJ (編) 『サイバネティクス：主要論文集』. ボルチモア: ユニバーシティ・パーク・プレス. p. 31.再版：チューリング, AM (1996). 「知能機械：異端の理論」 .哲学数学. 4 (3): 256– 260. doi : 10.1093/philmat/4.3.256 .

計算可能性理論

• ブーロス, ジョージ;ジェフリー, リチャード(1999) [1974].計算可能性と論理（第3版）. ケンブリッジ大学出版局. ISBN 0-521-20402-X。

• ブーロス, ジョージ;バージェス, ジョン・P.;ジェフリー, リチャード(2002) [1989].計算可能性と論理（第4版）. ケンブリッジ大学出版局. ISBN 0-521-00758-5一部はバージェスによって大幅に書き直されました。チューリングマシンをラムベックの「アバカスマシン」（レジスタマシン参照）と再帰関数の文脈で提示し、それらの等価性を示します。

• Booth, Taylor L. (1967). 『シーケンシャルマシンとオートマトン理論』 ニューヨーク: John Wiley and Sons, Inc.大学院レベルの工学テキスト。幅広いトピックを網羅。第9章「チューリングマシン」では再帰理論について解説。

• デイビス、マーティン（2000年）『ユニバーサル・コンピュータ：ライプニッツからチューリングへの道』WWノートン社、ISBN 0-393-04785-7。『論理エンジン：数学者とコンピュータの起源』として再版。ニューヨーク：ノートン社。2001年。ISBN 9780393322293。

• デイビス, マーティン; シガル, ロン;ワイユカー, エレイン・J. (1994). 『計算可能性、複雑性、言語と論理：理論計算機科学の基礎』（第2版）. サンディエゴ: アカデミック・プレス, ハーコート・ブレース・アンド・カンパニー. ISBN 0-12-206382-1。

• グレッチェル、マーティン。ロヴァシュ、ラスロー;シュライバー、アレクサンダー (1993)。幾何学的アルゴリズムと組み合わせ最適化。アルゴリズムと組み合わせ論。 Vol. 2（第2版）。ベルリン: Springer-Verlag。土井：10.1007/978-3-642-78240-4。ISBN 978-3-642-78242-8. MR  1261419 .

• ヘニー、フレデリック (1977). 『計算可能性入門』 マサチューセッツ州レディング: アディソン・ウェスレー社. QA248.5H4 1977. 90～103ページでヘニーはUTMについて例やフローチャートを用いて論じているが、実際の「コード」は示していない。

• ホップクロフト、ジョン、ウルマン、ジェフリー・D. (1979). 『オートマトン理論、言語、計算入門』（第1版）. マサチューセッツ州レディング：アディソン・ウェスレー. ISBN 0-201-02988-X「言語」の機械解釈、NP完全性などの問題を中心に扱います。

• ホップクロフト, ジョン・E. ; モトワニ, ラジーヴ;ウルマン, ジェフリー・D. (2001). 『オートマトン理論、言語、計算入門（第2版）』 マサチューセッツ州レディング: アディソン・ウェスレー. ISBN 0-201-44124-1。

• クリーネ、スティーブン(1952). 『メタ数学入門』（第10刷（1971年第6刷の訂正を含む））アムステルダム、オランダ: ノースホランド出版社。大学院レベルのテキスト。第13章「計算可能関数」の大部分は、チューリングマシンによる再帰関数の計算可能性証明などについて書かれている。

• ドナルド・E・クヌース（1973年）『コンピュータプログラミングの技法』第1巻：基本アルゴリズム（第2版）マサチューセッツ州レディング：アディソン・ウェスレー出版社。計算機の発展におけるチューリングマシンの役割については、1.4.5「歴史と参考文献」225ページ以降および2.6「歴史と参考文献」456ページ以降を参照。

• マンナ、ゾハル（1974年）『計算の数学的理論』（再版、ドーバー、2003年版）マグロウヒル、ISBN 978-0-486-43238-0。

• ミンスキー、マービン(1967). 『計算：有限機械と無限機械』 . ニュージャージー州: プレンティス・ホール社.第8章、第8.2節「停止問題の解決不能性」を参照。

• パパディミトリウ, クリストス(1993).計算複雑性（第1版）. アディソン・ウェスレー. ISBN 0-201-53082-1第2章:チューリングマシン、pp.19–56。

• レオナルド、トーレス・ケベド（1914年）。 「Ensayos sobre Automática – Su definición. Extensión teórica de sus aplicaciones」。Revista de la Academia de Ciencias Exactas (スペイン語)。12 : 391–418 .

• レオナルド、トーレス・ケベド（1915年）。「Essais sur l'Automatique – Sa definition. Étendue théorique de ses application」。Revue Générale des Sciences Pures et Appliquées (フランス語)。2：601～ 611。

• ロジャース、ハートリー(1987) [1967]. 『再帰関数の理論と実効計算可能性』（ペーパーバック（原著1967年マグロウヒル版））ケンブリッジ、マサチューセッツ州：MITプレス。ISBN 0-262-68052-1。

• シプサー、マイケル(2012) [1997]. 「第3章 チャーチ＝チューリングのテーゼ」.計算理論入門（第3版）. Cengage Learning. pp.  165– 192. ISBN 978-1-133-18779-0。

• ストーン、ハロルド・S. (1972). 『コンピュータ組織とデータ構造入門』（第1版）. ニューヨーク: マグロウヒル・ブック・カンパニー. ISBN 0-07-061726-0。

• ヴァン・エムデ・ボアス、ピーター(1990). 「マシンモデルとシミュレーション」. ヤン・ヴァン・レーウェン編.理論計算機科学ハンドブック A アルゴリズムと複雑性. MITプレス/エルゼビア. pp.  3– 66. ISBN 0-444-88071-2アメリカ議会図書館請求番号: QA76.H279 1990

チャーチの論文

• ダーショウィッツ, ナフム; グレヴィッチ, ユーリ (2008年9月). 「計算可能性の自然な公理化とチャーチのテーゼの証明」(PDF) . Bulletin of Symbolic Logic . 14 (3) . 2025年12月12日閲覧.

他の

• アローラ、サンジーヴ、バラク、ボアズ(2009). 「セクション1.4および1.7」.複雑性理論：現代的アプローチ. ケンブリッジ大学出版局. ISBN 978-0-521-42426-4。

• ロビン・ガンディ（1995年）「1936年における思想の合流」ロルフ・ヘルケン編『万能チューリングマシン ― 半世紀にわたる概観』シュプリンガー出版社、  51～ 102頁。ISBN 978-3-211-82637-9。

• ホーキング、スティーブン編（2005年）『神は整数を創造した：歴史を変えた数学的ブレークスルー』フィラデルフィア：ランニング・プレス、ISBN 978-0-7624-1922-7チューリングの1936年から1937年の論文とホーキングによる解説と伝記を収録

• ホッジス、アンドリュー(1983). 「真理の精神」.アラン・チューリング著『エニグマ』 . ニューヨーク:サイモン＆シュスター.証明に至る経緯と議論については「真理の精神」の章を参照。

• ホッジス、アンドリュー（2012年）『アラン・チューリング：エニグマ』（100周年記念版）プリンストン大学出版局、ISBN 978-0-691-15564-7。

• カントロヴィッツ, イザヤ・ピンチャス (2005年12月1日). 「ルール駆動型システムのチューリングマシン計算可能性に関するノート」. SIGACT News . 36 (4): 109–110 . doi : 10.1145/1107523.1107525 . S2CID  31117713 .

• キルナー、ライムンド。ウルフ・ツィンマーマン。リヒター、ディルク（2009 年 10 月）。「実際のプログラミング言語の決定不可能性の結果について」。15. コロキウム プログラミアプラッヘンとグルンドラーゲン デア プログラミエルング (KPS'09)。マリア・ターファール、オーストリア。

• ペンローズ、ロジャー（1989年）『皇帝の新しい心：コンピュータ、心、そして物理法則について』オックスフォード大学出版局（オックスフォード大学出版局）ISBN 0-19-851973-71990年の訂正

• ペッツォルド、チャールズ(2008). 『注釈付きチューリング』 ジョン・ワイリー・アンド・サンズ社ISBN 0-470-22905-5。

• 王浩(1957). 「チューリングの計算機理論の変種」.計算機協会誌 (KACM) . 4 : 63–92 .

外部リンク

• 「チューリングマシン」、数学百科事典、EMSプレス、2001 [1994]
• スタンフォード哲学百科事典2025年夏号に掲載された、リースベス・デ・モルによる「チューリングマシン」の項目