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 は、入力xでNステップ以内に停止するチューリング マシンM αが与えられた場合、入力α、x (異なるテープで与えられる) でCN log Nで停止するマルチテープ汎用チューリング マシンが存在することを示した。ここで、Cはマシン固有の定数で、入力xの長さには依存しないが、 M のアルファベット サイズ、テープ数、および状態数に依存する。これは実質的に、ドナルド クヌースのBig O 表記法を使用したシミュレーションである。 [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 ヘッド チューリング マシンが 3 つの値 (2、2A、0) の上にあります。次に、ルールによって任意の 3 つの値を別の 3 つの値に変換し、3 つのヘッドを左または右に移動します。たとえば、ルールによって (2、2A、0) が (2、1、0) に変換され、ヘッドが左に移動します。したがって、この例では、マシンは内部状態 A と B (文字で表されない) を持つ 3 色チューリング マシンのように動作します。2 ヘッド チューリング マシンの場合も非常に似ています。したがって、2 ヘッド チューリング マシンは 6 色でユニバーサルになります。マルチヘッド チューリング マシンに必要な色の最小数や、複数のヘッドで 2 色のユニバーサル チューリング マシンが実現可能かどうかは不明です。また、 3 重規則は書き換え規則と同等であるため、書き換え規則はチューリング完全であることを意味します。テープを 2 次元に拡張し、ヘッドが 1 つの文字とその 8 つの隣接文字をサンプリングすると、必要な色は 2 色のみになります。たとえば、色は 110 などの垂直の 3 重パターンでエンコードできます。
また、2つのヘッド間の距離が可変である場合（テープのヘッド間に「たるみ」がある場合）、いくつかのユニバーサルなポストタグシステムをシミュレートできます。 [18]
コーディング例
チューリングの指示どおりに UTM を設計するという課題に取り組みたい人は、Copeland (2004) の Davies の記事を参照してください。Davies は、元の記事の誤りを修正し、サンプルの実行がどのようなものになるかを示しています。彼は (多少簡略化された) シミュレーションを正常に実行しました。
次の例は、Turing (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 組のコードすべてが、「;」で始まり、「;」で区切られたコードに連結されます。つまり、次のようになります。
;ダッドクラダア; DAADDRDAAA ;だああああああああああ;ダアアドルダ
このコードは、交互に「F のマス目」に配置され、「E のマス目」(消去される可能性のあるマス目) は空白のままです。U マシンのテープ上のコードの最終的な組み立ては、2 つの特殊記号 (「e」) を次々に配置し、次に交互にマス目に分けたコード、最後に二重コロン記号「::」(ここではわかりやすくするために空白を「.」で示しています) で構成されます。
ええ。; .DADDCRDAA ; .DAADDRDAAA ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......
U マシンのアクション テーブル (状態遷移テーブル) は、シンボルのデコードを担当します。チューリングのアクション テーブルは、マーカー「u」、「v」、「x」、「y」、「z」を「マークされたシンボル」の右側の「E スクエア」に配置することで、その位置を追跡します。たとえば、現在の命令をマークするには、z を「;」の右側に配置します 。x は、現在の「m 構成」DAA に対する位置を維持します。U マシンのアクション テーブルは、計算の進行に合わせてこれらのシンボルを移動します (シンボルを消去して別の場所に配置します)。
ええ。; .DADDCRDAA ; z D.AA x D.DRDAAA ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......
チューリングの U マシンのアクション テーブルは非常に複雑です。
ロジャー・ペンローズは、ユニバーサルマシンの命令をバイナリシンボル{0,1}または{空白、マーク|}のみを使用してエンコードする方法の例を示しています。ペンローズはさらに進んで、Uマシンコード全体を書き出しました。彼は、それがまさにUマシンコードであり、1と0でほぼ2ページにわたる膨大な数であると主張しています。[19]
アスペルティとリッチオッティは、完全なアクションテーブルを明示的に与えるのではなく、非常に単純なセマンティクスを持つ基本マシンを組み合わせることで定義されたマルチテープUTMについて説明しました。このアプローチは十分にモジュール化されており、マティタ証明支援システムでマシンの正しさを正式に証明することができました。[20]
参照
- 交代チューリングマシン – 抽象計算モデル
- カウンターマシン – 形式論理と理論計算機科学で使用される抽象マシン
- クリーネの T 述語 – 計算可能性理論の概念
- マークとスペース – 通信信号の状態
- チューリングマシン相当物 – 仮想的な計算装置
- フォン・ノイマンのユニバーサル・コンストラクタ – 自己複製セルオートマトン
注記
- ^ ジョン・フォン・ノイマンの講義記録より。Copeland & Fan (2023) で Copeland が引用。
- ^ 特に: バークス、ゴールドスタイン、フォン・ノイマン (1971) [1946]。
参考文献
脚注
- ^ チューリング（1937年）、241ページ。
- ^ チューリング（1937年）、231ページ。
- ^ チューリング（1937年）、232ページ。
- ^ Davis (2000)、p. 193、 1999年3月29日のタイム誌を引用。
- ^ デイビス（2000）、188ページ。
- ^ クヌース（1973）、225ページ。
- ^ Davis (2000)、p.237脚注18。
- ^ デイビス（2000）、192ページ。
- ^ デイビス（2000）、184ページ。
- ^ クヌース（1973）、226ページ。
- ^ デイビス（2000）、185ページ。
- ^ アローラ＆バラク（2009）、定理1.9。
- ^ Arora & Barak (2009)、演習4.1。
- ^ ロゴジン（1996年）。
- ^ クドレック＆ロゴジン（2002年）。
- ^ ニアリー＆ウッズ（2009年）。
- ^ ニアリー＆ウッズ（2009b）。
- ^ ミンスキー（1967）、269ページ。
- ^ ペンローズ（1989）、71-73頁。
- ^ アスペルティ＆リチョッティ（2015年）。
原文と訂正
- チューリング、AM (1937)。「計算可能数について、そして計算問題への応用」(PDF)。ロンドン数学会紀要。2. 42 (1 ) : 230–265。doi :10.1112/plms/s2-42.1.230。
- チューリング、AM (1938)。「計算可能数について、その計算問題への応用：訂正」。ロンドン数学会紀要。2. 43 ( 6): 544–6。doi :10.1112/plms/s2-43.6.544。
その他の引用文献
- アローラ、サンジーヴ、バラク、ボアズ (2009)。複雑性理論：現代的アプローチ。ケンブリッジ大学出版局。ISBN 978-0-521-42426-4セクション
1.4「文字列としてのマシンと汎用チューリングマシン」および 1.7「定理 1.9 の証明」
- Asperti, Andrea; Ricciotti, Wilmer (2015). 「マルチテープチューリングマシンの形式化」.理論計算機科学. 603 : 23–42. doi :10.1016/j.tcs.2015.07.013. hdl : 11585/536349 . MR 3406235.
- Burks, Arthur W.; Goldstine, Herman H.; von Neumann, John (1971) [1946]. 「電子計算機器の問題の計画とコーディング」。 Bell, C. Gordon、Newell, Allen (編)。コンピュータ構造: 読み物と例。 ニューヨーク: McGraw-Hill Book Company。 pp. 92–119。ISBN 0-07-004357-4。
- コープランド、ジャック編 (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。
- Copeland, BJ; Fan, Z. (2023). 「チューリングとフォン・ノイマン: 論理からコンピュータへ」.哲学. 8 (22): 22. doi : 10.3390/philosophies8020022 .
- デイビス、マーティン(1980)。「計算とは何か?」スティーン、リン・アーサー(編) 『今日の数学: 12 の非公式エッセイ』。ニューヨーク: ヴィンテージ ブックス (ランダム ハウス) 。ISBN 978-0-394-74503-9。
- デイビス、マーティン (2000)。『論理エンジン: 数学者とコンピュータの起源』 (第 1 版)。ニューヨーク: WW ノートン & カンパニー。ISBN 0-393-32229-7。
- Hennie, FC; Stearns, RE (1966). 「マルチテープチューリングマシンの2テープシミュレーション」Journal of the ACM . 13 (4): 533. doi :10.1145/321356.321362. S2CID 2347143.
- Knuth, Donald E. (1973)。『コンピュータプログラミングの技法』第 1 巻: 基本アルゴリズム (第 2 版)。Addison-Wesley Publishing Company。
- Kudlek, Manfred; Rogozhin, Yurii (2002)。「3 つの状態と 9 つのシンボルを持つユニバーサル チューリング マシン」。Kuich, Werner、Rozenberg, Grzegorz、Salomaa, Arto (編)。言語理論の発展: 第 5 回国際会議、DLT 2001ウィーン、オーストリア、2001 年 7 月 16 ～ 21 日、改訂版論文。コンピュータ サイエンスの講義ノート。第 2295 巻。Springer。pp. 311 ～ 318。doi :10.1007/3-540-46011- x_27。ISBN 978-3-540-43453-5。
- ミンスキー、マービン・リー（1967年）。計算：有限マシンと無限マシン。プレンティス・ホール。ISBN 978-0-13-165563-8。
- Neary, Turlough; Woods, Damien (2009). 「4つの小型汎用チューリングマシン」(PDF) . Fundamenta Informaticae . 91 (1): 123–144. doi :10.3233/FI-2009-0036.
- Neary, Turlough、Woods, Damien (2009b)。「小型の弱汎用チューリングマシン」。第 17 回計算理論基礎国際シンポジウム。コンピュータサイエンスの講義ノート。第 5699 巻。Springer。pp. 262–273。
- ペンローズ、ロジャー（1989年）。『皇帝の新しい心』オックスフォード、イギリス：オックスフォード大学出版局。ISBN 0-19-851973-7。
- Rogozhin, Yurii (1996). 「小型汎用チューリングマシン」.理論計算機科学. 168 (2): 215–240. doi : 10.1016/S0304-3975(96)00077-1 .
さらに読む
- Arbib, MA (1988)。「ユニバーサル チューリング マシンから自己複製へ」。Herken, R. (編)。ユニバーサル チューリング マシンに関する半世紀にわたる調査。オックスフォード大学出版局。177 ～ 189 ページ。ISBN 978-0-19-853741-0。
- デイヴィス、マーティン編 (1965)。『The Undecidable』ヒューレット、ニューヨーク：レイヴン・プレス。
- デイビス、マーティン（2018）。ユニバーサルコンピュータ：ライプニッツからチューリングへの道。テイラー＆フランシスグループ。ISBN 978-1138413931。
- ヘルケン、ロルフ (1995)。『ユニバーサルチューリングマシン：半世紀の調査』。シュプリンガー出版。ISBN 3-211-82637-8。
- ミンスキー、マービン(1962)。 「タグシステム、再帰関数理論を使用したユニバーサルチューリングマシンのサイズと構造」。Proc . Symp. Pure Mathematics。5。プロビデンス RI: アメリカ数学会: 229–238。doi : 10.1090/pspum/005/0142452。
- シャノン、クロード(1956)。「2 つの内部状態を持つ汎用チューリング マシン」。オートマトン研究。プリンストン、ニュージャージー: プリンストン大学出版局。pp. 157–165。
外部リンク
- スミス、アルヴィ・レイ。「名刺サイズのユニバーサルチューリングマシン」（PDF） 。 2020年1月2日閲覧。