HN 日本語サマリー

← 一覧へ戻る
科学・技術

マルチウェイ・チューリング・マシン(2021年 AI以前)

Multiway Turing Machines (2021 pre-ai) (bulletins.wolframphysics.org)

17 pointsby marysminefnuf3 コメント

要約

この記事は、2021年に発表された「マルチウェイ・チューリング・マシン」という概念について論じています。これは、計算の進化を多岐にわたる可能性のネットワークとして捉える、Wolfram Physics Projectにおける計算の抽象化に関する研究の一部です。

全文翻訳

マルチウェイチューリングマシン

長年、私は単純な通常のチューリングマシンをかなり研究してきましたが、マルチウェイチューリングマシン(非決定性チューリングマシンまたはNDTMとも呼ばれる)についてはほとんど調べてきませんでした。しかし最近、マルチウェイチューリングマシンは、並行計算と、物理学プロジェクトで量子力学を考える方法の両方に対する「最大限にミニマルな」モデルと見なせることに気づきました。そこで、この文章はマルチウェイチューリングマシンに関する「当然の探求」を試みるものです。そして、計算宇宙の至る所でしばしば発見してきたように、最も単純な可能なルールのいくつかを適用した場合でも、かなりの驚きが得られます….

通常のチューリングマシンとマルチウェイチューリングマシンの比較

通常のチューリングマシンは、以下のようなルールを持っています。

[画像: RulePlot]

&#10005

システムの各構成に対して一意の後続を指定します(ここでは、空白テープからなる初期条件から、ページの下に向かって表示されています)。

[画像: RulePlot]

&#10005

マルチウェイチューリングマシンでは、ルールのある特定のケースに対して複数の可能な結果を指定できます。

[画像: CloudGet]

&#10005

その結果、システムには多くの可能な進化経路が存在する可能性があり、これは successive possible configurations を接続するマルチウェイグラフとして表されます。

[画像: With]

&#10005

通常のチューリングマシンのルールの進化は、マルチウェイグラフ内の特定の経路に対応します。

[画像: With]

&#10005

さらに数ステップ進めると、マルチウェイグラフにおける分岐と合流のかなり複雑なパターンが見え始めます。

[画像: With]

&#10005

私の目的は、単純なルールを持つマルチウェイチューリングマシンが何ができるかを探索することです。

私のマルチウェイチューリングマシンの基本的な設定は、通常「非決定性チューリングマシン」(NDTM)と呼ばれるものと同じですが、NDTMでは通常、単一の経路が特定のプロパティを持つかどうかに関心がありますが、ここではすべての可能な経路の完全なマルチウェイ構造に関心があります。(そして、「非決定性」ではなく「マルチウェイ」を使用することで、確率的またはランダムな経路を考えているという混乱を避け、すべての可能な経路の構造を研究していることを強調します。)

私たちの物理学プロジェクトでは、マルチウェイシステムは量子力学につながるものであり、ここのマルチウェイチューリングマシンは量子チューリングマシンに直接対応しており、量子振幅の大きさは経路の重み付けによって決定され、その位相はマルチウェイグラフの横断スライスから現れる分岐空間内の位置によって決定されます。

単純なルールを持つチューリングマシン

s = 2 のヘッド状態と k = 2 の色を持つ通常のチューリングマシンは 4096 種類存在します。これらのマシンはすべて最終的に単純な方法で動作し、最も複雑な振る舞いの例は(最後のケースは対数的な成長を持つバイナリカウンタです)以下の通りです。

[画像: With]

&#10005

s = 3 になると、事態はわずかに複雑になるだけですが、s = 2, k = 3 では、最も単純な複雑な振る舞いをするチューリングマシンが見つかります(そしてこの振る舞いは、空白の初期テープでも発生します)。

[画像: GraphicsRow]

&#10005

[画像: RulePlot]

&#10005

計算等価性の原理が示唆するように、このチューリングマシンは計算普遍的であることが判明します(これは可能な限り最も単純な普遍チューリングマシンとなります)。

したがって、通常のチューリングマシンにおける普遍性の閾値は s = 2, k = 3、つまりルールに6つのケースが指定されている状態であるということです。しかし、次に問えることは、マルチウェイチューリングマシンにおける普遍性の閾値は何かということです。

s = 2, k = 3 の通常のチューリングマシンが普遍的であるということは、適切な初期条件を与えれば、このチューリングマシンの進化が他の任意のチューリングマシン(少なくとも適切なエンコーディングで、有界計算によって実装可能)の進化をエミュレートできるということです。

