チューリングマシン

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

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

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

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

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

チューリングマシンは、機械的な計算能力に根本的な限界があることを証明しました。^[14]チューリングマシンは任意の計算を表現できますが、その最小限の設計により、実際に計算するには遅すぎます。現実世界のコンピュータは、チューリングマシンとは異なり、ランダムアクセスメモリを使用する異なる設計に基づいています。

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

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

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

チューリングマシンMと任意の文字列sが与えられた場合、 M が最終的にs を生成するかどうかは一般には判断できません。これは、停止問題が解決不可能であるためであり、これはコンピューティングの理論的な限界に大きな影響を与えます。

チューリングマシンは無制限の文法を処理でき、さらに無限の方法で一階述語論理を堅牢に評価できることも意味します。これはラムダ計算によってよく実証されています。

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

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

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

— チューリング 1948年、3ページ^[16]

チューリング マシンは、テープ上で機械的に動作するマシンを数学的にモデル化したものです。このテープにはシンボルがあり、マシンはテープ ヘッドを使用して 1 つずつ読み書きできます。操作は、「状態 42 で、シンボルが 0 の場合は 1 を書き込む。シンボルが 1 の場合は状態 17 に変更する。状態 17 で、シンボルが 0 の場合は 1 を書き込んで状態 6 に変更する」など、有限セットの基本命令によって完全に決定されます。元の記事 (「計算可能な数について、計算問題への応用」、以下の参考文献も参照) では、チューリングはメカニズムではなく、これらの決定論的な機械的ルールを忠実に (またはチューリングの表現を借りれば「散発的に」) 実行する「コンピュータ」と呼ばれる人物を想像しています。

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

• テープはセルに分割され、セルは隣り合って配置されます。各セルには、有限のアルファベットの記号が含まれます。アルファベットには、特別な空白記号 (ここでは「0」と表記) と 1 つ以上の他の記号が含まれます。テープは左右に任意に拡張可能であると想定されているため、チューリング マシンには、計算に必要なだけのテープが常に供給されます。以前に書き込まれたことのないセルは、空白記号で埋められているものと想定されます。一部のモデルでは、テープの左端に特別な記号が付けられており、テープは右に拡張されるか、無制限に拡張可能です。
• テープ上の記号を読み書きし、テープを 1セルずつ左右に動かすことができるヘッド。一部のモデルでは、ヘッドが移動し、テープは固定されています。
• 有限数あるチューリングマシンの状態のうちの 1 つを保存する状態レジスタ。これらの中には、状態レジスタが初期化される特別な開始状態があります。チューリングは、これらの状態は、計算を実行する人が通常持つ「心の状態」に取って代わると書いています。
• 機械が現在置かれている状態（q _{i ）}とテープ上^で読み取っているシンボル（a _{j ）（現在ヘッドの下にあるシンボル）に基づいて、機械に以下の処理を順番に実行するように指示する命令[18]}の^有限テーブル[ 17 ] （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) の両方のアクションを実行することはできません。モデルによっては、現在のシンボルと状態の組み合わせのエントリがテーブルにない場合、マシンは停止します。他のモデルでは、すべてのエントリを入力する必要があります。

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

