白い紙一枚だけですべての計算を実行できますか?

折り紙は面白いが役に立たない技術だと多くの人が考えていますが、実際には、折り紙は「チューリング完全」であることが証明されています。折り紙数学は、折り畳んで宇宙に輸送できる大型太陽電池パネルの設計、環境データを収集するために水中を泳ぐことができるロボット、小さな血管を通過できるステント、DNAの折り畳みをシミュレートするツールなど、幅広い用途に応用されています。現在、何百人もの人々が折り紙の数学とアルゴリズムを使用して新しい機械構造を設計しています。

著者 |ジアウェイ

1936年、イギリスの数学者アラン・チューリングは汎用コンピュータのアイデアを提唱しました。それは単純な装置でした。0 と 1 で満たされた無限に長いテープと、テープに沿って前後に移動し、特定のルールに従って 0 を 1 に、またはその逆に変換できる機械です。彼は、そのような装置を使ってあらゆる計算を実行できることを実証しました。

チューリングは、実際の問題を解決するために思考実験で機械を使用するつもりはなかった。むしろ、コンピューティングの性質とその限界を探るための貴重な方法を提供します。この画期的なアイデアが生まれてから数十年の間に、数学者たちは実用性に欠ける計算スキームを数多く考案してきました。原理的には、古典的なマインスイーパーやマジック：ザ・ギャザリングのようなゲームは、汎用コンピュータとして使用できます。同じことは、ジョン・コンウェイの「ライフゲーム」のような、2次元グリッド上で黒と白の正方形を進化させるための一連のルールである、いわゆるセルオートマトンにも当てはまります。

ライフゲームとセルオートマトンについて

1970 年、イギリスの数学者ジョン・ホートン・コンウェイは、生命の進化と複雑性をシミュレートできる 2 次元セルオートマトンを発明しました。

生命ゲームのルールは非常にシンプルで、各ピクセルの生存 (明るい) と死 (暗い) および周囲の 8 つのセルとの相互作用のみが関係します。具体的には、セルと呼ばれる各ピクセルには、生きているか死んでいるかという 2 つの状態があります。次の瞬間の各セルの状態は、次の 4 つのルールによって決まります。

1. 細胞の周囲に生きている細胞が 2 個未満の場合、その細胞は孤独で死んでしまいます。

2. 細胞が 2 つまたは 3 つの生き残った細胞に囲まれている場合、その細胞は生き続けます。

3. 細胞の周囲に 3 つ以上の生きている細胞がある場合、その細胞は混雑により死んでしまいます。

4. 死んだ細胞がちょうど 3 つの生きている細胞に囲まれている場合、その細胞は復活します。

コンウェイのライフゲームの魅力は、極めて単純なルールを使用して、極めて複雑で多様な現象を生み出す点にあります。ゲームが進むにつれて、さまざまなセル構造が出現します。安定したもの、周期的なもの、動くもの、成長するもの、インタラクティブなもの、さらには計算可能なものもあります。

抽象的でわかりにくいですが、このビデオでは実際に、コンウェイのライフゲームから構築された宇宙船の形を使用して素数を検索するプロセスを示しています。言い換えれば、私たちはライフゲームを、素数を計算するプログラムを実行できる汎用コンピュータに変えたのです。これらの宇宙船は素数を表しています。これは 1991 年に Dean Hickerson によって発明されました。丨出典: Conway's Game of Life (conwaylife.com)

2023年9月、コーネル大学のインナ・ザカレビッチ氏とフランクリン・マーシャル大学のトーマス・ハル氏は、計算可能なものはすべて折り紙を使って計算できることを証明した。彼らは折り紙が「チューリング完全」であることを証明した。つまり、チューリングマシンのように、十分な時間があればどんな計算可能な問題も解けるということだ。

ザカレビッチさんは折り紙愛好家です。 2021年、彼女は偶然「ライフゲーム」のチューリング完全性を説明する動画を見たことをきっかけに、この疑問について考え始めました。「折り紙は人生ゲームよりもずっと複雑だと思っていました」とザカレビッチ氏は語った。「ライフゲームがチューリング完全であるならば、折り紙もチューリング完全であるはずです。」

コンピューティングの本質

科学界には、広義の計算的世界観と呼ばれるニッチな見解があります (狭義の計算主義は一種の認識論です)。スティーブン・ウルフラム（有名な数学ソフトウェア Wolfram Mathematica を開発した人物）のような最も過激な支持者は、宇宙全体が単なるセルオートマトンに過ぎないと信じています。私たちの物理法則、そして物質そのものさえも、ある種の計算の結果として現れます。まさに人生ゲームと同じ。そして、本当の科学とは、核となる計算ルールを見つけることです。過去 2 年間で、彼は熱力学の第二法則が特定の計算規則の結果であることを証明しました。