マルチウェイチューリングマシンに対する計算普遍性の最も近い類推的な定義は、適切な初期条件を与えれば、チューリングマシンのマルチウェイ進化が他の任意のチューリングマシンのマルチウェイ進化を(適切なエンコーディングまで)エミュレートできるということであると言えます。(ただし、後で議論するように、「非決定性解釈」は、対応する個々の経路に特定の識別可能な特徴を持たせるように初期条件を設定できるかどうかに基づく、名目上異なる定義を示唆しています。)

通常のチューリングマシンのルールを指定するには、通常、以下のような s k 個の可能な「入力」に対する結果を定義するだけです。

[画像: Flatten]

&#10005

または:

[画像: Flatten]

&#10005

しかし、これらの入力の一部を省略した場合はどうなるでしょうか?文字列またはハイパーグラフ書き換えシステムの通常の扱いのアナロジーとして、省略された入力のいずれかがシステムの進化で到達した場合、書き換えは実行されない、または標準的なチューリングマシンの用語ではシステムが「停止する」と単純に言うことができます。

s = 2, k = 2 では、(空白テープから開始して)最終的に停止するマシンが存続できる最長時間はわずか6ステップです。そして、それらは(反射を除いて)8種類あり、そのうち3種類はルール中の4つのケースのうち2つだけを使用し、5種類は3つのケースを使用します。

[画像: CloudGet]

&#10005

ある意味で、これらの各ルールは、k = 2, s = 2 の場合のすべての 2 s2 k2 の可能なルールケースのサブセットを使用していると考えることができます。

[画像: CloudGet]

&#10005

一般に、任意のマルチウェイチューリングマシンルールは、そのようなサブセットのいずれかに対応します。すべての可能な入力が正確に1回出現する場合、停止しない通常のチューリングマシンが得られます。入力が最大で1回出現するが、一部が出現しない場合、チューリングマシンは停止する可能性があります(ただし、その入力に到達しない場合は停止しません)。

しかし、いずれかの入力が複数回出現する場合、チューリングマシンは非自明なマルチウェイ進化を示す可能性があります。すべての入力が少なくとも1回出現する場合、マルチウェイ進化のどの分岐も停止することはできません。しかし、一部の入力が複数回出現し、一部が出現しない場合、マルチウェイ進化のいくつかの分岐は停止するかもしれませんが、他の分岐は永遠に続く可能性があります。

一般に、22s2k2 の可能なマルチウェイチューリングマシンルールが存在します。ルール空間とルールマルチウェイシステムについて議論する際、以前に議論したのは、すべてのケースが含まれる(つまり、s = 2, k = 2 の場合の全32ケース)ルールの例(ある意味で「可能な限りマルチウェイな」チューリングマシン)でした。しかしここでは、代わりにルールが可能な限り単純である、つまり「ルール空間の限界から遠い」マルチウェイチューリングマシンに関心があります。

最も単純な非自明なマルチウェイチューリングマシンは、ルールにわずか2つのケースしか持ちません。一般に、二項 [2 s2 k2, 2] 個のそのようなルールが存在し、s = 2, k = 2 の場合は 496 個、そのうち 112 個が実際のマルチウェイ挙動を示します。

非常に単純な例は、以下のルールです。

[画像: CloudGet]

&#10005

これは、すべてのバイナリ数を含むテープ構成を生成します。

[画像: With]

&#10005

そして、無限のバイナリツリーを形成するマルチウェイシステムを生成します。

[画像: With]

&#10005

少しトリビアルでない例は、以下のルールです。

[画像: CloudGet]

&#10005

これは、ヘッドが非空白セル上にあるとすぐに分岐が停止するマルチウェイグラフを生成します。

[画像: With]

&#10005

これを続けると、マルチウェイグラフの全体的な構造は(停止状態は赤い点で示されています)以下のようになります。

[画像: CloudGet]

&#10005

別の例として、以下のルールを考えます。

[画像: CloudGet]

&#10005

[画像: MultiwayTuringMachine]

&#10005

ここでも、ヘッドが非空白セル上にあるとシステムは停止しますが、これは少し複雑な方法で行われ、少し複雑なマルチウェイグラフが生成されます。

[画像: TMAppliesGraph]

&#10005

