盡管很多人把折紙看作有趣但無用的雕蟲小技，但實際上，折紙已被證明是「圖靈完備」的；折紙數學正在獲得廣泛套用，如設計可折疊並運入太空的大型太陽能電池板、可在水中遊泳以收集環境數據的機器人、可在微小血管中穿行的支架，以及模擬DNA折疊工具等。現在有成百上千的人在使用折紙數學和演算法來設計新的機械結構。
1936年， 英國數學家阿蘭·圖靈提出了通用電腦的想法 。那是一個簡單的裝置：一條無限長的磁帶，上面寫滿了0和1，還有一台機器，可以沿著磁帶來回移動，按照一定的規則將0變為1，反之亦然。他證明，這樣一個裝置可以用來進行任何計算。
圖靈並不打算將他思想實驗裏的機器用於解決實際問題。相反，它是為探索 計算的本質 及其極限提供了一種寶貴的方法。 在這一開創性想法提出後的幾十年裏，數學家們提出了一系列實用性更低的計算方案 。原則上，如經典的【踩地雷】或【萬智牌】這樣的遊戲都可以用作通用電腦。約翰·康威 （John Conway） 的 「生命遊戲」 （Game of Life） 等所謂的元胞自動機也是如此，後者是一套在二維網格上演化黑白方格的規則。
關於生命遊戲與元胞自動機
英國數學家約翰·何頓·康威在1970年發明了一種 二維的細胞自動機 ，它可以模擬生命的演化和復雜性。
生命遊戲的規則非常簡單，只涉及到每個像素點的存活 （亮） 和死亡 （暗） ，以及它們與周圍8個細胞的互動。具體來說，每個像素點，我們叫它細胞，有兩種狀態：存活或死亡。 每個細胞在下一個時刻的狀態取決於以下四條規則 ：
1.如果一個細胞周圍有少於兩個存活的細胞，它會因為孤獨而死亡。
2.如果一個細胞周圍有兩個或三個存活的細胞，它會繼續存活。
3.如果一個細胞周圍有超過三個存活的細胞，它會因為擁擠而死亡。
4.如果一個死亡的細胞周圍有正好三個存活的細胞，它會重新復活。
康威的生命遊戲的魅力在於， 它用極其簡單的規則，卻能產生出極其復雜和多樣的現象 。在遊戲的進行中，可以出現各種各樣的細胞結構，有些是穩定的，有些是周期性的，有些是移動的，有些是增長的，有些是互動的，甚至有些是可計算的。
雖然很抽象晦澀，但這段視訊實際上是在用康威的【生命遊戲】中構建的宇宙飛船形態搜尋質數的過程。也就是說，我們把【生命遊戲】變成了一個可以執行計算質數程式的廣義電腦。這些飛船正好代表質數。它是由迪恩·希克森（Dean Hickerson）於1991年發明的。丨圖源：Conway's Game of Life (conwaylife.com)
2023年9月， 康奈爾大學的英娜·紮卡雷維奇（Inna Zakharevich）和富蘭庫林與馬歇爾學院的湯瑪斯·赫爾（Thomas Hull）證明，任何可以計算的東西都可以透過折紙來計算 。他們證明了折紙是「圖靈完備」的—— 這意味著，就像圖靈機一樣，只要有足夠的時間，它就能解決任何可計算問題 。
紮卡雷維奇是一名折紙愛好者。2021年，她在偶然看到一段解釋「生命遊戲」圖靈完備性的視訊後，開始思考這個問題。「我當時想，折紙比生命遊戲復雜得多。」紮卡雷維奇說，「如果生命遊戲是圖靈完備的，那麽折紙也應該是圖靈完備的。」
計算的本質
科學界有一種小眾主張，叫 廣義的 計算主義世界觀 （狹義的計算主義是一種認識論） 。其中最激進的鼓吹者如沃爾夫勒姆 （開發了著名的數學軟體Wolfram Mathematica的Stephen Wolfram） ，認為整個宇宙不過是台元胞自動機。我們的物理學規律、乃至物質本身，都是某種計算結果湧現。就和生命遊戲一樣。而真正的科學是尋找核心的計算規則。他在最近兩年甚至證明出，熱力學第二定律就是特定計算規則的結果。
考慮到計算的普遍性，我們甚至很難說他的觀點是錯的。
常見的計算的例子有數學方程式和電腦演算法。執行具體計算的機械或電子裝置 （或者歷史上的人） 被稱為 （狹義上的） 電腦。
良定義 （well-defined） 是指一個數學陳述或計算可以被明確地表達為一個圖靈機的初始參數 。圖靈機是一種抽象的計算模型，可以模擬任何可計算的過程。因此，任何 具有良定義性質的數學陳述或計算都被稱為可計算的 （computable） ，而陳述或計算本身被稱為計算 （computation） 。此類研究構成了可計算性領域，它是數理邏輯和電腦科學的一個子領域。
但是，計算也可以被看作是發生在一個封閉的物理系統中的純物理過程。圖靈在1937年的證明表明， 可計算陳述和特定的物理系統之間存在著形式上的等價性，這些物理系統也被一並稱為 （廣義上的） 電腦 。
那對一張紙按一些常見的規則進行折疊，這一操作也可以把紙變成電腦嗎？
可惜的是，計算科學並不是紮卡雷維奇的專業領域。雖然她從小就喜歡折紙——「如果你想給我一個超級復雜的東西，需要一張24英寸的紙，有400個步驟，我都會親手操作一番。」但她的數學研究涉及代數拓撲學和範疇論等更為抽象的領域。於是，她給全心研究折紙數學的赫爾發了電子信件。
「她突然就給我發了信件，我當時就想，為什麽一個代數拓撲學家會問我這個？」赫爾說。但他意識到自己從未想過折紙是否可能是圖靈完備的。「我當時想，可能是如此，但實際上我並不確定。」
於是，他和紮卡雷維奇開始證明， 折紙可以轉化成電腦 。 首先，他們必須將計算輸入和輸出以及AND和OR等基本邏輯運算編碼成用紙折出的構型 。如果他們能證明他們的方案可以模擬其他已知圖靈完備的計算模型，那麽他們就達到了目的。
關於折紙
折紙，在一些人看來或許是些不登大雅之堂的雕蟲小技，學齡前兒童玩玩就算了，上了學，一般就沒時間玩折紙了。日本人卻不這麽看。他們把折紙視為國粹，不但有折紙協會，還把折紙列為了全國小學必修科目。日本人並不是因為折紙屬於傳統藝術，就決定將它列入必修課的；同是該國傳統藝術的插花、茶道，就沒有被列入必修課。
20世紀70年代，日本學者吉澤章 （Akira Yoshizawa） 將目光投向折紙中的數理，之後在日本形成了一個研究折紙數理的高潮，結成了多個研究團體，也出版了許多的專著。
這些早期研究者驚喜地意識到，折紙甚至可以解三次以內方程式，至於1/n這種有理數自然是可以求 （表示） 出來的；不僅如此，折紙可以解決三等分角和倍立方體這兩個尺規作圖不能解的問題 （然而還是不能解決化圓為方，因為π是超越數） 。
到今天，在學術領域，折紙已經得到了相當多的數學分析 。人們感興趣的領域包括特定紙模型的平整可折疊性 （立體模型能否在不損壞的情況下被壓成平面） ，以及用折紙法求解有理方程式。
此外還有著名的餐巾折疊問題：是否可以把一張正方形或長方形的紙折疊成一個平面圖形，使得它的周長大於原來的正方形。
如果對折好的紙作品進行剪下的話，我們還有美妙的 折 疊和切割定理 ：任何具有直邊的形狀都可以透過從單張 （理想化） 紙上將其折疊平整並進行單個直線完全切割而來。這些形狀包括多邊形 （可以是凹形的） 、帶孔的形狀以及此類形狀的集合 （即區域不需要連線） 。
計算折紙學是電腦科學的一個最新的分支，主要研究解決折紙問題的演算法。 自20世紀90年代勞勃·朗 （Robert Lang） 提出TreeMaker演算法以幫助精確折疊底座以來，計算折紙領域也取得了長足的發展。 在折紙可折疊性問題中，目標是利用初始構型的折痕折疊某物 。折紙設計問題的結果比折紙可折疊性問題的結果更容易理解。計算折紙對數學和電腦圖形學方面知識的要求很高，而且在航空材料等很多領域都有巨大貢獻，而不只是停留在折紙工藝品的層面上。
不過上述技術本質上是基於幾何的——針對具體問題給出明確而巧妙的構造，紮卡雷維奇與赫爾現在則是希望了解，借助一些顯而易見的折紙規則， 能否透過折疊一張紙，從理論上實作圖靈機的抽象功能？
邏輯運算 接受一個或多個輸入 （每個輸入都寫成「真」或「假」） ，並根據給定的規則輸出「真」或「假」的值。為了在「紙上」進行運算，數學家們設計了一個名為 折痕模式 的線條圖，規定了折痕的位置。紙上的褶代表輸入。如果沿著折痕圖案中的一條線折疊，褶皺就會翻轉到一邊，表示輸入值為「真」。但如果沿著不同的 （附近的） 線折疊紙張，褶皺就會翻轉到其反面，表示「假」。
代表邏輯真值的折痕與褶皺丨圖源：quantamagazine
其中兩個輸入褶被送入一個復雜的褶皺數學編譯小工具。小工具對邏輯運算進行編碼。為了在完成所有這些折疊的同時還能使紙張折疊平整——這是赫爾和紮卡雷維奇提出的要求——他們加入了第三個褶皺，迫使它以特定的方式折疊。 如果褶皺以一種方式翻轉，則表示輸出為「真」。若翻轉向另一側，則輸出為「假」。
數學家們設計了不同的小工具，根據各種邏輯運算將輸入轉化為輸出。赫爾說：「我們在紙上玩了很久，互相發送圖片......然後寫出嚴格的證明，證明這些東西按照我們所說的方式運作。」
自20世紀90年代末以來，人們就知道康威生命遊戲的一個更簡單的一維類似物是圖靈完備的。 赫爾和紮哈雷維奇想出了如何用折紙代表的邏輯運算來編寫這個版本的「生命」遊戲 。「我們最終只需要使用 四個門：AND、OR、NAND和NOR 。但要將這些不同的門 組 合 起來，他們必須制造新的小工具，吸收無關訊號，並允許其他訊號在不相互幹擾的情況下轉向和交叉。」紮卡雷維奇說。
紮卡雷維奇認為，這是最困難的部份。要想辦法讓所有東西都正確地排列在一起。 在她和赫爾成功地將他們的小工具組裝在一起後，他們可以將所需的一切都編碼在紙張折疊中，從而表明折紙是圖靈完備的 。
折紙電腦的效率非常低，而且不切實際。但從原理上講，如果我們有一張很大的紙和大量的時間，你可以用折紙計算出任意多位數的π、確定世界上所有送貨司機的最佳路線，或者執行一個預測天氣的程式。赫爾說：「最終，折疊次數將非常巨大。 在物理上很難完成，但理論上它能完美工作 。」 （真實世界裏的紙，我們都難以把它對折7次！）
有用與無用的折紙數學
幾十年來，數學家們被折紙所吸引。在麻省理工學院電腦科學家艾瑞克·德梅因 （Erik Demaine） 看來，「它看起來既有趣又無用」。
計算幾何——計算折紙學裏劃時代的論文出自1999年，正是艾瑞克·德梅因——那時的滑鐵盧大學博士研究生——描述了一種能決定如何將一張紙折為任何可想象到的三維形狀的演算法。但這種方法並沒有得出非常實用的折疊模式，主要在於闡明了理論上的可行性。
在2017年7月舉行的計算幾何學討論會上，德梅因和東京大學的計算幾何學家舘知宏 （Tomohiro Tachi） 又找到了接縫最少的演算法。
研究人員建立了一種用於折疊折紙形狀的通用演算法，可以保證最少的接縫數量。丨圖源：Christine Daniloff/麻省理工學院
美國數學會成員勞勃·朗是當代最富盛名的折紙數學和電腦折紙學研究者，他證明了無論多麽復雜的折紙作品，都可透過數學來建模。他撰寫的著作Origami Design Secrets被譽為折紙的聖經。
但 最近，折紙也吸引了工程師的目光 。
在折紙數學領域，存在若幹非常著名的問題。如剛性折紙的問題，把折痕看成是鉸鏈，折痕兩邊的紙區域是兩個被鉸鏈連線的剛性平面。 這方面的研究具有很大的實用價值 。如Miura地圖折疊是一種剛性折疊，早已用於為太空衛星部署大型太陽能電池板陣列。
在過去，衛星天線是使用四疊或八疊法。然而，這折疊方法非但在運作時需繁復的工序，更浪費不少空間，又容易損耗，需經常維修和保養。為此，日本學者三浦公亮（Miura）致力發明一種能解決上述問題的新技術。結果，他發現橢圓筒表面的褶皺構造有利節省空間又能避免損耗，而且強度高[3]。這最終使他發明了「拉開對角兩端來把物品展開，而在收縮時則反向推入」的折疊方法。丨圖源：Miura fold - Wikipedia
折紙數學已被用於設計可折疊並運入太空的大型太陽能電池板、可在水中遊泳以收集環境數據的機器人、可在微小血管中穿行的支架，以及模擬DNA折疊工具等 。德梅因說：「現在有成百上千的人在使用我們開發的所有折紙數學和演算法來設計新的機械結構。」
因此，「我們越是做這樣的事情，」赫爾說，「我認為我們就越有機會在折紙和成熟的數學分支之間建立深度交叉。」
補充內容
利爾法折紙解三次方程式
在數學中， 利爾法 是一種尋找任意次冪一元多項式實根的直觀方法，由奧地利工程師愛德華·利爾 （Eduard Lill） 於1867年提出。後來折紙幾何的研究者意識到， 這一技術恰好也是折紙解三次方程式的核心演算法 。下面主要展示利爾如何把多項式和方程式的根直觀化。略過具體折紙過程和證明。
利爾的方法是畫成直角的直線段，每條長度等於多項式的系數。多項式的根可以透過其直角路徑的斜率找到，這些路徑也連線起點和終點，但頂點在第一條路徑的直線上。
用折紙求整系數三次方程式 4x+2x-2x-1=0的根-1/2、-1/√2 和 1/√2，重點在於直觀顯示如何處理負系數和延長線段。
三次代數方程式的圖示法丨圖源：Lill's method - Wikipedia
要使用這種方法，需要從原點開始畫圖。根據第一個系數 （最高冪項的系數） 的大小向右畫一條線段 （因此，如果系數為負，線段的終點將在原點的左邊） 。從第一條線段的末端開始，按第二個系數的大小向上繪制另一條線段，然後按第三個系數的大小向左繪制，再按第四個系數的大小向下繪制，依此類推。方向 （不是轉折） 的順序總是向右、向上、向左、向下，然後重復。因此，每一圈都是逆時針方向。多項式的每個系數 （包括零） 都是如此，負系數則「倒著走」——例題正是有負系數的情況。最後到達的點，也就是方程式常數項對應線段的末端，就是終點。
再按照一定的規則畫出圖裏的彩線。以紅線為例，它構成的折線直角都是90°，且紅線最終也要落在終點上。如果能夠確定紅線，就能借助對稱性，確定和原點相連的第一條藍線，然後根據直角折線找到藍線的終點。
彩色線上顯示的每個數位都是其斜率的相反數，也是多項式的實數根。
所以， 問題本質上就是用折紙的方法，確定由原點出發的那段紅線的斜率，保證紅線折線段最後可以落在終點上 。具體論證比較繁復，有興趣的朋友可以見參考[7]裏的詳細資料。
參考：
[1] [2309.07932v1] Flat origami is Turing Complete (arxiv.org)
[2] How to Build an Origami Computer | Quanta Magazine
[3] Mathematics of paper folding - Wikipedia
[4] 折り紙公理 - Wikipedia
[5] TT's Page (tsg.ne.jp)
[6] Lill's method - Wikipedia
[7] 折紙數學-扔掉工具，你能走的更遠（四）莉兒法則 - 嗶哩嗶哩 (bilibili.com)
[8] Nathaniel Johnston » Generating Sequences of Primes in Conway's Game of Life
來 源：返樸
編輯：virens
轉載內容僅代表作者觀點
不代表中科院物理所立場
如需轉載請聯系原公眾號