コンピューターの普及を考えると、彼が間違っていると言うことすら難しい。

計算の一般的な例としては、数式やコンピュータアルゴリズムが挙げられます。特定の計算を実行する機械的または電子的な装置（または歴史的には人）は、（狭義の）コンピュータと呼ばれます。

明確に定義されたステートメントまたは計算とは、チューリングマシンの初期パラメータを使用して明確に表現できるステートメントまたは計算です。チューリングマシンは、あらゆる計算可能なプロセスをシミュレートできる抽象的な計算モデルです。したがって、明確に定義されたプロパティを持つ数学的なステートメントまたは計算は計算可能と呼ばれ、ステートメントまたは計算自体は計算と呼ばれます。このような研究は、数理論理学とコンピュータサイエンスのサブフィールドである計算可能性の分野を構成します。

ただし、計算は、閉じた物理システム内で行われる純粋に物理的なプロセスとして見ることもできます。 1937 年のチューリングの証明は、計算可能なステートメントと、（広義では）総称してコンピュータと呼ばれる特定の物理システムとの間に形式的な同等性があることを示しました。

では、いくつかの共通ルールに従って紙を折ることで、この操作によって紙をコンピューターに変えることもできるのでしょうか?

残念ながら、コンピューターサイエンスはザカレビッチ氏の専門分野ではありませんでした。彼女は子供の頃から折り紙が大好きで、「24インチの紙を使って400ステップの超複雑な折り紙を頼まれたら、自分で折ります」と語るが、彼女の数学研究は代数的位相幾何学や圏論など、より抽象的な分野にまで及んでいる。そこで彼女は、折り紙の数学に全力を注いでいたハルにメールを送った。

「彼女は突然私にメールを送ってきたので、私は、なぜ代数位相学者が私にこんなことを尋ねるのだろうと思いました。」ハル氏は語った。しかし、彼は折り紙がチューリング完全であるかどうかについて考えたことがなかったことに気づいた。「そうかもしれないとは思ったけど、実際は確信が持てなかった」

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

折り紙について

中国人にとって、折り紙は正式な場で披露する価値のないつまらない技術なのかもしれない。未就学児が折り紙で遊ぶのは良いのですが、学校に行くと折り紙で遊ぶ時間がなくなってしまうのが一般的です。日本人はそうは考えません。彼らは折り紙を国宝とみなしています。折り紙協会があるだけでなく、全国の小学校で折り紙を必修科目にしています。日本人が折り紙を必修科目に選んだのは、単にそれが伝統的な芸術だからという理由だけではありません。同じく国の伝統芸術である華道や茶道は必修科目に含まれていなかった。

1970 年代に日本の学者吉澤章氏が折り紙の数学に注目し、それが後に日本における折り紙の数学の研究の最高潮へとつながりました。いくつかの研究グループが結成され、多くの研究論文が出版されました。

初期の研究者たちは、折り紙が3次までの方程式を解くことができ、1/nのような有理数を自然に計算（表現）できることに気づき、うれしい驚きを覚えました。それだけでなく、折り紙は、定規とコンパスによる作図では解けない問題、つまり、角度を三等分したり、立方体を倍にしたりといった問題も解くことができます (ただし、π は超越数であるため、円を二乗する問題は依然として解けません)。

現在までに、折り紙は学術分野でかなりの数学的分析を受けてきました。関心分野には、特定の紙モデルの平坦な折り畳み可能性（3 次元モデルを損傷することなく平らな面に圧縮できるかどうか）や、有理方程式を解くための折り紙の使用などがあります。

有名なナプキン折り問題もあります。正方形または長方形の紙を、周囲が元の正方形よりも大きくなるように平面図形に折ることは可能でしょうか?

折り紙で作った作品を切ると、素晴らしい折り紙定理と切り紙定理も得られます。つまり、1 枚の (理想的な) 紙を平らに折り、1 本の直線で切るだけで、直線のあるあらゆる形状を作成できます。これらの形状には、多角形（凹型になる場合もあります）、穴のある形状、およびそのような形状の集合（つまり、領域が接続されている必要はありません）が含まれます。

計算折り紙は、折り紙の問題を解決するためのアルゴリズムを研究するコンピュータサイエンスの新しい分野です。計算折り紙の分野も、ロバート・ラングが1990年代に底部を正確に折るためのTreeMakerアルゴリズムを提案して以来、長い道のりを歩んできました。折り紙の折りやすさの問題では、初期構成の折り目を使用して何かを折ることが目標です。折り紙の設計問題の結果は、折り紙の折りやすさの問題の結果よりも理解しやすいです。計算折り紙は、数学やコンピュータグラフィックスに関する高度な知識を必要とし、折り紙工芸のレベルにとどまらず、航空宇宙材料など多くの分野に多大な貢献をしてきました。

