ウルフラムの2状態3記号チューリングマシン

スティーブン・ウルフラムは著書『A New Kind of Science』の中で、汎用的な2状態5記号チューリングマシンについて説明し、特定の2状態3記号チューリングマシン（以下、(2,3)チューリングマシン）も汎用的である可能性があると推測した。[ 1 ]

2007年5月14日、ウルフラムは(2,3)チューリングマシンの普遍性を最初に証明または反証した人物に2万5000ドルの賞金を授与すると発表した。[ 2 ] 2007年10月24日、バーミンガム大学で電子工学とコンピューターを専攻する学生、アレックス・スミスが、 (2,3)チューリングマシンが「普遍的」であることを証明したことでこの賞を受賞したことが発表された。この証明は、無限かつ非周期的な初期設定を許容し、決して停止しない非標準的なチューリングマシンモデルに適用されるため、一部の人々からは「弱普遍的」と分類されている。[ 3 ]

背景

クロード・シャノンは1956 年に初めて、可能な限り最小の汎用チューリング マシンを見つけるという問題を明確に提起しました。彼は、十分な状態が使用されている限り 2 つのシンボルで十分であり (またはその逆)、常に状態をシンボルと交換できることを示しました。

ミンスキー（1967）は、標準的な（2,2）マシンは汎用性がないことを簡潔に論じ、M. マーゲンシュテルン（2010）は、L. パブロツカヤによる1973年の結果（未発表だがマーゲンシュテルンの論文で言及されている）に基づく数学的証明[ 4 ]を示した。これらの証明は、有限の入力が与えられ、完了時に停止しなければならない通常のチューリングマシンモデルに適用される。ウルフラムのマシンは、これらの制約のいずれも満たしていない。

コンピュータ科学者が一般的に用いるチューリングマシンモデルには、様々なバリエーションがあります。これらのバリエーションには、テープ数、テープが双方向無限か片方向無限か、マシンヘッドの位置が一定か、遷移ごとに必ず移動するか、TM命令でヘッドの移動とシンボルの書き込みを同じステップで同時に実行できるか、などが含まれます。これらのモデルごとに、「可能な限り最小の汎用チューリングマシン」は異なります。したがって、Wolframのマシンは、その（特に非標準的な）モデルにおいてのみ「可能な限り最小の汎用チューリングマシン」と言えるでしょう。

説明

次の表は、チューリング マシンの現在の状態がAかBか、および現在読み取られているシンボルが 0、1、または 2 であるかどうかに応じて、チューリング マシンによって実行されるアクションを示しています。表のエントリは、印刷されるシンボル、テープ ヘッドが移動する方向、およびマシンのその後の状態を示しています。

あB
0 P1、R、BP2、L、A
1 P2、L、AP2、R、B
2 P1、L、AP0、R、A

(2,3)チューリングマシン:

  • 停止状態はありません。
  • 状態、シンボル、方向の交換により、他の 23 台のマシンと簡単に関連付けられます。

場所: 左

特定の行のヘッドの状態 (上または下の液滴 (それぞれ A と B)) と色のパターン (それぞれ白、黄色、オレンジ (0、1、2)) は、そのすぐ上の行の内容によってのみ決まります。

この機械には2つの状態しかないヘッドと、3色しか記録できないテープ（テープの初期内容によって異なる）があるにもかかわらず、機械の出力は任意に複雑になる可能性がある。[ 5 ]

普遍性の証明

2007年10月24日、バーミンガム大学（英国）の電子工学とコンピューター科学の学生であるアレックス・スミスが（2,3）チューリングマシンが汎用的であることを証明し、前述のウルフラム賞を受賞したことがウルフラム・リサーチによって発表された。[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ]

証明によれば、このマシンは、既に普遍的であることが知られているタグ システムのバリエーションと等価である。スミスはまず、(2,3) チューリング マシンが任意の有限計算を実行できることを示すルール システムのシーケンスを構築した。次に、斬新なアプローチを採用して、その構築を無制限の計算に拡張した。証明は 2 段階で行われる。最初の部分では、任意の 2 色巡回タグ システムの有限進化をエミュレートする。このエミュレーションは、インデックス付きルール システム「システム 0」から「システム 5」を含む一連のエミュレーションを組み合わせたものである。各ルール システムは、シーケンス内の次のルール システムをエミュレートする。次にスミスは、(2,3) チューリング マシンの初期条件は反復的でないが、その初期条件の構築は普遍的ではないことを示した。したがって、(2,3) チューリング マシンは普遍的である。

ウルフラムは、スミスの証明はウルフラムの一般的な「計算等価性の原理」（PCE）のもう一つの証拠であると主張している。[ 17 ]この原理は、明らかに単純ではない動作が見られた場合、その動作は、ある意味で「最大限に洗練された」計算に対応すると述べている。[ 18 ]スミスの証明は、チューリングマシンが汎用マシンの候補となるために満たさなければならない正確な動作条件に関する議論を引き起こした。

汎用(2,3)チューリングマシンには様々な応用が考えられます。[ 19 ]例えば、このように小型で単純なマシンは、少数の粒子や分子を用いて組み込んだり構築したりすることができます。しかし、スミスのアルゴリズムが示唆する「コンパイラ」は、少なくとも最も単純なケースを除いて、コンパクトで効率的なコードを生成しません。そのため、生成されるコードは天文学的な規模になり、非常に非効率になりがちです。(2,3)チューリングマシンの計算速度を向上させる、より効率的なコーディングが存在するかどうかは、未解決の問題です。

紛争

