折叠门盘算方法_仅用一张白纸竟然就能实现所有计算

只管很多人把折纸看作有趣但无用的雕虫小技，但实际上，折纸已被证明是“图灵完备”的；折纸数学正在得到广泛运用，如设计可折叠并运入太空的大型太阳能电池板、可在水中拍浮以网络环境数据的机器人、可在眇小血管中穿行的支架，以及仿照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年提出。
后来折纸几何的研究者意识到，这一技能恰好也是折纸解三次方程的核心算法。
下面紧张展示利尔如何把多项式和方程的根直不雅观化。
略过详细折纸过程和证明。

利尔的方法是画成直角的直线段，每条长度即是多项式的系数。
多项式的根可以通过其直角路径的斜率找到，这些路径也连接出发点和终点，但顶点在第一条路径的直线上。

用折纸求整系数三次方程 4x3+2x2-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