Hopcroft & Ullman (1979, p. 148) によれば、（1テープ）チューリングマシンは、7つの組 として正式に定義され、 ${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$

• ${\displaystyle \ガンマ}$テープアルファベット記号の有限の空でない集合です。
• ${\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は右シフトである。が現在の状態と現在のテープシンボルに対して定義されていない場合、マシンは停止する。^[19]直感的には、遷移関数は現在の状態から遷移する次の状態、ヘッドが指している現在のシンボルを上書きするシンボル、および次のヘッドの動きを指定する。${\displaystyle \delta }$

変形では、方向のセットの 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}$

van Emde Boas (1990) の 6 ページの言葉を借りれば、「集合論的オブジェクト [上記に類似した彼の正式な 7 組の記述] は、マシンがどのように動作するか、およびその計算がどのようになるかについて、部分的な情報しか提供しません。」

例えば、

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

文献での定義は、議論や証明をより簡単に、またはより明確にするために、わずかに異なることがありますが、これは常に、結果として得られるマシンが同じ計算能力を持つように行われます。たとえば、セットは から に変更でき、ここでN (「なし」または「操作なし」) は、マシンが左または右に移動するのではなく、同じテープ セルに留まるようにします。これにより、マシンの計算能力は向上しません。 ${\displaystyle \{L,R\}}$${\displaystyle \{L,R,N\}}$

最も一般的な規則では、チューリング/デイビスの規則に従って、「チューリング テーブル」内の各「チューリング命令」を 9 つの 5 組のうちの 1 つで表します (Turing (1936) のThe Undecidable、p. 126–127 および Davis (2000) p. 152)。

（定義１）: (q _i , S _j , S _k /E/N, L/R/N, q _m )

(現在の状態q _i 、スキャンされたシンボルS _j 、印刷シンボルS _k /消去E /なしN 、 move_tape_one_square left L /right R /なしN 、新しい状態q _m )

_{他の著者（Minsky（1967）p. 119、Hopcroft and Ullman（1979）p. 158、Stone（1972）p. 9）は、スキャンされたシンボルS j の}直後に新しい状態q _mをリストするという異なる規則を採用しています。

（定義２）: (q _i , S _j , q _m , S _k /E/N, L/R/N)

(現在の状態q _i 、スキャンされたシンボルS _j 、新しい状態q _m 、印刷シンボルS _k /消去E /なしN 、 move_tape_one_square left L /right R /なしN )

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

次の表では、チューリングのオリジナルモデルでは、彼が N1、N2、N3 と呼んだ最初の 3 行のみが許可されていました ( The Undecidableのチューリング、p. 126 を参照)。彼は、0 番目のシンボル S ₀を「消去」または「空白」などと名付けることで、「スキャンされた正方形」の消去を許可しました。ただし、印刷しないことは許可しなかったため、すべての命令行に「シンボル S _kを印刷」または「消去」が含まれています (Post (1947)、The Undecidable、p. 300 の脚注 12 を参照)。略語はチューリングのものです ( The Undecidable、p. 119)。1936 年から 1937 年にかけてのチューリングのオリジナル論文以降、マシンモデルでは 5 組の可能な 9 種類すべてが許可されています。

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

それほど頻繁ではありませんが、4 タプルが使用されることもあります。これは、チューリング命令をさらに細分化したものです (Post (1947)、Boolos & Jeffrey (1974、1999)、Davis-Sigal-Weyuker (1994) を参照)。詳細については、Post–Turing machineを参照してください。

チューリング マシンの文脈で使われる「状態」という言葉は、2 つの意味を持つ可能性があるため、混乱の原因となることがあります。チューリング以降のほとんどの解説者は、「状態」を、現在実行されている命令の名前/指定子、つまり状態レジスタの内容の意味で使用してきました。しかし、チューリング (1936) は、マシンの「m 構成」と呼んだものの記録と、計算中のマシン (または人) の「進行状態」、つまりシステム全体の現在の状態を明確に区別しました。チューリングが「状態式」と呼んだものには、現在の命令とテープ上の すべてのシンボルの両方が含まれます。

したがって、どの段階でも計算の進行状況は、テープ上の指示の記録と記号によって完全に決定されます。つまり、システムの状態は、テープ上の記号、それに続く Δ (他の場所には現れないはず)、そして指示の記録で構成される単一の式 (記号のシーケンス) によって記述できます。この式は「状態式」と呼ばれます。

—  The Undecidable、pp. 139-140、強調追加

チューリングは、論文の前半でこれをさらに進め、現在の「m 構成」のシンボル (命令のラベル) を、テープ上のすべてのシンボルとともにスキャンした四角形の下に配置した例を挙げています ( 『The Undecidable 』 、p. 121)。彼はこれを「完全な構成」と呼んでいます ( 『The Undecidable』、p. 118)。「完全な構成」を 1 行に印刷するために、彼は状態ラベル/m 構成をスキャンしたシンボルの 左側に配置しています。

このバリエーションは、Kleene (1952) に見られます。Kleeneは、マシンの「状況」のゲーデル数の書き方を示しています。つまり、テープ上の 6 つの空白でない四角形のほぼ中央のスキャンされた四角形の上に「m 構成」シンボル q ₄を配置し (この記事のチューリング テープ図を参照)、スキャンされた四角形の右側に配置します。しかし、Kleene は「q ₄」自体を「マシンの状態」と呼んでいます (Kleene、374 ～ 375 ページ)。Hopcroft と Ullman はこの複合を「瞬間記述」と呼び、チューリング規則に従って「現在の状態」(命令ラベル、m 構成) をスキャンされたシンボルの左側に配置します (149 ページ)。つまり、瞬間記述は、左側の空白でないシンボル、マシンの状態、ヘッドによってスキャンされた現在のシンボル、右側の空白でないシンボルの複合です。

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

1 1​

つまり、3 回の移動後、テープには ... 000110000 ... があり、ヘッドは右端の 1 をスキャンしており、状態はAです。空白 (この場合は「0」で表されます) は、ここに示すように全体の状態の一部になることがあります: B 01。テープには 1 が 1 つありますが、ヘッドはその左側の 0 (「空白」) をスキャンしており、状態はBです。

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

チューリングの伝記作家アンドリュー・ホッジス（1983：107）は、この混乱について指摘し、議論しています。

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

通常、大きな表は表のままにしておく方がよいでしょう (Booth、p. 74)。表形式にすると、コンピュータで簡単にシミュレートできます (Booth、p. 74)。ただし、特定の概念 (たとえば、「リセット」状態を持つマシンや繰り返しパターンを持つマシン (Hill および Peterson、p. 244ff を参照)) は、図として表示すると、よりわかりやすくなります。

図面が表の改良点を表すかどうかは、特定の状況に応じて読者が判断する必要があります。

読者は、このような図が時間と空間を通じた計算の過程 (「軌跡」)ではなく、時間的に凍結されたテーブルのスナップショットを表していることに再度注意する必要があります。ビジー ビーバー マシンが「実行」されるたびに、常に同じ状態軌跡をたどりますが、これは可変入力「パラメータ」を提供できる「コピー」マシンには当てはまりません。

「計算の進行」図は、3 状態のビジー ビーバーの「状態」(命令) が計算の開始から終了まで進行する様子を示しています。右端は、各ステップでのチューリングの「完全な構成」(クリーネの「状況」、ホップクロフト - ウルマンの「瞬間的な記述」) です。マシンを停止して「状態レジスタ」とテープ全体を空にすると、これらの「構成」を使用して、計算の進行中のどの場所でも計算を再開できます (参照: チューリング (1936) 『決定不能なもの』、139 ～ 140 ページ)。

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

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

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

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

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

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

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

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

...その動作は構成によって部分的にしか決定されません...このようなマシンがこれらのあいまいな構成の 1 つに到達すると、外部のオペレータによって任意の選択が行われるまで、マシンは動作を続けることができません。これは、マシンを使用して公理系を扱っている場合に当てはまります。

— 『  The Undecidable』、118ページ

チューリング (1936) は、脚注で「ヒルベルト計算の証明可能なすべての公式を見つける」ために選択マシンを使用するのではなく a-machine を使用する方法を説明している以外は、これ以上詳しく説明していません。彼は「選択肢は常に 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、... を順に実行します」(脚注 ‡、The Undecidable、p. 138)

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

オラクルマシンまたは o マシンは、計算を状態「o」で一時停止し、計算を完了するために「オラクル」の「決定を待つ」チューリング a マシンです。オラクルとは、チューリングによって「マシンではあり得ない」と述べられている以外は具体的に定義されていない実体です (Turing (1939)、「決定不能なもの」、p. 166-168)。

チューリングは『The Undecidable』の128ページ（強調筆者）で次のように書いている。

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

この発見は今では当然のこととみなされていますが、当時 (1936 年) は驚くべきことと考えられていました。^{[要出典]チューリングが「ユニバーサル マシン」(略して「} U 」)と呼んだ計算モデルは、一部の人々によって (Davis (2000) を参照)、プログラム内蔵型コンピュータの概念につながる基本的な理論的ブレークスルーであったと考えられています。

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

— ミンスキー（1967）、104ページ

計算の複雑さの点では、マルチテープ汎用チューリングマシンは、シミュレートするマシンと比較して対数係数で遅くなるだけで済みます。この結果は、1966 年に FC Hennie とRE Stearnsによって得られました。(Arora と Barak、2009、定理 1.9)

チューリングマシンは、有限状態マシンやプッシュダウンオートマトンなどの他の種類のオートマトンよりも強力です。チャーチ-チューリングのテーゼによれば、チューリングマシンは実際のマシンと同じくらい強力であり、実際のプログラムが実行できるすべての操作を実行できます。この記述で無視されているのは、実際のマシンは有限の数の構成しか持てないため、有限状態マシンにすぎないのに対し、チューリングマシンには計算に使用できる記憶領域が無制限にあるということです。

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

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

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

コンピューティングの初期の頃、コンピュータの使用は、通常、バッチ処理、つまり、与えられた入力データから出力データを生成する非対話型タスクに限定されていました。入力から出力までの関数の計算可能性を研究し、チューリング マシンが発明された計算可能性理論は、この実践を反映しています。

1970 年代以降、コンピュータの対話型使用はより一般的になりました。原理的には、チューリング マシンと同時に外部エージェントがテープから読み取り、テープに書き込むことでこれをモデル化できますが、これが対話の実際の発生方法と一致することはほとんどありません。そのため、対話性を説明する場合は、通常、 I/O オートマトンなどの代替手段が好まれます。

計算の算術モデルはチューリングモデルと2つの点で異なる: ^{[20] : 32}

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

一部のアルゴリズムは、あるモデルでは多項式時間で実行されますが、他のモデルでは実行されません。例:

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

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

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

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

—  （バベッジの引用、ガンディ、p. 54の強調部分）

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

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

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

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

— ガンディ p. 55

1900 年に有名な数学者デイヴィッド ヒルベルトが提起したヒルベルトの問題に関して、問題 10の側面は、正確に定義されるまでほぼ 30 年間にわたって議論されていました。問題 10 に対するヒルベルトの元の表現は次のとおりです。

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

— この翻訳とオリジナルのドイツ語を引用、Dershowitz and Gurevich、2008年

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

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

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

— ガンディ、p. 57、ベーマンの言葉を引用

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

— 同上。

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

— 同上、92ページ

1928 年の国際数学者会議までに、ヒルベルトは「非常に明確な疑問を呈した。第一に、数学は完全か...第二に、数学は一貫しているか...第三に、数学は決定可能か?」 (Hodges p. 91、Hawking p. 1121)。最初の 2 つの疑問は、1930 年に、ヒルベルトが引退演説を行ったまさにその会議で、クルト ゲーデルによって答えられた(ヒルベルトにとっては残念なことだった)。3 つ目の「決定問題」は、1930 年代半ばまで待たなければならなかった。

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

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

— ホッジス p. 112

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

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

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

— ガンディ、74ページ

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

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

— 同上、76ページ

ガンディはニューマンの上記の発言は「誤解を招く」と考えていたが、この意見はすべての人に受け入れられているわけではない。チューリングは生涯を通じて機械に興味を持っていた。「アランは子供の頃、タイプライターを発明することを夢見ていた。[彼の母親]チューリング夫人はタイプライターを持っていた。そして彼は、タイプライターを「機械式」と呼ぶことの意味を自問することから始めたのかもしれない」(ホッジス、96 ページ)。プリンストンで博士号取得を目指していたとき、チューリングはブール論理乗算器を作成した (下記参照)。彼の博士論文「序数に基づく論理システム」には、「計算可能な関数」の次の定義が含まれている。

上で「関数は、その値が何らかの純粋に機械的なプロセスによって見つけられる場合、効果的に計算可能である」と述べられました。この記述を文字通りに受け取ることができます。純粋に機械的なプロセスとは、機械によって実行できるプロセスです。これらの機械の構造を、ある標準形式で数学的に記述することは可能です。これらのアイデアを展開すると、著者の計算可能関数の定義と、計算可能性と効果的な計算可能性の同一視につながります。これらの 3 つの定義 [3 番目は λ 計算] が同等であることを証明するのは、多少面倒ではありますが、難しくはありません。

— チューリング（1939年）『決定不可能なもの』160ページ

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

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

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

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

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

— チューリングの論文より、 The Undecidableに再録、p. 145

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

1937 年、プリンストンで博士論文に取り組んでいたチューリングは、独自の電気機械式リレーを製作し、デジタル (ブール論理) 乗算器を一から構築しました(Hodges p. 138)。「アランの課題は、チューリング マシンの論理設計をリレー操作スイッチのネットワークに具体化することだった...」(Hodges p. 138)。チューリングは当初は単に好奇心と実験に熱中していただけだったかもしれませんが、同じ方向への非常に真剣な研究がドイツ (コンラート ツーゼ(1938))、米国 (ハワード エイケン)、ジョージ スティビッツ(1937) で進められ、彼らの努力の成果は第二次世界大戦で枢軸軍と連合軍の両方で使用されました(cf. Hodges p. 298–299)。 1950 年代前半から中頃に、Hao WangとMarvin Minsky はチューリング マシンをより単純な形式 ( Martin Davisのポスト チューリング マシンの前身) に縮小しました。同時に、ヨーロッパの研究者は、当時流行していた電子コンピュータを、当時「チューリング マシン」と呼ばれていたものに相当するコンピュータのような理論上のオブジェクトに縮小していました。1950 年代後半から 1960 年代前半にかけて、Melzak と Lambek (1961)、Minsky (1961)、Shepherdson と Sturgis (1961) による偶然にも同時進行の開発により、ヨーロッパの研究がさらに進められ、チューリング マシンは、カウンター マシンと呼ばれる、より使いやすくコンピュータのような抽象モデルに縮小されました。Elgot と Robinson (1964)、Hartmanis (1971)、Cook と Reckhow (1973) は、レジスタ マシン モデルとランダム アクセス マシンモデルでこの研究をさらに進めましたが、基本的にはすべて、算術のような命令セットを備えたマルチテープ チューリング マシンにすぎません。

今日でも、カウンター、レジスター、ランダム アクセス マシン、およびそれらの親であるチューリング マシンは、計算理論の問題を研究する理論家が好んで選ぶモデルであり続けています。特に、計算複雑性理論ではチューリング マシンが利用されています。

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

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

— ファン・エムデ・ボアス 1990:4

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

— ファン・エムデ・ボアス 1990:16

1. ^ Minsky 1967:107 「1936 年の論文で、AM Turing は現在彼の名前を冠している抽象マシンのクラスを定義しました。チューリング マシンは、特殊な環境 (テープ) に関連付けられた有限状態マシンであり、そのテープにシンボルのシーケンスを保存 (および後で復元) できます」また Stone 1972:8 では、「マシン」という単語が引用符で囲まれています。
2. ^ Stone 1972:8 は「この「マシン」は抽象的な数学モデルである」と述べており、また「チューリングマシンモデル」について説明している Sipser 2006:137ff も参照してください。Rogers 1987 (1967):13 は「チューリングの特徴付け」に言及し、Boolos Burgess と Jeffrey 2002:25 は「特定の種類の理想化されたマシン」に言及しています。
3. ^ Sipser 2006:137「チューリングマシンは、実際のコンピュータが実行できることすべてを実行できます」。
4. ^ Sipser 2002:137 を参照。また、Rogers 1987 (1967):13 では「両方向に無限の長さの紙テープ」と説明されている。Minsky 1967:118 では「テープは両方向に無限であるとみなされる」と述べられている。Boolos Burgess と Jeffrey 2002:25 では「必要に応じて空白の四角形を追加するために、両端に誰かが配置されている」可能性も挙げられている。
5. ^ Rogers 1987 (1967):13を参照。他の著者は「square」という単語を使用している。例：Boolos Burgess Jeffrey 2002:35、Minsky 1967:117、Penrose 1989:37。
6. ^ Boolos Burgess Jeffry 2002:25 は、マシンがテープに沿って動いていることを説明しています。Penrose 1989:36-37 は、無限のテープは「動かすのが難しいかもしれない」と述べ、テープが「有限のデバイスが移動できる外部環境を表すと考えることを好みます」と述べ、さらに「「動き」は物事を描写するのに便利な方法である」と述べ、次に「デバイスはすべての入力をこの環境から受け取る」と示唆しています。チューリング マシン モデルのいくつかのバリエーションでは、ヘッドが動いたり停止したりするのではなく、同じ位置に留まることもできます。
7. ^ ab ホッジス、アンドリュー(2012)。アラン・チューリング：エニグマ（センテナリー版）。プリンストン大学出版局。ISBN 978-0-691-15564-7。
8. ^ このアイデアは、1935 年半ば (おそらく、詳細は歴史の項を参照)、MHA ニューマンが講義で「数学的な記述に適用でき、それが証明可能かどうかの答えを導き出す明確な方法、またはニューマンの言葉を借りれば「機械的プロセス」は存在するか」という質問を受けて、チューリングに浮かんだものである。(Hodges 1983:93)。チューリングは 1936 年 5 月 31 日にロンドン数学会の Proceedings に論文を提出した( cf. Hodges 1983:112) が、論文は 1937 年初頭に出版され、抜刷りは 1937 年 2 月に入手可能になった (cf. Hodges 1983:129)。
9. ^ Davis 2000:151の脚注を参照。
10. ^ ab 『アロンゾ・チャーチ全集』の序文を参照（バージ、タイラー、エンダートン、ハーバート編（2019-04-23）『アロンゾ・チャーチ全集』。マサチューセッツ州ケンブリッジ、米国：MITプレス。ISBN 978-0-262-02564-5。）
11. ^ ab Turing 1936 in The Undecidable 1965:132-134; チューリングの「循環的」の定義は 119 ページにあります。
12. ^ abチューリング、アラン・マシソン (1937)。「計算可能数について、そして 計算問題への応用」。ロンドン数学会紀要。シリーズ 2。42 ( 1): 230–265。doi :10.1112/plms/ s2-42.1.230。S2CID 73712  。
13. ^ チューリング 1936年The Undecidable 1965:145
14. ^ Sipser 2006:137 は、「チューリング マシンは、実際のコンピュータが実行できることはすべて実行できます。ただし、チューリング マシンでも特定の問題は解決できません。実際のところ、これらの問題は計算の理論的な限界を超えています。」と述べています。
15. ^ ウィクショナリーの「イニング」の定義を参照
16. ^ AM Turing (1948年7月). インテリジェント機械（レポート）. 国立物理学研究所. こちら: p.3-4
17. ^ アクションテーブルや遷移関数と呼ばれることもあります。
18. ^ 通常は5つ組[5組]：q _i a _j →q _i1 a _j1 d _kですが、4つ組[4組]の場合もあります。
19. ^ p.149; 特にホップクロフトとウルマンは、${\displaystyle \delta }$${\displaystyle F}$
20. ^ マーティン・グレッチェル; Lovász, ラスロー; Schrijver、Alexander (1993)、幾何学的アルゴリズムと組み合わせ最適化、Algorithms and Combinatorics、vol. 2 (第 2 版)、Springer-Verlag、ベルリン、doi :10.1007/978-3-642-78240-4、ISBN 978-3-642-78242-8、MR  1261419
21. ^ L. トーレス・ケベド。Ensayos sobre Automática – Su の定義。 Extension teórica de sus aplicaciones、 Revista de la Academia de Ciencias Exacta、Revista 12、391–418 ページ、1914 年。
22. ^ トーレス・ケベド。 L. (1915)。 「Essais sur l'Automatique - Sa definition. Etendue théorique de ses Applications」、Revue Génerale des Sciences Pures et Appliquées、vol. 2、601–611ページ。
23. ^ ヒルベルトの第10問題で提起されたディオファントス方程式に関するより狭い問題は、1970年に再帰的可算集合とディオファントス集合の関係が最終的に明らかになるまで未解決のままでした。

• B.ジャック コープランド編 (2004)、『The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma』、クラレンドン プレス (オックスフォード大学出版局)、オックスフォード、英国、ISBN 0-19-825079-7 。チューリング論文に加え、エミール ポストへの「チューリングの慣習」に対する批判に関する手紙の草稿と、ドナルド W. デイヴィスの「チューリングのユニバーサル コンピューティング マシンに対する修正」が含まれています。 
• マーティン・デイヴィス（編）（1965年）『The Undecidable』、レイヴン・プレス、ヒューレット、ニューヨーク。
• Emil Post (1936)、「有限組み合わせプロセス - 定式化 1」、Journal of Symbolic Logic、1、103-105、1936 年。The Undecidable、289 ページ以降に再掲載。
• Emil Post (1947)、「Thue の問題の再帰的解決不可能性」、Journal of Symbolic Logic、第 12 巻、pp. 1–11。The Undecidable 、pp. 293ff に再録。この論文の付録で、Post は 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) (1937 年発行): 544–6。doi :10.1112/plms/s2-43.6.544 。『The Undecidable』115～154ページに再録。
• アラン・チューリング、1948年、「インテリジェント・マシナリー」。「サイバネティクス：主要論文」に再録。C.R.エバンス、AD.J.ロバートソン編。ボルチモア：ユニバーシティ・パーク・プレス、1968年。31ページ。チューリング、AM（1996年）に再録。「インテリジェント・マシナリー、異端の理論」。哲学数学。4 （3）：256-260。doi ： 10.1093/ philmat /4.3.256。
• FC HennieとRE Stearns .マルチテープチューリングマシンの2テープシミュレーション. JACM , 13(4):533–546, 1966.