これまで見た例では、チューリングマシンがどのルールも適用されない状態に到達できるという意味での明示的な停止があります。もう一つ起こりうることは、チューリングマシンが無限ループに入り込むことです。そして、マルチウェイグラフでは同一の状態がマージされるため、このようなループは実際のループとしてマルチウェイグラフに現れます。この例のように。

[画像: TuringMachinePlot]

&#10005

[画像: MultiwayTuringMachine]

&#10005

ルールに3つのケースを許可すると、事態は急速に複雑になります。例えば、以下のルールを考えます(これは決して停止しません)。

[画像: TuringMachinePlot]

&#10005

そのマルチウェイグラフの最初の数ステップは以下の通りです。

[画像: MultiwayTuringMachine]

&#10005

この例は、やや微妙な問題点を露呈しています。以前の例では、特定のステップで生成されたすべての状態は、マルチウェイグラフの単一の層に一貫して配置できましたが、ここでは状態 [画像] がステップ2とステップ4の両方で生成されます。そのため、(同一の状態のコピーを結合すると仮定した場合)このような「グローバルな層化」は不可能です。

そして、このグローバルな層化の欠如の結果として、指定されたステップ数だけ計算した場合、「ぶら下がった状態」— [画像] のような — が、表示された「最終層」よりもかなり上に現れる可能性があります。

さらに1ステップ進めると、以前の「ぶら下がった状態」は後続を持ちますが、新しいぶら下がった状態が現れます。

[画像: MultiwayTuringMachine]

&#10005

さらにステップを進めると、やや複雑ですが、それでもかなり規則的なマルチウェイが現れ始めます。

[画像: MultiwayTuringMachine]

&#10005

以下は、3つのケースを持つマルチウェイチューリングマシンの別の例です。

[画像: TuringMachinePlot]

&#10005

そのマルチウェイグラフの最初の数ステップは以下の通りです。

[画像: MultiwayTuringMachine]

&#10005

さらに1ステップ進めると、事態はより複雑になり、特にループが見られます。

[画像: MultiwayTuringMachine]

&#10005

さらに数ステップ進めると、以下のようになります。

[画像: TMAppliesGraph]

&#10005

(このルールでは停止がないため、ここで見えるぶら下がった端は、進化が継続された場合にさらなる成長を示す必要があります。)

急速な成長と停止の両方を得ることは完全に可能です。以下に例を示します。

[画像: TuringMachinePlot]

&#10005

[画像: TMAppliesStatesGraph]

&#10005

または、より長く続けると:

[画像: TMAppliesGraph]

&#10005

可視化とマルチスペース

通常のチューリングマシンの振る舞いは、その構成をページの下に successive に表示するだけで、かなり容易に把握できます。しかし、マルチウェイチューリングマシンの場合はどうでしょうか?マルチウェイグラフは、システムの完全な構成(状態)間の進化によって定義される関係を示します。

[画像: MultiwayTuringMachine]

&#10005

しかし、このような図では、異なる構成の詳細な形式間の関係や、例えばヘッドの「空間的な動き」が明確になりません。では、これをどうすればよいでしょうか?

一つの可能性は、あるステップでのすべての異なる可能な構成を「重ねて」表示することです。上記の機械では、 successive ステップで得られる新しい構成は以下の通りです(ただし、上記のマルチウェイグラフのレンダリングで特定の層に現れるわけではないことに注意してください)。

[画像: TuringMachine]

&#10005

これらを「重ね合わせ」、色を「平均化」すると、以下のようになります。

[画像: TuringMachinePlot]

&#10005

この場合、そのような可視化は振る舞いの「拡散性」を明らかにします。異なる進化におけるヘッドの動きは、ランダムウォークのアンサンブルにおけるすべての可能な経路に実質的に対応するため、オフセット x でヘッドを見つける確率は 二項 [ t, x ] / 2t となります。

ヘッド位置を successive ステップの進化で結合すると、経路の格子をより明確に見ることができます。

[画像: HeadTraceGraphics2X]

&#10005

このアプローチは、これまで議論してきた他のマルチウェイチューリングマシンについて何を明らかにしているでしょうか?最初の例の一つを示します。

[画像: TMSummary2]

&#10005

そして、別の例を示します。

[画像: TMSummary]

&#10005

しかし一般に、この種のスムージングされた画像はあまり役に立ちません。では、代替案はあるでしょうか?基本的に、マルチウェイ構造と個々の構成の詳細な形式の両方を同時に可視化する方法が必要です。