これらの技術は本質的に幾何学的な性質を持ち、特定の問題に対して明確で巧妙な構成を提供しますが、ザカレビッチ氏とハル氏は現在、明らかな折り紙のルールを使用して紙を折ることで、チューリングマシンの抽象的な機能を理論的に実装できるかどうかを理解したいと考えています。

論理演算は、1 つ以上の入力 (それぞれ「true」または「false」として記述されます) を受け取り、指定されたルールに従って「true」または「false」の値を出力します。数学者は、「紙の上で」計算を実行するために、折り目の位置を指示する「折り目パターン」と呼ばれる折れ線グラフを考案しました。紙の折り目は入力を表します。折り目パターンの線に沿って折ると、折り目が横に反転し、実際の入力値が示されます。しかし、別の（近くの）線に沿って紙を折ると、折り目は反対側に反転し、「偽」であることを示します。

論理的な真理値を表す折り目とシワ|画像出典: quantamagazine

入力フォールドのうち 2 つは、複雑なフォールド数学コンパイルガジェットに入力されます。ガジェットは論理演算をエンコードします。紙を平らに折りながらこれらすべての折り目を実現するために（ハル氏とザカレビッチ氏が提唱した要件）、彼らは 3 つ目のプリーツを追加して、紙を特定の方法で折るように強制しました。折り目が一方向に反転する場合、出力は「true」になります。反対側に反転すると、出力は「false」になります。

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

1990 年代後半から、コンウェイのライフゲームのより単純な 1 次元類似物がチューリング完全であることが知られています。ハル氏とザハリエヴィッチ氏は、折り紙で表現された論理演算を使用して、このバージョンのライフゲームを記述する方法を考案しました。「最終的に、AND、OR、NAND、NOR の 4 つのゲートだけを使う必要がありました。しかし、これらの異なるゲートを組み合わせるには、無関係な信号を吸収し、他の信号が互いに干渉することなく方向転換して交差できるようにする新しい装置を作成する必要がありました」とザカレビッチ氏は語った。

ザカレビッチ氏は、これが最も難しい部分だと考えている。すべてを正しく整列させる方法を見つけ出すこと。彼女とハルが装置をうまく組み立てた後、彼らは必要なものすべてを紙の折り目にエンコードすることができ、折り紙がチューリング完全であることを示した。

折り紙コンピューターは非常に非効率で実用的ではありません。しかし原理的には、大きな紙とたくさんの時間があれば、折り紙を使って任意の大きな桁の円周率を計算したり、世界中の配達ドライバー全員にとって最適なルートを決定したり、天気を予測するプログラムを実行したりすることができます。「最終的には、折り畳みの数は非常に多くなるだろう」とハル氏は語った。「物理的には非常に難しいですが、理論的には完璧に機能するはずです。」（紙を7回折ることはほとんど不可能です！）

役に立つ折り紙数学と役に立たない折り紙数学

数学者たちは何十年もの間、折り紙に魅了されてきました。 MITのコンピューター科学者であるエリック・デメイン氏にとって、「これは興味深いと同時に役に立たないように見えます。」

計算幾何学と計算折り紙における画期的な論文は、1999年に発表されました。当時ウォータールー大学の博士課程の学生だったエリック・デメイン氏が、一枚の紙を想像し得るあらゆる三次元形状に折る方法を決定できるアルゴリズムについて説明しました。ただし、この方法では実用的な折り畳みパターンは生成されず、主に理論的な実現可能性を示すものになります。

2017年7月の計算幾何学会議で、デモイン氏と東京大学の計算幾何学者舘知宏氏は、継ぎ目が最も少ないアルゴリズムを発見した。

研究者たちは、折り紙の形を折り曲げる際に継ぎ目の数を最小限に抑える一般的なアルゴリズムを作成した。画像提供: クリスティン・ダニロフ/マサチューセッツ工科大学

アメリカ数学会の会員であるロバート・ロング氏は、折り紙数学とコンピュータ折り紙の分野で最も権威のある現代の研究者です。彼は、折り紙作品がどんなに複雑であっても、数学を通してモデル化できることを証明しました。彼の著書『Origami Design Secrets』は折り紙のバイブルとみなされています。

しかし最近では、折り紙はエンジニアたちの注目も集めています。