• Boolos, George; Richard Jeffrey (1999) [1989]. Computability and Logic (第3版). Cambridge UK: Cambridge University Press. ISBN 0-521-20402-X。
• Boolos, George、John Burgess、Richard Jeffrey (2002)。Computability and Logic (第 4 版)。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-00758-5。いくつかの部分は、Burgess によって大幅に書き直されました。Lambek の「そろばんマシン」(レジスタ マシンを参照) と再帰関数のコンテキストでのチューリング マシンのプレゼンテーション、およびそれらの同等性を示します。
• Taylor L. Booth (1967)、「Sequential Machines and Automata Theory」、John Wiley and Sons, Inc.、ニューヨーク。大学院レベルの工学テキスト。幅広いトピックを扱っており、第 IX 章「チューリングマシン」には再帰理論が含まれています。
• マーティン・デイビス(1958)。『計算可能性と解決不可能性』McGraw-Hill Book Company, Inc、ニューヨーク。12～20ページでは、加算、後続関数、減算（x ≥ y）、適切な減算（x < yの場合は0）、恒等関数とさまざまな恒等関数、乗算の5組の表の例を示しています。
• デイビス、マーティン、ロン・シガル、エレイン・J・ワイユカー(1994)。計算可能性、複雑性、言語と論理: 理論計算機科学の基礎(第 2 版)。サンディエゴ: アカデミック プレス、ハーコート、ブレイス & カンパニー。ISBN 0-12-206382-1。
• ヘニー、フレデリック (1977)。計算可能性入門。アディソン・ウェズレー、マサチューセッツ州リーディング。QA248.5H4 1977。90～103 ページで、Hennie は UTM について例やフローチャートを使って説明していますが、実際の「コード」はありません。
• ホップクロフト、ジョン、ウルマン、ジェフリー(1979)。オートマトン理論、言語、計算入門(第 1 版)。Addison–Wesley、マサチューセッツ州リーディング。ISBN 0-201-02988-X。「言語」の機械解釈、NP完全性などの問題を中心に扱います。
• ホップクロフト、ジョン E.、ラジーヴ モトワニ、ジェフリー D. ウルマン (2001)。オートマトン理論、言語、計算入門(第 2 版)。Reading Mass: Addison– Wesley。ISBN 0-201-44124-1。
• Stephen Kleene (1952)、「Introduction to Metamathematics」 、North–Holland Publishing Company、アムステルダム、オランダ、第 10 刷 (1971 年の第 6 刷の訂正を含む)。大学院レベルのテキスト。第 XIII 章「計算可能関数」の大部分は、再帰関数の計算可能性のチューリング マシン証明などについてです。
• Knuth, Donald E. (1973)。第 1 巻/Fundamental Algorithms: The Art of computer Programming (第 2 版)。マサチューセッツ州レディング: Addison–Wesley Publishing Company。計算（ハードウェアとソフトウェアの両方）の発展におけるチューリングマシンの役割については、1.4.5歴史と参考文献の 225 ページ以降と 2.6歴史と参考文献の 456 ページ以降を参照してください。
• ゾハル・マンナ、1974年、「計算の数学的理論」。再版、ドーバー、2003年。ISBN 978-0-486-43238-0 
• マービン・ミンスキー著『計算：有限マシンと無限マシン』、Prentice–Hall, Inc.、NJ、1967年。第8章、セクション8.2「停止問題の解決不能性」を参照。
• Christos Papadimitriou (1993)。計算複雑性（第 1 版）。Addison Wesley。ISBN 0-201-53082-1。第2章: チューリングマシン、pp. 19–56。
• Hartley Rogers, Jr.著『再帰関数と効果的な計算可能性の理論』、MIT Press、ケンブリッジ MA、ペーパーバック版 1987 年、オリジナル McGraw-Hill 版 1967 年、ISBN 0-262-68052-1 (ペーパーバック) 
• マイケル・シプサー（1997年）。計算理論入門。PWS出版。ISBN 0-534-94728-X。第3章: チャーチ＝チューリングのテーゼ、pp. 125–149。
• ストーン、ハロルド S. (1972)。コンピュータ組織とデータ構造入門(第 1 版)。ニューヨーク: McGraw-Hill Book Company。ISBN 0-07-061726-0。
• Peter van Emde Boas 1990、「Machine Models and Simulations」、pp. 3–66、Jan van Leeuwen編、「Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity」、The MIT Press/Elsevier、[場所?]、ISBN 0-444-88071-2 (Volume A)。QA76.H279 1990。 