私たちの物理学プロジェクトのアナロジーとして、これは基本的に分岐構造と空間構造の両方を同時に可視化する問題です。では、どこから始めればよいでしょうか?私たちの日常経験は通常の空間に関するものであり、分岐空間に関するものではないため、通常の空間から始めて、分岐成分を追加するのがより良いかもしれません。そして、このことについて考えることがマルチスペースの概念につながりました。これは、各点でマルチウェイの可能性のスタックがあり、これらの異なる可能性が分岐空間の異なる場所で接続されている、空間の一般化です。

私たちの物理学プロジェクトでは、通常の空間自体を可視化することさえ困難です。なぜなら、それはハイパーグラフに対応する低レベルの構造から構築されているからです。しかし、チューリングマシンにとっては、空間の基本的な構造は非常に単純に制約されています。1次元のテープがあり、ヘッドはそれに沿って前後に移動できます。

しかし、マルチスペースを理解するには、分岐側から始める方がおそらく簡単です。ここでは、チューリングマシンのテープに書き込まれた値を無視し、ヘッドの位置のみを考慮します。これは、開始位置からの相対位置です。マルチウェイグラフ内の各状態は、そのチューリングマシンの構成におけるヘッドの位置でラベル付けできます。したがって、上記の最初のルールでは、以下のようになります。

[画像: TMAppliesGraph]

&#10005

そして今、これを3Dで設定することを想像してみましょう。時間的な方向はページの下方向、分岐的な方向はページを横切る方向、空間的な方向はページの内側方向とします。

[画像: TMAppliesMultispaceRailed]

&#10005

しかし、これを回転させると、分岐構造と空間構造の相互作用を見ることができます。

[画像: Click to copy input and view animation]

&#10005

この特定のケースでは、マルチウェイシステム(つまり、分岐方向)で見られる主な分岐が、ヘッド位置の空間方向へのますます分離された位置に対応していることがわかります。

常にこのように単純であるとは限りません。このセクションの冒頭のチューリングマシンに対するヘッド位置注釈付きマルチウェイグラフを示します。

[画像: MultiwayTuringMachine]

&#10005

そして、マルチスペースでのこのチューリングマシンの進化の3Dビューを示します。まず、分岐時間平面に投影していることになります。ただし、接続は3Dで行われる可能性があるため、レンダリングで選択されたレイアウトは、マルチウェイグラフを2Dでレンダリングする際に選択されるものとは異なります。

[画像: Click to copy input and view animation]

&#10005

マルチスペースで回転させると、分岐構造と空間構造の間の相互作用を見ることができます。

[画像: Click to copy input and view animation]

&#10005

この比較的単純なマルチウェイチューリングマシンでさえ、何が起こっているのかを理解するのはすでにかなり困難です。しかし、さらに数ステップ進めると、マルチスペースで明確なパターンが見られます(下部の狭まりは、有限ステップで実行されたことを反映しています。より長く実行すれば埋まるでしょう)。

[画像: Click to copy input and view animation]

&#10005

私たちの物理学プロジェクトでは、物理空間または分岐空間のいずれにも固有の座標系はありません。したがって、どのような座標系も純粋に創発的でなければなりません。しかし、チューリングマシンの基本的な構造は、空間と時間座標の即時の定義を必要とします。これは、上記の画像でノードを空間的および時間的方向に配置するために使用したものです。(時間的方向は少し微妙です。マルチウェイグラフの層化で状態が現れる場所に基づいて座標を割り当てています。これは、それが最初に現れる「時間ステップ」であるとは限りません。)しかし、チューリングマシンには分岐座標の即時の定義はありません。そして、上記の画像では、分岐座標を(やや恣意的な)マルチウェイグラフの2Dレンダリングで使用されるレイアウトから導出しています。

では、より良い代替案はあるでしょうか?実質的には、チューリングマシンの完全な状態、テープの構成を含むものを適切に座標化する方法を見つける必要があります。一つの可能性は、テープの構成を基数 k の数として扱うことです。そして例えば、その数の対数から座標を計算することです。(ヘッドの位置を通じて、ヘッドの位置が「処理」されているかのように数をシフトすることも想像できます。しかし、ヘッド位置は、ある意味で既に空間座標を通じて「処理」されています。)以下は、上記のチューリングマシンに対してこれを行った結果です。

