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

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

2007年5月14日、ウルフラムは、(2,3)チューリングマシンの普遍性を最初に証明または反証した人に25,000ドルの賞金を与えると発表した。^{[2] 2007年10月24日、}バーミンガム大学の電子工学とコンピューティングを学ぶ学生であるアレックス・スミスが、それが普遍的であることを証明したことで賞を受賞したことが発表された。この証明は、無限の非周期的な初期構成を許容する非標準的なチューリングマシンモデルに適用されるため、一部の人々によって「弱普遍的」と分類されている。^[3]

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

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

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

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

ミンスキー (1967) は、標準的な (2,2) マシンは汎用ではあり得ないと簡単に論じ、M. マーゲンシュテルン (2010) は、1973 年の L. パブロツカヤの結果 (未発表だがマーゲンシュテルンの論文で言及されている) に基づく数学的証明^{[4]を示した。したがって、(2,3) チューリング マシンは、状態数と記号数の積で考えれば、可能な限り最小の}汎用チューリング マシンであるように思われる。しかし、ミンスキーは明示的に停止するマシンのみを考慮しているのに対し、(2,3) マシンはそうではないため、結果を直接比較することはできない。より一般的には、チューリング マシンのほとんどすべての形式的な定義は、そのパワーとは無関係な細部で異なっているが、与えられた数の状態と記号を使用して何を表現できるかということには関係している可能性がある。単一の標準的な形式的な定義はない。(2,3) チューリング マシンは、無限の非反復入力も必要とするため、これもまた、以前の小型の汎用チューリング マシンとの直接の比較に問題が生じる。

したがって、(2,3) マシンはある意味で「可能な限り最小の汎用チューリング マシン」であるというのは事実かもしれませんが、これは古典的な意味で厳密に証明されておらず、従来の汎用性の定義や、証明に使用されたチューリング マシンの特性の緩和が一般に許容されるかどうかを考慮すると、その主張は議論の余地があり、さらに、任意の選択 (停止構成を持つことや空のテープが必要であることなど) からより独立した計算の汎用性を定義する新しい方法を示唆する可能性さえあります。

特定の行のヘッドの状態 (上または下の液滴 (それぞれ 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]}

• チューリング完全性— あらゆるチューリングマシンをシミュレートする能力
• ルール 110 — チューリング完全な基本セルオートマトン

• Wolfram, S (2002) 『新しい種類の科学』 Wolfram Media。
• Wolfram Research, Inc.、「チューリングマシン計算の限界を決定した功績により賞が発表」。Wayback Machineに 2012 年 2 月 7 日にアーカイブ。アレックス・スミスが賞を受賞したことの正式発表。
• —、Wolfram 2,3 チューリングマシン研究賞。出場者への招待。

• マービン・ミンスキー(1967) 「計算：有限マシンと無限マシン」プレンティス・ホール。
• チューリング、A (1937)「計算可能数とその計算問題への応用」、ロンドン数学会シリーズ2の議事録、42：230-265。
• — (1938)「計算可能数について、その計算問題への応用。訂正」ロンドン数学会誌第2シリーズ、43 :544-546。

• 「学生が数学の賞を獲得」Nature 誌、2007 年 10 月 24 日オンライン版掲載。
• 「大学生が、ウルフラムのチューリングマシンが最もシンプルな汎用コンピュータであることを証明」Wired Science。2007 年 10 月 24 日オンライン公開。
• 「最もシンプルな『ユニバーサル コンピューター』が学生に 25,000 ドルの賞金をもたらす」、New Scientist。2007 年 10 月 24 日オンライン公開。
• 「ウルフラム賞とユニバーサルコンピューティング: それは今あなたの問題です」、Dr. Dobb's Journal。2007年 10 月 22 日にオンラインで公開。
• Minkel, JR、「新しいタイプの科学著者が、最も単純なコンピュータを特定した優秀な大学生に 25,000 ドルを支払う」、Scientific American、2007 年 10 月 25 日。
• 数学の基礎に関するディスカッションスレッドより:
  • 単純なチューリングマシン、普遍性、エンコーディングなど。
  • 最も単純な汎用チューリングマシン
  • 最小のユニバーサルマシン
  • ヴォーン・プラットはスミスの証明は無効であると主張した
  • 同じフォーラムでのPrattへのWolframの返信
  • 賞の審査員の一人、トッド・ローランド氏によるプラット氏への返答