「“折り紙”コンピュータ」。折り目で「0」と「1」を表現しNANDゲート実装【研究紹介】

2024年6月27日

山下 裕毅

先端テクノロジーの研究を論文ベースで記事にするWebメディア「Seamless/シームレス」を運営。最新の研究情報をX(@shiropen2)にて更新中。

オーストラリアのメルボルン大学に所属する研究者が発表した論文「An origami Universal Turing Machine design」は、折り紙を用いて理論上の万能チューリングマシン(UTM)を設計する方法を提案した研究報告である。この研究は、理論的には折り紙によって、計算可能な任意の関数を計算できることを示している

(関連記事:電力不要「“ゴム”コンピュータ」 伸縮により「0」と「1」をカウント

研究内容

折り紙コンピュータは、紙の折り目でデータを表現し、コンピュータの基本的な論理回路である「NANDゲート」を折り紙でつくることで構築する。NANDゲートの組み合わせにより、他のすべての論理回路をつくり出せるため、NANDゲートさえあれば、現代のコンピュータと同じようなあらゆる計算が可能になる。

具体的な方法は以下の通りである。まず、2進数の0と1を、折り目の層の順序、平行な山折りと谷折り、そして選択した方向に基づいて定義する。次に、この0と1を使って論理演算を行うために、「NAE」(Not All Equal)と呼ばれる折り紙構造を利用する。これは3つの入力信号を受け取り、それらが全て等しくない場合にのみ平坦に折りたたむことができる。このNAEを巧妙に組み合わせ、NANDゲートの真理値表を実現する。

▲0と1を定義
▲NAEの構造図

さらに、NOTゲート、Reflector(反射)、Rotation(回転)、Duplication(複製)などの新しい折り紙構造を考案し、これらを組み合わせて完全なNANDゲートを構築する。

理論上の万能チューリングマシンを完成させるには、論理ゲートに加えてメモリ機能も必要となる。研究者は、Dフリップフロップレジスタを用いてメモリを実現できることを示した。レジスタにはNANDゲートとクロック信号の組み合わせが必要となり、クロック信号は一定の間隔で状態が反転する折り目によって表現される。

▲Rotation(左)、Duplication(中央)、NOTゲート(右)
▲NANDゲートの折り目パターンの概略図(左)と完全な折り目パターン(右)
▲NANDゲートを実際の紙で折った実物

研究評価

理論的には、無限の大きさの紙と無限のメモリがあれば万能チューリングマシンがつくれるとのこと。これは、折り紙によりどんな複雑な計算でも理論上は可能だということを示唆する

ただし、この研究はあくまで理論的な証明であり、実用的な折り紙コンピュータの製作を目指すものではない。計算の本質や物理的実装の可能性について、新たな視点を提供する理論的な探求だといえる。

Source and Image Credits: Assis, Michael. “An origami Universal Turing Machine design.” arXiv preprint arXiv:2406.08490 (2024).

関連記事

人気記事

  • コピーしました

RSS
RSS