[画像: Click to copy input and view animation]

&#10005

他の例をいくつか示します。

[画像: Click to copy input and view animation]

&#10005

テープ構成について考えると、別の可視化が思い浮かびます。 successive ステップで生成できるすべてのテープ構成を積み重ねるだけです。ルールの場合

[画像: TuringMachinePlot]

&#10005

ステップ t で、 successive 整数の0から2t–1までのバイナリ数字がテープ上に得られます。

[画像: TuringMachinePlot]

&#10005

しかし、以下のルールのような場合でも、結果はより複雑になります。

[画像: TuringMachinePlot]

&#10005

そして今、灰色の行はチューリングマシンが既に停止した状態に対応します。

[画像: TMAppliesQ]

&#10005

マルチウェイグラフを構築し、マルチスペースまたは他の場所でレンダリングする場合、マルチウェイチューリングマシンなどの状態の進化を直接表現しています。しかし、特に私たちの物理学プロジェクトにおける量子力学の研究は、補完的な視点の重要性を強調しています。個々の状態の進化ではなく、マルチウェイグラフにおける共通の祖先によって定義される状態間の関係(または「エンタングルメント」)を見ることです。

以下のルールを考えます。

[画像: TuringMachinePlot]

&#10005

これはマルチウェイグラフを生成します。

[画像: MultiwayTuringMachine]

&#10005

このグラフを葉状化します。

[画像: MultiwayTuringMachine]

&#10005

この最後のスライスを見ると、共通の祖先を持つノードのペアがいくつかあります。それぞれが元のルールの異なるケースの使用から来ています。しかし、共通の祖先を持つ構成(ノード)を接続する分岐グラフは、非常に単純です。

[画像: MultiwayTuringMachine]

&#10005

しかし、以下のルールでさえ

[画像: TuringMachinePlot]

&#10005

マルチウェイグラフは

[画像: MultiwayTuringMachine]

&#10005

successive ステップでの分岐グラフは、わずかに単純ではありません。

[画像: MultiwayTuringMachine]

&#10005

「厚みのある分岐グラフ」を構築することもできます。ここでは、直接の共通祖先だけでなく、例えば τ ステップ前の共通祖先まで見ます。τ > 1 の場合、結果はハイパーグラフになり、この最初のケースでさえ、かなり非自明なものになる可能性があります。

[画像: WolframModelPlot]

&#10005

単純なマルチウェイチューリングマシンの世界

通常のチューリングマシンが s = 2 の状態と k = 2 の色を両方とも持たない限り、常に実質的に自明な振る舞いをします。しかし、マルチウェイチューリングマシンはどうでしょうか? k = 1 の色の場合、システムはテープに何も保存できず、ヘッドがいる位置で常に「同じダンス」をしなければなりません。

例えば、s = 2 のルールを考えます。

[画像: TuringMachinePlot]

&#10005

このシステムのステートは {σ, i} の形で表すことができ、σ はヘッドの状態、i はヘッドの位置です。空白テープから開始して3ステップ後の進化のマルチウェイグラフは、以下のようになります(各状態の座標は {σ, i} から決定されます)。

[画像: MultiwayTuringMachine]

&#10005

さらに長く続けると、以下のようになります。

[画像: MultiwayTuringMachine]

&#10005

そして、マルチウェイグラフは実質的に繰り返し可能なブレードであることがわかります。ただし、任意のステップでは「わずかにほつれた」端があります。ブレードは「モチーフ」のシーケンスから構築できます。ここでは3つの「ベクトル」で構成され、各ベクトルは基になるルールのケースによって直接決定されます。この場合:

[画像: ruleToMotif]

&#10005

3つのケースを持つすべての s = 2 マルチウェイチューリングマシンを見ると、これらのマルチウェイグラフ構造が得られます。

[画像: MultiwayTuringMachine]

&#10005

すべてのケースで、任意の経路の実質的な繰り返し長は1、2、または4です。

s = 3 のヘッド状態が可能になると、わずかに複雑なマルチウェイグラフが可能になります。例えば、

[画像: TuringMachinePlot]

&#10005

は「8サイクルブレード」を生成します。

[画像: TuringMachinePlot]

&#10005

「純粋なブレード」マルチウェイグラフを超えるには、k ≥ 2 の色を考慮する必要があります。しかし、ヘッド状態 s = 1 のみを(つまり、ルール範囲0の「モバイルオートマトン」)使用した場合はどうなるでしょうか?