• Nachum Dershowitz、Yuri Gurevich (2008 年 9 月)。「計算可能性の自然な公理化と Church のテーゼの証明」(PDF)。Bulletin of Symbolic Logic。14 ( 3) 。2008 年 10 月 15日閲覧。
• ロジャー・ペンローズ（1990）[1989]。『皇帝の新しい心』（第2版）。オックスフォード大学出版局、ニューヨーク。ISBN 0-19-851973-7。

• Rogozhin, Yurii、1998、「22 の状態と 2 つのシンボルを持つ汎用チューリング マシン」、Romanian Journal of Information Science and Technology、1(3)、259–265、1998 年。(小型の汎用チューリング マシンに関する既知の結果を調査)
• スティーブン・ウルフラム、2002年、「A New Kind of Science」、ウルフラムメディア、ISBN 1-57955-008-8 
• ブルンフィール、ジェフ、「学生が数学の賞を獲得」、ネイチャー、2007 年 10 月 24 日。
• Jim Giles (2007)、「最もシンプルな「ユニバーサル コンピューター」が学生に 25,000 ドルの賞金をもたらす」、New Scientist、2007 年 10 月 24 日。
• Alex Smith、Wolfram 2、3 チューリング マシンの普遍性、Wolfram 2、3 チューリング マシン研究賞への応募。
• Vaughan Pratt、2007、「シンプルなチューリングマシン、普遍性、エンコーディングなど」、FOM 電子メール リスト。2007 年 10 月 29 日。
• Martin Davis、2007、「最小の汎用マシン」、および汎用チューリング マシンの定義 FOM 電子メール リスト。2007 年 10 月 26 ～ 27 日。
• Alasdair Urquhart、2007 年「最小のユニバーサル マシン」、FOM 電子メール リスト。2007 年 10 月 26 日。
• Hector Zenil (Wolfram Research)、2007 年「最小の汎用マシン」、FOM 電子メール リスト。2007 年 10 月 29 日。
• Todd Rowland、2007、「FOM に関する混乱」、Wolfram Science メッセージ ボード、2007 年 10 月 30 日。
• Olivier と Marc RAYNAUD、2014、「チューリング マシンを実現するためのプログラム可能なプロトタイプ」 、Wayback Machineに 2016 年 1 月 14 日にアーカイブされました。「ブレーズ パスカル大学 (フランス、クレルモン フェラン) の LIMOS 研究所」。