アレックス・スミスの証明が優勝したという発表は審査委員会の承認なしに行われた。[ 20 ]委員会メンバーのマーティン・デイビスはFOMメーリングリストへの投稿で次のように述べている。

「私の知る限り、委員会のどのメンバーもこの40ページに及ぶ証明の妥当性を認めていません。スミスの証明が正しいという判断は、ウォルフラム社によって完全になされたようです。私の理解では、I/Oには複雑な符号化が関わっているようです。」[ 21 ]

その後、ヴォーン・プラットはメーリングリストへの投稿でこの証明の正しさに異議を唱え、[ 22 ]同様の技術を用いれば線形有界オートマトン（LBA）を普遍的にすることができるが、これはノーム・チョムスキーによる既知の非普遍性の結果と矛盾すると指摘した。アレックス・スミスはこのメッセージの後メーリングリストに参加し、翌日返信し、LBAは同じ初期設定を使用して普遍的にするために手動で再起動する必要があるが、彼の構成ではチューリングマシンが外部からの介入なしに自動的に再起動されると説明した。[ 23 ]証明に関する議論はアレックス・スミス、ヴォーン・プラット、その他の間でしばらく続いた。[ 24 ]

出版物

スミスの証明は最終的に2020年にウルフラムの雑誌Complex Systemsに掲載されました。 [ 25 ]

参照

参考文献

  1. ^ Wolfram, Stephen (2002). 『新しい種類の科学』 p. 709. 2009年2月10日閲覧。
  2. ^ 「Wolfram 2,3 チューリングマシン研究賞」 。 2009年2月10日閲覧。
  3. ^ Goodman-Strauss, Chaim, Can't decide? Undecide! , CiteSeerX 10.1.1.164.306 , 2022年2月4日閲覧 
  4. ^ 「2つの文字と2つの状態を持つチューリングマシン」複雑系学会誌、2010年。 2017年10月25日閲覧。
  5. ^ Brumfiel, Geoff (2007). 「学生が数学賞を獲得」 . Nature . doi : 10.1038/news.2007.190 . 2009年2月10日閲覧。
  6. ^ Keim, Brandon (2007年10月24日). 「大学生がWolframのチューリングマシンが最もシンプルな汎用コンピュータであることを証明」 Wired . 2009年2月10日閲覧。
  7. ^ Geoff Brumfiel (2007年10月24日). 「Nature.com」 . Nature . Nature.com. doi : 10.1038/news.2007.190 . 2010年3月9日閲覧。
  8. ^ 「ニューサイエンティスト」ニューサイエンティスト2010年3月9日閲覧。
  9. ^ 「バーミンガム大学」 Newscentre.bham.ac.uk . 2010年3月9日閲覧。
  10. ^ 「Math Societyのニュースで取り上げられた数学」 Ams.org。2010年2月20日時点のオリジナルよりアーカイブ。2010年3月9日閲覧。
  11. ^ Crighton, Ben (2007年11月26日). 「チューリングの単純なコンピュータの証明」 . BBCニュース. 2010年3月9日閲覧。
  12. ^ 「Bitwise Magの記事」。Bitwise Magの記事。2007年10月24日。 2010年3月9日閲覧。
  13. ^ 「アメリカ数学協会」 Maa.org 2010年3月9日閲覧。
  14. ^ Minkel, JR (2007年10月25日). 「新種の科学の著者が、最も単純なコンピュータを発見した優秀な大学生に2万5000ドルを支払う」 . Scientific American . 2010年3月9日閲覧。
  15. ^ "plus magazine" . Plus.maths.org. 2007年11月8日. 2009年12月20日時点のオリジナルよりアーカイブ。 2010年3月9日閲覧。
  16. ^ Stuart, Tom (2007年11月29日). 「非常に単純なコンピュータの複雑な証明」 . The Guardian . ロンドン. 2010年3月9日閲覧。
  17. ^ 「FOMリストにおけるStephen Wolframの返信」ニューヨーク大学、2007年10月。
  18. ^ 「ウルフラム賞とユニバーサルコンピューティング: それは今あなたの問題です」。
  19. ^ 「最もシンプルな『ユニバーサルコンピュータ』が学生に2万5000ドルの賞金をもたらす」ニューサイエンティスト、2007年10月24日。 2016年1月28日閲覧。
  20. ^ 「[FOM] 最小の万能マシン」 Cs.nyu.edu、2007年10月30日。 2022年8月18日閲覧。
  21. ^ 「[FOM] 最小の万能マシン」 Cs.nyu.edu、2007年10月26日。 2022年8月18日閲覧。
  22. ^ 「Vaughan PrattのFOMリストへのメッセージ」 2007年10月29日。
  23. ^ 「Alex Smith による FOM リストでの Vaughan Pratt への最初の返信」 2007 年 10 月 30 日。
  24. ^ 「FOMリストアーカイブ 2007年11月」 Cs.nyu.edu 2010年3月9日閲覧。
  25. ^スミス、アレックス (2020). 「Wolframの2, 3チューリングマシンの普遍性」. Complex Systems . 29 (1): 1– 44. doi : 10.25088/ComplexSystems.29.1.1 . S2CID 17142621 . 

参考文献

歴史読書

  • マービン・ミンスキー(1967) 「計算：有限マシンと無限マシン」プレンティス・ホール。
  • チューリング、A（1937） 「計算可能数とその計算問題への応用」ロンドン数学会誌シリーズ2、42：230-265。
  • — (1938)「計算可能数について、そして計算問題への応用。訂正」ロンドン数学会誌第2シリーズ、43 :544-546。
「 https://en.wikipedia.org/w/index.php?title=Wolfram%27s_2-state_3-symbol_Turing_machine&oldid=1335677593」より取得