s = 1, k = 2 の場合、ルールで発生する可能性のある8つのケースがあります。

[画像: TuringMachinePlot]

&#10005

したがって、256種類の可能なマルチウェイチューリングマシンがあり、そのうち231種類は「純粋に決定論的」ではありません。

p = 2 のケースのみを許可する場合、28種類のマシンがあり、そのうち12種類は純粋に決定論的ではなく、区別可能な非自明なマルチウェイグラフの形式は(最初のルールでは2番目の色が使用されていない)以下の通りです。

[画像: CloudGet]

&#10005

p = 3 のケースを許可する場合、56種類のマシンがあり、純粋に決定論的なものはありません。それらが生成する区別可能なマルチウェイグラフは以下の通りです。

[画像: TMAppliesGraphUntil]

&#10005

これらのうちいくつかは既に上で見ました。しかし、これらのグラフがどれほど複雑に見えるかは注目に値します。

しかし、マルチスペースにグラフを配置すると、いくつかは非常に明確な規則性を示します。

[画像: TMAppliesMultispaceIndicatorUntil]

&#10005

複雑なケースをさらにステップ数で見た場合でも、かなりの複雑さが見られます。

[画像: CloudGet]

&#10005

最初のルールの successive ステップで到達した状態の数は以下の通りです。

[画像: MultiwayTuringMachine]

&#10005

他の2つの場合は以下の通りです。

[画像: MultiwayTuringMachine]

&#10005

どちらも指数関数的に成長するように見えますが、基数はわずかに異なり、どちらも1.46に近い値です。

状態のコレクションを見ても、振る舞いに対する直接的な洞察は得られません。

[画像: TuringMachine]

&#10005

では、p > 3 のケースを許可した場合はどうなるでしょうか?p = 4 のケースでは、70種類のマシンがあり、純粋に決定論的なものはありません。以下は、見られるより複雑な振る舞いの例です。

[画像: CloudGet]

&#10005

p = 5 の例も見てみましょう。

[画像: CloudGet]

&#10005

s = 2, k = 2 を使用した場合に何が起こるかについても尋ねることができます。ルールに p = 3 のケースを許可した場合、最も複雑なマルチウェイグラフは以下の通りです。

[画像: TMAppliesGraphUntil]

&#10005

p = 4 のケースでは、振る舞いはわずかに複雑になる可能性がありますが、単一ヘッド状態 s = 1 で見たもの以上にはならないようです。

[画像: CloudGet]

&#10005

最も単純な普遍マルチウェイチューリングマシンとは?

マルチウェイチューリングマシンで複雑な振る舞いを得るには複雑なルールが必要であり、ルールが複雑になるにつれて振る舞いも同様に複雑になると想定していたかもしれません。しかし、前のセクションで見たのはそうではありませんでした。むしろ、非常に単純なルールを持つマルチウェイチューリングマシンでさえ、既に複雑な振る舞いを示すことができ、ルールが複雑になるにつれて振る舞いが根本的に複雑になるようには見えませんでした。

これは驚くべきことかもしれません。しかし、実際には計算宇宙の至る所で見られることと非常に似ており、まさに私の計算等価性の原理が示唆する通りです。なぜなら、この原理が言うのは、明らかに単純な振る舞いをするシステムを超えると、それらが実行する計算の洗練度において同等なシステムに到達するということです。言い換えれば、非常に低い閾値を超えると、常に同じ最大レベルの計算的洗練度に到達するシステムが見られるということです。

計算等価性の原理は、システムが行う「典型的な計算」について語り、例えば、これらの計算は、システム自体が実行する計算と実質的に同じ長さの計算を除いて、その結果を決定することはできないという意味で計算不可約になる傾向があることを示唆しています。しかし、計算等価性の原理のもう一つの結果は、システムの振る舞いが明らかに単純でなくなった場合、それは計算普遍的である可能性が高いということです。言い換えれば、システムが複雑な振る舞いを示すことができるようになると、それを他のシステム(少なくとも有界計算による変換まで)をエミュレートさせる特定の初期条件を見つけることが、実質的に常に可能になります。

そして、単純なセルオートマトンや、通常の決定性チューリングマシンでこれがどのように機能するかについての良い証拠があります。s = 2, k = 2 のチューリングマシンは常に単純で非常に規則的な振る舞いを示し、そのようなマシンは計算普遍性を実行できません。しかし、s = 2, k = 3 では、より複雑な振る舞いを示すマシンがいくつかあります。そして、これらのマシンが実際に計算普遍的であることを知っており、通常のチューリングマシンの中で普遍性の閾値が可能な限り低いことを確立しています。

