Loading article…
コンピュータ科学において、ユニバーサルチューリングマシン（UTM）とは、アラン・チューリングが画期的な論文「計算可能な数について、決定問題への応用」で述べたように、任意の計算可能な数列を計算できるチューリングマシンである[ 1 ]。言い換えれば、他のあらゆる特殊チューリングマシンをシミュレートできるチューリングマシンである。
常識的に考えれば万能機械は不可能だと思うかもしれないが、チューリングはそれが可能であることを証明した。[ a ]彼は、実数を計算する人間の過程を、有限個の条件しか処理できない機械と比較できると示唆した。 ; これらは「 m構成」と呼ばれる。 [ 2 ]彼は次に、以下に説明するように、そのような機械の動作を説明し、次のように主張した。
これらの演算には、数値の計算に使用されるすべての演算が含まれるというのが私の主張である。[ 3 ]
チューリングは1936年から1937年にかけて、そのような機械のアイデアを提唱した。
マーティン・デイビスは、チューリングが考案した、現在「プログラム内蔵型コンピュータ」として知られる概念、すなわち「アクションテーブル」（機械への命令）を入力データと同じ「メモリ」に配置するという概念が、ジョン・フォン・ノイマンによる最初のアメリカ製離散記号（アナログとは対照的）コンピュータであるEDVACの構想に強く影響を与えたという説得力のある主張を展開している。デイビスは、この点に関してタイム誌の記事を引用し、「キーボードを叩く人は皆 、チューリングマシンの具現化に取り組んでいる」とし、「ジョン・フォン・ノイマンはアラン・チューリングの研究の上に築いた」と述べている。[ 4 ]
デイビスは、チューリングの自動計算エンジン（ACE）コンピュータがマイクロプログラミング（マイクロコード）とRISCプロセッサの概念を「先取り」していたと主張している。[ 5 ]ドナルド・クヌースは、 ACEコンピュータに関するチューリングの研究を「サブルーチンリンクを容易にするハードウェアの設計」として引用している。[ 6 ]デイビスはまた、この研究をチューリングのハードウェア「スタック」の使用として言及している。[ 7 ]
チューリングマシンがコンピュータの構築を促したように、UTMは黎明期のコンピュータ科学の発展を促した。EDVAC向けに「若き敏腕プログラマー」によって、最初のアセンブラではないにしても、初期のアセンブラが提案された。[ 8 ]フォン・ノイマンの「最初の本格的なプログラム…[は]単にデータを効率的にソートすることだった」。[ 9 ]クヌースは、サブルーチンの戻り値を特別なレジスタではなくプログラム自体に埋め込むのはフォン・ノイマンとゴールドスタインによるものだと指摘している。[ b ]さらにクヌースは、
最初の解釈ルーチンは「ユニバーサルチューリングマシン」と言えるでしょう...従来の意味での解釈ルーチンは、 1946年にジョン・モークリーがムーアスクールで行った講義で言及されました...チューリングもこの開発に参加し、パイロットACEコンピュータ用の解釈システムは彼の指導の下で作成されました。[ 10 ]
デイビスは、プログラム・アズ・データの概念の結果として、オペレーティングシステムとコンパイラについて簡単に言及している。[ 11 ]
アクションテーブルを文字列として符号化することで、原理的にはチューリングマシンが他のチューリングマシンの振る舞いに関する質問に答えることが可能になる。しかし、これらの質問のほとんどは決定不能であり、つまり、問題となっている関数を機械的に計算することはできない。例えば、任意のチューリングマシンが特定の入力で停止するか、すべての入力で停止するかを決定する問題（停止問題として知られる）は、チューリングの原著論文で一般に決定不能であることが示された。ライスの定理は、チューリングマシンの出力に関する非自明な質問はすべて決定不能であることを示している。
万能チューリングマシンは、あらゆる再帰関数を計算し、あらゆる再帰言語を判定し、あらゆる再帰的に列挙可能な言語を受理することができます。チャーチ＝チューリングのテーゼによれば、万能チューリングマシンで解決できる問題は、アルゴリズムまたは効率的な計算方法によって解決できる問題と全く同じであり、これらの用語の妥当な定義は問いません。こうした理由から、万能チューリングマシンは計算システムを比較するための基準として用いられ、万能チューリングマシンをシミュレートできるシステムはチューリング完全であると言われます。
普遍チューリングマシンの抽象的なバージョンは普遍関数であり、これは他のあらゆる計算可能な関数を計算するために使用できる計算可能な関数である。UTM定理は、このような関数の存在を証明する。
一般性を失うことなく、チューリングマシンの入力はアルファベット {0, 1} であると仮定できます。他の有限アルファベットも {0, 1} 上にエンコードできます。チューリングマシンMの動作は、その遷移関数によって決定されます。この関数も、アルファベット {0, 1} 上の文字列として容易にエンコードできます。M のアルファベットのサイズ、テープの数、状態空間のサイズは、遷移関数の表から推測できます。区別された状態と記号は、その位置によって識別できます。たとえば、最初の 2 つの状態は、慣例として開始状態と停止状態にすることができます。したがって、すべてのチューリングマシンは、アルファベット {0, 1} 上の文字列としてエンコードできます。さらに、すべての無効なエンコードは、即座に停止する自明なチューリングマシンにマッピングされ、プログラミング言語のコメントのように、エンコードの末尾に任意の数の (たとえば) 1 をパディングすることで、すべてのチューリングマシンは無限の数のエンコードを持つことができると仮定します。ゲーデル数の存在とチューリングマシンとμ再帰関数の計算上の等価性を考慮すると、この符号化が実現できることは驚くべきことではないはずです。同様に、私たちの構成では、すべてのバイナリ文字列αにチューリングマシンMαが対応付けられます。
上記のエンコーディングから出発して、1966年にFC HennieとRE Stearnsは、Nステップ以内に入力xで停止するチューリングマシンMαが与えられた場合、入力α、x（異なるテープで与えられる）でCN log Nで停止するマルチテープユニバーサルチューリングマシンが存在することを示した。ここで、Cはマシン固有の定数であり、入力xの長さには依存しないが、 Mのアルファベットサイズ、テープの数、および状態の数に依存する。これは実質的にドナルド・クヌースのビッグオー記法を用いたシミュレーション。[ 12 ]時間計算量ではなく空間計算量に対応する結果は、計算のどの段階でも最大でCN個のセルを使用する方法でシミュレーションできるということである。シミュレーション。[ 13 ]
アラン・チューリングが万能機械の構想を思いついたとき、彼が念頭に置いていたのは、計算可能なすべての関数を計算できるほど強力な、最も単純な計算モデルだった。クロード・シャノンは1956年に、最小の万能チューリング機械を見つけるという問題を初めて明確に提起した。彼は、十分な状態が用いられていれば2つの記号で十分であること（あるいはその逆も然り）、そして状態と記号は常に交換可能であることを示した。また、1つの状態からなる万能チューリング機械は存在し得ないことも示した。
マービン・ミンスキーは、 1962 年に2 タグ システムを使用して 7 状態 4 シンボルのユニバーサル チューリング マシンを発見しました。その後、ユーリ・ロゴジンらが、このタグ システム シミュレーションのアプローチを拡張して、他の小型ユニバーサル チューリング マシンを発見しました。m状態、nシンボルの UTM のクラスを (m, n)とすると、次のタプルが見つかっています: (15, 2)、(9, 3)、(6, 4)、(5, 5)、(4, 6)、(3, 9)、(2, 18)。[ 14 ] [ 15 ] [ 16 ]ロゴジンの (4, 6) マシンは 22 個の命令しか使用せず、これより記述の複雑さが低い標準的な UTM は知られていません。
しかし、標準チューリングマシンモデルを一般化すると、さらに小さなUTMが実現します。そのような一般化の1つは、チューリングマシンの入力の片側または両側に無限に繰り返される単語を許容することで、普遍性の定義を拡張し、それぞれ「半弱普遍性」または「弱普遍性」として知られています。ルール110セルオートマトンをシミュレートする小さな弱普遍チューリングマシンは、(6, 2)、(3, 3)、および(2, 4)状態-記号ペアに対して与えられています。[ 17 ] Wolframの2状態3記号チューリングマシンの普遍性の証明は、特定の非周期的な初期構成を許容することで、弱普遍性の概念をさらに拡張しています。小さなUTMを生み出す標準チューリングマシンモデルの他の変種には、複数のテープまたは多次元のテープを持つマシン、および有限オートマトンと結合されたマシンが含まれます。
チューリングマシンで複数のヘッドが連続するテープ位置を読み取ることが許される場合、内部状態は必要ありません。なぜなら、「状態」はテープにエンコードできるからです。たとえば、0、1、2、0A、1A、2A の 6 色のテープを考えてみましょう。0、0、1、2、2A、0、2、1 のようなテープを考え、3 ヘッドのチューリングマシンがトリプル (2、2A、0) の上に配置されているとします。ルールは、任意のトリプルを別のトリプルに変換し、3 つのヘッドを左右に移動させます。たとえば、ルールは (2、2A、0) を (2、1、0) に変換し、ヘッドを左に移動させるかもしれません。したがって、この例では、マシンは内部状態 A と B (文字で表されない) を持つ 3 色のチューリングマシンのように動作します。2 ヘッドのチューリングマシンの場合も非常に似ています。したがって、内部状態を持たない 2 ヘッドのチューリングマシンは、6 色でユニバーサルになります。マルチヘッドチューリングマシンに必要な最小の色数がいくつなのか、また、内部状態を持たない 2 色のユニバーサルチューリングマシンが複数のヘッドで可能かどうかは不明です。また、 3 文字ルールが書き換えルールと等価であるため、書き換えルールはチューリング完全であることを意味します。文字とその 8 つの隣接文字をサンプリングするヘッドでテープを 2 次元に拡張すると、たとえば 110 のような垂直の 3 つのパターンで色をエンコードできるため、2 色しか必要ありません。
また、2つのヘッド間の距離が可変である場合（テープにヘッド間の「たるみ」がある場合）、任意のポストタグシステムをシミュレートすることができ、その中には汎用的なものもあります。[ 18 ]
チューリングが指定したとおりにUTMを設計するという難題に挑戦したい方は、コープランド（2004）に掲載されているデイヴィスの記事を参照してください。デイヴィスは元の記事の誤りを訂正し、実行例を示しています。彼は（やや簡略化された）シミュレーションを正常に実行しました。
以下の例はチューリング（1937）から引用したものです。この例の詳細については、「チューリングマシンの例」を参照してください。
チューリングは、各 5 タプルをエンコードするために 7 つの記号 { A, C, D, R, L, N, ; } を使用しました。記事「チューリングマシン」で説明されているように、彼の 5 タプルは N1、N2、N3 のタイプのみです。各「 m構成」（命令、状態）の番号は、「D」に続いて A の単項文字列で表されます。たとえば、「q3」= DAAA です。同様に、彼は記号を空白として「D」、記号「0」を「DC」、記号「1」を DCC などとしてエンコードします。記号「R」、「L」、「N」はそのままです。
エンコード後、各5タプルは次の表に示す順序で文字列に「組み立て」られます。
最後に、4 つの 5 タプルすべてのコードを「;」で始まり「;」で区切られたコードに連結します。例:
彼はこのコードを交互に「Fマス」に配置し、「Eマス」（消去可能なマス）は空のままにした。Uマシン用のテープ上のコードの最終的な組み立ては、2つの特殊記号（「e」）を連続して配置し、次にコードを交互にマスに配置し、最後に二重コロン記号「::」を配置することから構成される（ここでは分かりやすくするために空白を「.」で示している）。
Uマシンのアクションテーブル（状態遷移テーブル）は、シンボルのデコードを担当します。チューリングのアクションテーブルは、マーカー「u」、「v」、「x」、「y」、「z」を用いて、マークされたシンボルの右側にある「Eスクエア」内にそれらを配置することで、現在位置を追跡します。例えば、現在の命令をマークするために、zは「;」の右側に配置され、 xは現在の「 m構成」DAAに対する位置を保持します。Uマシンのアクションテーブルは、計算の進行に伴い、これらのシンボルを移動（消去したり、異なる場所に配置したり）します。
チューリングのUマシンにおける動作表は非常に複雑である。
ロジャー・ペンローズは、バイナリ記号{0, 1}または{空白、マーク|}のみを使用してユニバーサルマシンの命令をエンコードする方法の例を示しています。ペンローズはさらに進んで、Uマシンコード全体を書き出しています。彼は、それが真にUマシンコードであり、1と0でほぼ2ページにわたる膨大な数であると主張しています。[ 19 ]
AspertiとRicciottiは、完全なアクションテーブルを明示的に与えるのではなく、非常に単純な意味論を持つ基本マシンを組み合わせることによって定義されるマルチテープUTMについて説明した。このアプローチは十分にモジュール化されており、Matita証明支援システムでマシンの正当性を形式的に証明することができた。[ 20 ]
「文字列としての機械と万能チューリングマシン」および 1.7「定理 1.9 の証明」
