ユニバーサルチューリングマシン
コンピューターサイエンスでは、 ユニバーサルチューリングマシン （ UTM ）は、任意の入力で任意のチューリングマシンをシミュレートできるチューリングマシンです。ユニバーサルマシンは、シミュレートするマシンの説明と、独自のテープからの入力の両方を読み取ることにより、基本的にこれを実現します。アラン・チューリングは、1936年から1937年にそのような機械のアイデアを導入しました。この原理は、1946年にジョン・フォン・ノイマンがフォン・ノイマンの名前を冠した「電子計算機」のために使用したストアドプログラム・コンピューターのアイデアの起源であると考えられています。
計算の複雑さの観点から、マルチテープユニバーサルチューリングマシンは、シミュレートするマシンと比較して、対数係数だけ遅くなるだけで済みます。
前書き
すべてのチューリングマシンは、アルファベット上の入力文字列から特定の固定部分計算可能関数を計算します。その意味では、プログラムが固定されたコンピューターのように動作します。ただし、任意のチューリングマシンのアクションテーブルを文字列にエンコードできます。したがって、テープ上にアクションテーブルを記述する文字列とそれに続く入力テープを記述する文字列を期待し、エンコードされたチューリングマシンが計算するテープを計算するチューリングマシンを構築できます。チューリングは、1936年の論文でこのような構造を詳細に説明しました。
「それは、任意の計算順序を計算するために使用することができる単一のマシンを発明することが可能である。このマシンUは、いくつかの計算機MのSDを書かれるの先頭にテープで供給されている場合、Uは、同一の配列を計算しますMとして。」ストアドプログラムコンピューター
デービスは、「アクションテーブル」（マシンの指示）を入力データと同じ「メモリ」に配置するという、現在「ストアドプログラムコンピューター」として知られているもののチューリングの概念が、ジョンに強い影響を与えたと説得力のある議論を行いますフォン・ノイマンの最初のアメリカの離散記号（アナログではなく）コンピューターEDVACの概念。デイビスは、デイビス2000（「アラン・チューリングの仕事にジョン・フォン・ノイマン」「キーボードでタップ誰もが...、チューリングマシンの化身に取り組んでいる」とということを、この効果にタイム誌を引用：193 時間を引用します1999年3月29日の雑誌）。
Davisは、Turingの自動計算エンジン（ACE）コンピューターがマイクロプログラミング（マイクロコード）とRISCプロセッサーの概念を「予測」したと主張しています（Davis 2000：188）。 Knuthは、「サブルーチンリンケージを容易にするハードウェア」（Knuth 1973：225）の設計として、ACEコンピュータでのTuringの仕事を引用しています。デイビスはまた、この作業をハードウェア「スタック」のチューリングの使用として参照しています（Davis 2000：237 footnote 18）。
チューリングマシンがコンピューターの構築を奨励していたため、UTMは駆け出しのコンピューターサイエンスの発展を奨励していました。最初のアセンブラーではありませんが、初期のアセンブラーがEDVAC用に「若いホットショットプログラマーによって」提案されました（Davis 2000：192）。 Von Neumannの「最初の本格的なプログラム...データを効率的に単純にソートする」（Davis 2000：184）。 Knuthは、特殊レジスターではなくプログラム自体に埋め込まれたサブルーチンリターンは、フォンノイマンとゴールドスタインに起因することを観察しています。クヌースはさらに次のように述べています
「最初の解釈ルーチンは「ユニバーサルチューリングマシン」と言われるかもしれません...従来の意味での解釈ルーチンは、1946年のムーア学校での講義でジョンモークリーによって言及されました...チューリングもこの開発に参加しました。 Pilot ACEコンピューターの解釈システムは彼の指示の下で作成されました」（Knuth 1973：226）。Davisは、プログラムとしてのプログラムの概念の結果として、オペレーティングシステムとコンパイラについて簡単に言及しています（Davis 2000：185）。
ただし、一部の人はこの評価で問題を引き起こす可能性があります。当時（1940年代半ばから1950年代半ば）、比較的少数の研究者が新しい「デジタルコンピュータ」のアーキテクチャに密接に関与していました。この時点で若い研究者であるハオ・ワン（1954）は、次の観察を行いました。
チューリングの計算可能関数の理論は先行していますが、デジタルコンピュータの実際の大規模な構築にはあまり影響していません。理論と実践のこれら2つの側面は、ほぼ完全に独立して開発されてきました。主な理由は、間違いなく、論理学者は、応用数学者や電気技術者が主に関係しているものとは根本的に異なる質問に興味があることです。ただし、2つの開発において同じ概念が非常に異なる用語で表現されることが多いという、奇妙なものに失敗することはありません。」（Wang 1954、1957：63）ワンは、彼の論文が「2つのアプローチを結びつける」ことを望んでいた。確かに、ミンスキーはこれを確認します：「コンピューターのようなモデルにおけるチューリング機械理論の最初の定式化は、Wang（1957）に現れる」（Minsky 1967：200）。ミンスキーは、カウンターマシンのチューリング等価性を実証し続けています。
コンピューターの単純なチューリング等価モデルへの縮小（およびその逆）に関しては、ミンスキーの「最初の定式化」を行ったという王の指定は議論の余地があります。 1961年のミンスキーの論文と1957年のワンの論文は両方ともシェパードソンとスタージス（1963）に引用されていますが、ヨーロッパの数学者Kaphenst（1959）、Ershov（1959）、およびPéter（1958）の研究も引用して要約しています。数学者エルメス（1954、1955、1961）とカフェンスト（1959）の名前は、シェパードソンスタージス（1963年）とエルゴットロビンソン（1961年）の両方の書誌に表示されます。重要な他の2つの名前は、カナダの研究者Melzak（1961）とLambek（1961）です。詳細については、チューリングマシンの同等物をご覧ください。参照は、登録マシンで見つけることができます。
数理理論
アクションテーブルを文字列としてエンコードすることで、原則として、チューリングマシンが他のチューリングマシンの動作に関する質問に答えることが可能になります。ただし、これらの質問のほとんどは決定できません。つまり、問題の関数を機械的に計算することはできません。たとえば、任意のチューリングマシンが特定の入力で停止するか、すべての入力で停止するかを決定する問題は、一般に、チューリングの元の論文では決定できないことが示されています。ライスの定理は、チューリングマシンの出力に関する重要な問題は決定不能であることを示しています。
汎用チューリングマシンは、再帰関数を計算し、再帰言語を決定し、再帰的に列挙可能な言語を受け入れることができます。 Church-Turingの論文によれば、普遍的なチューリングマシンによって解決可能な問題は、それらの用語の合理的な定義のために、 アルゴリズムまたは効果的な計算方法によって解決可能な問題です。これらの理由により、ユニバーサルチューリングマシンは計算システムを比較するための標準として機能し、ユニバーサルチューリングマシンをシミュレートできるシステムはチューリング完全と呼ばれます。
ユニバーサルチューリングマシンの抽象バージョンは、他の計算可能な関数を計算するために使用できる計算可能な関数であるユニバーサル関数です。 UTM定理は、このような関数の存在を証明します。
効率
一般性を失うことなく、チューリングマシンの入力はアルファベット{0、1}であると仮定できます。他の有限アルファベットは{0、1}でエンコードできます。チューリングマシンMの動作は、その遷移関数によって決まります。この関数は、アルファベット{0、1}上の文字列としても簡単にエンコードできます。 Mのアルファベットのサイズ、それが持つテープの数、および状態空間のサイズは、遷移関数のテーブルから推定できます。区別された状態とシンボルは、それらの位置によって識別できます。たとえば、最初の2つの状態は慣例により開始状態と停止状態になります。その結果、すべてのチューリングマシンは、アルファベット{0、1}上の文字列としてエンコードできます。さらに、すべての無効なエンコーディングは、すぐに停止する些細なチューリングマシンにマップされ、すべてのチューリングマシンは、コメントのように、任意の数の（たとえば）1でエンコーディングをパディングすることにより、無限のエンコーディングを保持できることを招集しますプログラミング言語で作業する。ゲーデル数の存在と、チューリングマシンとμ再帰関数の間の計算的等価性を考えると、このエンコードを実現できることは驚くべきことではありません。同様に、この構造は、すべてのバイナリ文字列α 、チューリングマシンMαに関連付けられます。
上記のエンコーディングから始まり、1966年にFC HennieとRE Stearnsは、 Nステップ内で入力xで停止するチューリングマシンMαが与えられると、入力α 、 xで停止するマルチテープユニバーサルチューリングマシンが存在することを示しましたCNログNで、 Cは入力xの長さに依存しないマシン固有の定数ですが、 Mのアルファベットサイズ、テープの数、状態の数に依存します。事実上、これはドナルドクヌースのビッグO表記を使用したO（NlogN）{\ displaystyle {\ mathcal {O}} \ left（N \ log {N} \ right）}シミュレーションです。
最小のマシン
Alan Turingがユニバーサルマシンのアイデアを思いついたとき、計算可能なすべての関数を計算するのに十分強力な最も単純な計算モデルを念頭に置いていました。クロードシャノンは、1956年に可能な限り最小のユニバーサルチューリングマシンを見つけるという問題を最初に明示しました。十分な状態が使用される限り2つのシンボルで十分（またはその逆）であり、状態をシンボルと常に交換できることを示しました。
マービンミンスキーは、1962年に2タグシステムを使用した7ステートの4シンボルユニバーサルチューリングマシンを発見しました。他の小型汎用チューリングマシンは、タグシステムシミュレーションのこのアプローチを拡張することにより、Yurii Rogozhinなどによって発見されました。 （ m 、 n ）によって、 m個の状態とn個のシンボルを持つUTMのクラスを示す場合、次のタプルが見つかりました：（15、2）、（9、3）、（6、4）、（5、5）、 （4、6）、（3、9）、および（2、18）。 Rogozhinの（4、6）マシンは22命令のみを使用し、記述の複雑さの低い標準UTMは知られていない。
ただし、標準のチューリングマシンモデルを一般化すると、さらに小さなUTMが許可されます。そのような一般化の1つは、チューリングマシン入力の片側または両側で無限に繰り返される単語を許可することです。したがって、普遍性の定義を拡張し、それぞれ「半弱」または「弱」普遍性として知られています。 （6、2）、（3、3）、および（2、4）状態シンボルペアに対して、Rule 110セルオートマトンをシミュレートする小型で汎用性の低いチューリングマシンが提供されています。 Wolframの2状態3シンボルチューリングマシンの普遍性の証明は、特定の非周期的な初期構成を許可することにより、弱い普遍性の概念をさらに拡張します。小さなUTMを生成する標準的なチューリングマシンモデルの他のバリエーションには、複数のテープまたは複数の次元のテープを備えたマシン、および有限オートマトンと結合されたマシンが含まれます。
内部状態のないマシン
チューリングマシンで複数のヘッドを許可する場合、内部状態のないチューリングマシンを使用できます。 「状態」はテープの一部としてエンコードされます。たとえば、0、1、2、0A、1A、2Aの6色のテープがあるとします。 3頭のチューリングマシンがトリプル（2,2A、0）の上にある0,0,1,2,2A、0,2,1などのテープを考えます。次に、ルールは任意のトリプルを別のトリプルに変換し、3ヘッドを左右に移動します。たとえば、ルールは（2,2A、0）を（2,1,0）に変換し、頭を左に移動します。したがって、この例では、マシンは内部状態AおよびB（文字なしで表される）を持つ3色のチューリングマシンのように動作します。 2ヘッドチューリングマシンの場合は非常によく似ています。したがって、2ヘッドチューリングマシンは6色でユニバーサルにすることができます。マルチヘッドチューリングマシンに必要な色の最小数が何であるか、または複数ヘッドの2色ユニバーサルチューリングマシンが可能かどうかは不明です。また、トリプルルールは書き換えルールと同等であるため、書き換えルールはチューリング完全であることも意味します。文字をサンプリングし、8人の隣人でテープを2次元に拡張します。たとえば、110のような垂直のトリプルパターンで色をエンコードできるため、2色のみが必要です。
汎用マシンコーディングの例
Turingが指定したとおりにUTMを設計するという課題に取り組む人は、Davies in Copeland（2004：103ff）の記事を参照してください。 Daviesは元のエラーを修正し、サンプルの実行がどのようになるかを示します。彼は（ある程度単純化された）シミュレーションを正常に実行したと主張しています。次の例は、Turing（1936）からの抜粋です。この例の詳細については、チューリングマシンの例をご覧ください。
チューリングは7つのシンボルを使用しました{A、C、D、R、L、N 、; }各5タプルをエンコードします。チューリングマシンの記事で説明されているように、彼の5タプルはタイプN1、N2、およびN3のみです。各「m-構成」（命令、状態）の数は、「D」の後に単項文字列が続くことで表されます（例：「q3」= DAAA）。同様の方法で、彼は「D」として空白、「DC」として記号「0」、DCCとして記号「1」などの記号をエンコードします。記号「R」、「L」、および「N」はです。
次の表に示すように、各5タプルをエンコードした後、順番に文字列に「アセンブル」されます。
| 現在のm構成 | テープ記号 | 印刷操作 | テープモーション | 最終的なm構成 | 現在のm構成コード | テープ記号コード | 印刷操作コード | テープモーションコード | 最終的なm構成コード | 5タプルアセンブルコード | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| q1 | ブランク | P0 | R | q2 | DA | D | DC | R | DAA | DADDCRDAA | |
| q2 | ブランク | E | R | q3 | DAA | D | D | R | DAAA | DAADDRDAAA | |
| q3 | ブランク | P1 | R | q4 | DAAA | D | DCC | R | DAAAA | DAAADDCCRDAAAA | |
| q4 | ブランク | E | R | q1 | DAAAA | D | D | R | DA | DAAAADDRDA |
最後に、4つの5タプルすべてのコードは、「;」で始まるコードにまとめられます。 「;」で区切られますすなわち：
; DADDCRDAA ; DAADDRDAAA ; DAAADDCCRDAAAA ; DAAAADDRDAこのコードは、代替の正方形（「F正方形」）に配置され、「E正方形」（消去されやすい）を空のままにします。 Uマシンのテープ上のコードの最終アセンブリは、2つの特別なシンボル（ "e"）を次々に配置し、次にコードを交互の正方形に分離し、最後にダブルコロンシンボル " :: "で構成します。 （ここではわかりやすくするために空白を「。」で示しています）：
ええ。 ; .DADDCRDAA ; .DAADDRDAAA ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......Uマシンのアクションテーブル（状態遷移テーブル）は、シンボルのデコードを担当します。チューリングのアクションテーブルは、マーカー「u」、「v」、「x」、「y」、「z」で「マークされたシンボル」の右側の「E-squares」に配置することで、その場所を追跡します。 、現在の命令をマークするために、 zは「;」の右側に配置されます。 xは、現在の「m構成」DAAに関して場所を維持しています。 Uマシンのアクションテーブルは、計算の進行に合わせてこれらのシンボルを往復させます（それらを消去して異なる場所に配置します）。
ええ。 ; .DADDCRDAA ; z D.AA x D.DRDAAA ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......Uマシンのチューリングのアクションテーブルは非常に複雑です。
他の多くのコメンテーター（特にPenrose 1989）は、ユニバーサルマシンの命令をエンコードする方法の例を提供します。ペンローズと同様に、ほとんどのコメンテーターはバイナリシンボルのみを使用します。つまり、シンボル{0、1}、または{blank、mark | }。ペンローズはさらに進んで、U-machineコード全体を書きます（Penrose 1989：71–73）。彼はそれが本当にU-machineコードであり、1と0のほぼ2ページに及ぶ膨大な数であると断言します。 Post-Turingマシンのより単純なエンコーディングに興味のある読者にとっては、Davis in Steen（Steen 1980：251ff）の議論が役に立つかもしれません。
AspertiとRicciottiは、完全なアクションテーブルを明示的に提供するのではなく、非常に単純なセマンティクスで基本マシンを構成することによって定義されるマルチテープUTMについて説明しました。このアプローチは十分にモジュール化されており、Matita proof Assistantでマシンの正確性を正式に証明できます。
プログラミングチューリングマシン
さまざまな高レベル言語がチューリングマシンにコンパイルされるように設計されています。例には、LaconicおよびTuring Machine記述子が含まれます。