では、マルチウェイチューリングマシンについてはどうでしょうか?そのようなマシンの普遍性の閾値はどこにあるのでしょうか?通常のチューリングマシン(および他の多くの種類のシステム)での経験に基づくと、前のセクションの結果は、s = 1, k = 2, p = 3 で既に十分である可能性が高いことを示唆するかもしれません。通常のチューリングマシンでは、s = 2, k = 3(ルールに6つのケースに対応)で普遍性が達成されます。ここでは、ルールにわずか3つのケースで普遍性が可能になるようです。そして、s = 1, k = 2 で。

おそらく最も驚くべき点は、普遍性がわずか1つのヘッド状態 s = 1 でさえ可能かもしれないという示唆です。これは、ヘッド状態が全くないチューリングマシンさえ必要としないことを意味します。単にモバイルオートマトンを使用でき、実際には「半径0」のもの(つまり、隣接する要素に直接影響されないルール)を使用できます。これは、例えば以下のように示すことができます。

[画像: TuringMachinePlot]

&#10005

チューリングマシンは、しばしば有限オートマトンの拡張として見なされ、無限のメモリを提供するテープが追加されます。通常の決定性チューリングマシンは決定性有限オートマトン(DFA)の拡張であり、マルチウェイチューリングマシンは非決定性有限オートマトン(NDFA)の拡張です。そして、単一の状態 s = 1 を持つ有限オートマトンは、決定性か非決定性かに関わらず、常に自明です。また、s = 1 の通常の決定性チューリングマシンは、テープの色 k がいくつであっても常に自明であることも知っています。s = 2 が非自明な振る舞いを達成するための最小値であり(そして実際、s = 2, k = 3 がある意味で最大限に複雑な振る舞いを達成するのに十分であることを知っています)。

しかし、上で見たように、マルチウェイチューリングマシンは s = 1 でさえ非自明な振る舞いを示すことができます。s = 1 マルチウェイチューリングマシンが s > 1 のマシンをエミュレートできることを示す直接的な構成がある可能性は高いです。しかし、これがなぜ可能であるかについての直感的な説明を以下に示します。通常のチューリングマシンでは、ヘッドはテープ上を「空間的に」移動し、ヘッドの状態は状態情報と共に移動します。しかし、マルチウェイチューリングマシンでは、実際には空間だけでなく、分岐空間への移動もあります。そして、複数のヘッド状態なしでは、ヘッドが通常の空間で情報を運ぶことができないとしても、分岐空間内の近くの構成の集合は、分岐空間で情報を運ぶことができます。言い換えれば、分岐空間では、複数の可能なヘッド状態を想定できる「スーパーヘッド」のようなものを表す近くの構成の「クラウド」が存在すると考えることができます。

この考え方にとって重要なのは、マルチウェイシステムが同一の状態をマージするように設定されているという事実です。このマージがなければ、マルチウェイチューリングマシンのマルチウェイグラフは単なるツリーになります。しかし、マージは分岐空間を「編み合わせ」、その中の距離や動きの概念を理解できるようにします。

通常のチューリングマシンでは、進化をシステムのステートを徐々に変換するものと考えることができます。マルチウェイチューリングマシンでは、進化をマルチウェイグラフの基本的な部分を編み合わせるものと考える方が良いかもしれません。その結果、個々のチューリングマシンの状態がどのようなものであるかよりも、異なる状態が分岐空間、またはマルチウェイシステムでどのように関連しているかが重要になります。

しかし、普遍性とは具体的に何を意味するのでしょうか?通常の決定性システムでは、基本的な定義は、普遍的なシステムが(適切な初期条件を与えれば)他の任意の計算システム(例えば任意のチューリングマシン)をエミュレートできなければならないということです。必然的に、エンコーディングとデコーディングが必要になります。エミュレートしようとしているシステムの仕様(例えば、チューリングマシンのルール)が与えられると、適切な初期条件を設定する手順、または実質的にはルールを適切な「コード」に「コンパイル」する方法が必要です。次に、普遍的なマシンを実行するとき、その進化を「デコード」して、エミュレートしているシステムの進化のステップを特定する方法が必要です。