• マーティン・デイビス(2000)。『論理エンジン: 数学者とコンピュータの起源』 (第 1 版)。WW ノートン & カンパニー、ニューヨーク。ISBN 978-0-393-32229-3。
• ロビン・ガンディ、「1936 年の思想の合流」、ロルフ・ヘルケン著 51 ～ 102 ページ、下記参照。
• スティーブン・ホーキング（編）、2005年、「神は整数を創造した：歴史を変えた数学的ブレークスルー」、ランニング・プレス、フィラデルフィア、ISBN 978-0-7624-1922-7。チューリングの1936～1937年の論文と、ホーキングによるチューリングの短い解説と伝記が含まれています。 
• ロルフ・ヘルケン (1995)。『ユニバーサル・チューリングマシン 半世紀の調査』。シュプリンガー・フェアラーク。ISBN 978-3-211-82637-9。
• アンドリュー・ホッジス著『アラン・チューリング：エニグマ』、サイモン＆シュスター、ニューヨーク。彼の証明に至る歴史と議論については、「真実の精神」の章を参照。
• アイヴァース・ピーターソン(1988)。『数学の旅人: 現代数学のスナップショット』 (第 1 版)。WH フリーマン アンド カンパニー、ニューヨーク。ISBN 978-0-7167-2064-5。
• ロジャー・ペンローズ、『皇帝の新しい心：コンピュータ、心、そして物理法則について』、オックスフォード大学出版局、オックスフォードおよびニューヨーク、1989年（1990年訂正）、ISBN 0-19-851973-7。 
• ポール・ストラザーン（1997年）。『チューリングとコンピュータ ― ビッグアイデア』アンカー・ブックス/ダブルデイ。ISBN 978-0-385-49243-0。
• Hao Wang、「チューリングの計算機理論の変種」、Journal of the Association for Computing Machinery (JACM) 4、63–92 (1957)。
• チャールズ・ペッツォルド『注釈付きチューリング』、ジョン・ワイリー・アンド・サンズ社、ISBN 0-470-22905-5 
• Arora, Sanjeev、Barak, Boaz、「複雑性理論: 現代的アプローチ」、ケンブリッジ大学出版局、2009 年、ISBN 978-0-521-42426-4、セクション 1.4「文字列としてのマシンと汎用チューリング マシン」および 1.7「定理 1.9 の証明」 
• Kantorovitz, Isaiah Pinchas (2005 年 12 月 1日)。 「ルール駆動システムのチューリング マシン計算可能性に関するメモ」。SIGACT ニュース。36 (4): 109–110。doi : 10.1145 /1107523.1107525。S2CID  31117713。
• キルナー、ライムンド。ウルフ・ツィンマーマン。 Richter, Dirk: 「実際のプログラミング言語の決定不可能性の結果について」、15. Kolloquium Programmierspra​​chen und Grundlagen der Programmierung (KPS'09)、Maria Taferl、オーストリア、2009 年 10 月。

• 「チューリングマシン」、数学百科事典、EMS Press、2001 [1994]
• チューリングマシン –スタンフォード哲学百科事典
• Wolfram デモンストレーション プロジェクトの一環として Enrique Zeleny が作成した Turing Machine Causal Networks 。