Wolframが「マルチウェイ・チューリングマシン」で見つけた驚きの計算世界

Multiway Turing Machines (2021 pre-ai)

Stephen Wolfram氏が、従来のチューリングマシンと異なり、各状態から複数の遷移が可能な「マルチウェイ・チューリングマシン」（非決定的チューリングマシン）を体系的に探求。このモデルは並行計算や量子力学の「マルチウェイシステム」の最も単純な例とみなせる。Wolfram氏は、最も単純なルール（s=2, k=2）を持つマシンでも、分岐・合流・ループ、さらには停止と無限成長が混在する複雑なマルチウェイグラフが生じることを発見。また、これらのマシンが「ルリアル空間」の探求や、物理学プロジェクトにおける量子力学の理解につながると論じる。