折り紙数学の分野には、非常に有名な問題がいくつかあります。例えば、剛体折り紙の問題では、折り目がヒンジとみなされ、折り目の両側の紙の領域はヒンジによって接続された 2 つの剛体平面になります。この分野の研究は大きな実用的価値を持っています。たとえば、ミウラ折りは、宇宙の衛星用の大型太陽電池パネルアレイを展開するために長年使用されてきた剛性折りです。

昔は、衛星放送受信アンテナは 4 段または 8 段に積み重ねられていました。しかし、この折り畳み方式では、操作時に複雑な手順が必要になるだけでなく、多くのスペースが無駄になり、摩耗しやすいため、頻繁な修理とメンテナンスが必要になります。この目的のために、日本の学者三浦氏は、上記の問題を解決できる新しい技術を発明することに尽力しています。その結果、楕円柱表面のしわ構造はスペースを節約し、損失を防ぎ、高い強度を持つことがわかった[3]。これにより、彼は最終的に「対角端を引っ張って広げ、反対方向に押すと折りたたむ」という折り方を発明しました。丨出典: ミウラ折り - Wikipedia

折り紙の数学は、折り畳んで宇宙に輸送できる大型ソーラーパネル、水中を泳いで環境データを収集できるロボット、小さな血管を移動できるステント、DNAの折り畳みをシミュレートするツールなどの設計に使用されてきました。「今では何百人もの人々が、私たちが開発した折り紙の数学とアルゴリズムを使って新しい機械構造を設計しています」とデメイン氏は語った。

「このようなことをすればするほど、折り紙と数学の確立された分野との深い融合を生み出す機会が増えると思います」とハル氏は語った。

補足コンテンツ

折り紙で三次方程式を解く

数学において、リル法は、1867 年にオーストリアのエンジニアであるエドゥアルト・リルによって提案された、任意のべき乗の単変数多項式の実根を見つけるための直感的な方法です。後に、折り紙幾何学の研究者は、この技術が折り紙で 3 次方程式を解くための中核的なアルゴリズムでもあることに気付きました。以下は主に、Lear が多項式と方程式の根を視覚化する方法を示しています。特定の折り紙のプロセスと証明をスキップします。

リアの方法では、それぞれの長さが多項式の係数に等しい直線部分を直角に描きます。多項式の根は、始点と終点を結ぶ直角パスの傾きを求めることで見つけることができますが、その場合、頂点は最初のパスの直線上にあります。

折り紙を使って、整数係数を持つ 3 次方程式 4x3+2x2-2x-1=0 の根 -1/2、-1/√2、1/√2 を求めます。負の係数を扱い、線分を延長する方法を直感的に示すことに重点を置きます。

3次代数方程式のグラフィカル手法 |画像出典: リルのメソッド - Wikipedia

この方法を使用するには、原点から描画を開始する必要があります。最初の係数（最も高いべき乗項の係数）の大きさに応じて、右に線分を引きます（したがって、係数が負の場合、線分の終点は原点の左側になります）。最初の線分の端から、2 番目の係数のサイズだけ上に別の線分を描き、次に 3 番目の係数のサイズだけ左に、4 番目の係数のサイズだけ下に、というように描きます。方向の順序（曲がる順序ではない）は常に右、上、左、下、そしてその繰り返しです。したがって、各回転は反時計回りになります。これは多項式のすべての係数（ゼロを含む）に当てはまりますが、負の係数の場合は逆になります。これはまさに例の負の係数の場合です。到達した最後の点、つまり方程式の定数項に対応する線分の終点が終点となります。

次に、特定のルールに従って、絵の中に色のついた線を描きます。赤い線を例にとると、赤い線が形成する破線の直角はすべて 90° であり、赤い線は最終的に終点に落ちます。赤い線を決定できれば、対称性を利用して原点に接続する最初の青い線を決定し、直角線に基づいて青い線の終点を見つけることができます。

色付きの線上に示される各数値は、その傾きの反対であり、多項式の実根でもあります。

したがって、問題は本質的に、折り紙の方法を使用して、原点から始まる赤い線の傾斜を決定し、赤い線分が最終的に終点に落ちるようにすることです。具体的な議論はかなり複雑なので、興味のある方は詳細な情報については参考文献[7]を参照してください。

参照する

[1] [2309.07932v1] 平面折り紙はチューリング完全である (arxiv.org)

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

[3] 折り紙の数学 - Wikipedia

[4] 折り紙の公理 - Wikipedia

[5] TTのページ（tsg.ne.jp）

[6] リル法 - Wikipedia

[7] 折り紙数学 - 道具を捨てればさらに先へ進むことができる (IV) リリーの法則 - Bilibili (bilibili.com)

[8] ナサニエル・ジョンストン » コンウェイのライフゲームにおける素数列の生成