折り紙コンピューターの作り方 |クアンタマガジン

1936 年、イギリスの数学者アラン チューリングは万能コンピューターのアイデアを思いつきました。それは単純な装置でした。XNUMX と XNUMX で覆われた無限のテープのストリップと、テープに沿って前後に移動し、一定のルールに従って XNUMX を XNUMX に、またはその逆に変更できる機械です。彼は、そのようなデバイスを使用してあらゆる計算を実行できることを示しました。

チューリングは自分のアイデアが問題解決に実用的であることを意図していませんでした。むしろ、計算の性質とその限界を探求する貴重な方法を提供してくれました。この独創的なアイデアから数十年にわたり、数学者はさらに実用的ではないコンピューティング スキームのリストを集めてきました。マインスイーパやマジック：ザ・ギャザリングのようなゲームは、原則として汎用コンピュータとして使用できます。ジョン・コンウェイのようないわゆるセルオートマトンも同様かもしれない 人生のゲーム、二次元グリッド上の黒と白の正方形を進化させるための一連のルール。

9月2023で、 インナ・ザハレヴィッチ コーネル大学の博士と トーマス・ハル フランクリン＆マーシャル大学の教授は、あらゆるものは計算できることを示しました。 紙を折ることで計算できる。彼らは、折り紙が「チューリング完全」であることを証明しました。つまり、十分な時間があれば、チューリング マシンのように、扱いやすい計算問題をすべて解決できることを意味します。

生涯の折り紙愛好家であるザカレビッチ氏は、人生ゲームのチューリング完全性を説明するビデオに出会った後、2021 年にこの問題について考え始めました。 「折り紙は人生ゲームよりもはるかに複雑だと思いました」とザカレビッチ氏は語った。 「人生ゲームがチューリング完全であるなら、折り紙もチューリング完全であるはずです。」

しかし、これは彼女の専門分野ではありませんでした。彼女は幼い頃から折り紙を折っていましたが、「24 インチの紙を必要とし、400 ステップもある超複雑なものを私に教えて欲しいのであれば、私はそれをすべて喜んでいます」と彼女は言いました。数学的研究は、代数トポロジーと圏論のより抽象的な領域を扱いました。そこで彼女は、フルタイムで折り紙の数学を勉強しているハルにメールを送りました。

「彼女は突然私にメールを送ってきました。私は、なぜ代数トポロジストがこのことについて私に尋ねるのかと思いました。」ハルは言った。しかし彼は、折り紙がチューリング完全であるかどうかについて実際に考えたことがないことに気づきました。 「おそらくそうなのではないかと思ったのですが、実際のところはわかりません。」

そこで彼とザカレヴィッチは、折り紙でコンピューターを作れることを証明しようと試みた。まず、計算の入力と出力、および AND や OR などの基本的な論理演算を紙の折り目としてエンコードする必要がありました。その後、彼らのスキームがチューリング完全であることがすでに知られている他の計算モデルをシミュレートできることを示すことができれば、目標は達成されるでしょう。

論理演算は 1 つ以上の入力 (それぞれ TRUE または FALSE として書き込まれます) を受け取り、指定されたルールに基づいて出力 (TRUE または FALSE) を吐き出します。紙から演算を行うために、数学者は紙を折る場所を指定する折り目パターンと呼ばれる線の図を設計しました。紙のひだは入力を表します。折り目パターンの 1 つの線に沿って折り畳むと、プリーツは片側に反転し、入力値が TRUE であることを示します。しかし、別の (近くの) 線に沿って紙を折ると、プリーツは反対側に反転し、FALSE を示します。

これらの入力プリーツのうち 2 つは、ガジェットと呼ばれる複雑なひだの渦に組み込まれます。ガジェットは論理演算をエンコードします。これらすべての折り目を付けながら、紙を平らに折りたたむために (ハルとザカレヴィッチが課している要件)、特定の方法で強制的に折り畳む 3 番目のプリーツが含まれていました。プリーツが一方向に反転する場合、出力が TRUE であることを意味します。逆に反転すると、出力は FALSE になります。

数学者は、さまざまな論理演算に従って入力を出力に変換するさまざまなガジェットを設計しました。 「紙で遊んだり、お互いに写真を送ったり…そして、これらのことが私たちが言ったとおりに機能するという厳密な証拠を書くのはとても大変でした」とハル氏は語った。

1990 年代後半から、より単純な方法が知られていました。 一次元アナログ コンウェイの人生ゲームはチューリングが完了しました。ハルとザカレヴィッチは、論理演算の観点からこのバージョンの『ライフ』を書く方法を考え出しました。 「最終的には、AND、OR、NAND、NOR の 4 つのゲートを使用するだけで済みました」と、追加の 2 つの単純なゲートについてザカレビッチ氏は述べました。しかし、これらの異なるゲートを組み合わせるには、無関係な信号を吸収し、他の信号が互いに干渉することなく方向転換したり交差したりできる新しいガジェットを構築する必要がありました。 「それが最も難しい部分だった」とザカレビッチ氏は語った。「すべてを適切に並べる方法を見つけるのが大変だった」。彼女とハルがなんとか装置を組み合わせることができた後、必要なものすべてを紙の折り目にエンコードすることができ、それによって折り紙がチューリングとして完成したことを示しました。

折り紙コンピューターは非常に非効率で非実用的です。しかし原理的には、非常に大きな紙があり、時間がたっぷりあれば、折り紙を使って $latex pi$ の任意の桁数を計算したり、世界中のすべての配達ドライバーをルートする最適な方法を決定したりすることができます。天気を予測するプログラムを実行します。 「最終的に、しわのパターンは巨大になります」とハル氏は言う。 「折りたたむのは難しいですが、仕事はうまくいきます。」

何十年もの間、数学者が折り紙に惹かれてきたのは、「楽しそうだし、役に立たなさそうだったから」だという。 エリック・ドメーヌはマサチューセッツ工科大学のコンピューター科学者であり、折り紙の数学に広く貢献しています。しかし、最近ではエンジニアの注目も集めています。

折り紙の数学は、折りたたんで宇宙に輸送できる巨大なソーラーパネル、環境データを収集するために水の中を泳ぐロボット、小さな血管の中を移動するステントなどの設計に使用されています。 「現在、新しい機械構造の設計で私たちが開発したすべての折り紙の数学とアルゴリズムを、数千とは言わないまでも数百人が使用しています」とディメイン氏は言いました。

そのため、「このようなことをやればやるほど、折り紙と数学の確立された分野との間に深い交差を確立する可能性が高まると思います」とハル氏は語った。