普遍性の概念が意味を持つためには、エンコーディングとデコーディングのプロセスがあまり多くの計算を必要としないことが重要です。特に、それらが必要とする計算量は有界でなければなりません。つまり、「メインの計算」が計算不可約であり、徐々に長く実行する必要がある場合でも、これらはそうではありません。別の言い方をすれば、エンコーディングとデコーディングのどの特徴も決定可能であるべきであり、メインの計算は計算不可約性や決定不能性を示すことができます。

ここでは、普遍性が1つのマシンが別のマシンをエミュレートする物語について話してきました。そして最終的には、それがすべてです。しかし、伝統的な計算理論(実際のデジタルコンピュータが一般的になる前に開発された)では、通常、セットアップにさらに2つの特徴があります。第一に、チューリングマシンを単に「関数を計算する」ものと見なし、特定の入力が与えられると特定の出力が得られると考えることがよくあります。そして、「内部で何をしているか」は問いません。第二に、チューリングマシンが出力を生成したときに「停止する」と考えることです。しかし、特に計算プロセスについての直感を得たい場合、「プロセスを見る」ことができることが重要です。そして、現代のデジタルコンピュータの操作に合わせて、「停止」することよりも、振る舞いをデコードする方法(例えば、結果が「考慮されるべき」ことを示す「信号」を探すこと)を知ることの方が重要です。

(さらに、チューリングマシンは純粋に「決定マシン」として考えられることもあります。特定の入力が与えられると、最終的に「真」または「偽」の結果が得られ、異なる形式の結果が生成されるわけではありません。)

マルチウェイチューリングマシンを研究する上で、普遍性を定義する最良の方法は、通常のチューリングマシンに使用したものに最も直接的に類似した方法であると思います。普遍的なマシンは、他の任意のシステム(例えば、他の任意のマルチウェイチューリングマシン)のマルチウェイグラフを「デコード」できるように、初期条件を設定する方法がなければなりません。

ここで「初期条件」は、単一のチューリングマシン構成ではない可能性があることに注意してください。それらは構成のアンサンブルを含めることができます。通常の決定性チューリングマシンでは、テープ上のセルの色を異なる位置に指定するという意味で、「空間的に広がる」初期条件を与えます。マルチウェイチューリングマシンでは、「分岐空間に広がる」初期条件、つまりマルチウェイシステムで異なる分岐(マージされる可能性のある)を開始する異なる構成を含むものも与えることができます。通常のチューリングマシンでは、物理学の用語で言えば、「空間的超曲面」に初期データを指定するようなものです。マルチウェイチューリングマシンでは、「分岐的超曲面」に初期データを指定します。

ちなみに、言うまでもなく、普遍的な決定性チューリングマシンは常にマルチウェイチューリングマシンをエミュレートできます(だからこそ、実用的なコンピュータでマルチウェイチューリングマシンを実行できるのです)。しかし、少なくとも最も明白なアプローチでは、マルチウェイチューリングマシンのマルチウェイグラフのすべての分岐を追跡するために、通常のチューリングマシンの指数関数的なステップが必要になる可能性があります。

しかし、「関数を計算する」通常のチューリングマシンのマルチウェイアナログは何でしょうか?最も直接的な可能性は、マルチウェイチューリングマシンがある構成のセットから別のセットへのマッピングを定義することです。(これには、マルチウェイグラフの葉状化に関連するいくつかの微妙な点があり、どの構成のセットを「結果」と見なすべきかを指定する必要があります。)しかし、その後、適切なエンコーディングとデコーディングにより、普遍的なマルチウェイチューリングマシンは、任意のマルチウェイチューリングマシンが計算できる任意の関数を計算できると要求するだけです。

しかし、別の可能性もあります。「非決定性チューリングマシン」という言葉が示唆するように、マルチウェイシステムのいずれかの分岐に望む出力があることを要求することです。例えば、決定問題の答えを決定しようとしている場合、単に「はい」の分岐があるかどうかを確認し、もしあれば、答えは「はい」と結論付けます。

単純なアナロジーとして、変換 {「()」→「」、「()」→「|」} を持つ文字列置換を考えます。括弧のシーケンスがバランスが取れているかどうかは、その進化が最終的に空文字列(「」)状態を生成するかどうかを見て計算できます。しかし、この状態が生成されたとしても、あらゆる種類の「無関係な」状態も生成されます。

[画像: ResourceFunction[