如何制作折纸电脑 |广达杂志

1936年，英国数学家艾伦·图灵提出了通用计算机的想法。这是一个简单的设备：一条无限长的胶带，上面覆盖着零和一，还有一台可以沿着胶带来回移动的机器，根据一组规则将零更改为一，反之亦然。他证明了这样的设备可以用来执行任何计算。

图灵并不打算让他的想法实际用于解决问题。相反，它提供了一种探索计算本质及其局限性的宝贵方法。自从这个开创性的想法诞生以来的几十年里，数学家们已经列出了一系列甚至不太实用的计算方案。原则上，扫雷或万智牌等游戏可以用作通用计算机。像约翰·康威这样的所谓元胞自动机也可以 生命之游戏，一组在二维网格上演化黑白方块的规则。

在9月2023， 伊娜·扎哈列维奇 康奈尔大学和 托马斯·赫尔 富兰克林与马歇尔学院的研究表明，任何可以计算的东西 可以通过折叠纸来计算。他们证明了折纸是“图灵完备的”——这意味着，就像图灵机一样，只要有足够的时间，它就可以解决任何易于处理的计算问题。

扎哈列维奇是一位终生的折纸爱好者，在偶然发现一段解释生命游戏图灵完备性的视频后，他于 2021 年开始思考这个问题。 “我当时想，折纸比生命游戏复杂得多，”扎哈列维奇说。 “如果生命游戏是图灵完备的，那么折纸也应该是图灵完备的。”

但这不是她的专业领域。尽管她从小就开始折纸——“如果你想给我一个超级复杂的东西，需要一张 24 英寸的纸，有 400 个步骤，我就喜欢这个东西，”她说——数学研究涉及代数拓扑和范畴论等更为抽象的领域。于是她给赫尔发了一封电子邮件，赫尔全职研究折纸数学。

“她突然给我发了一封电子邮件，我就想，为什么代数拓扑学家要问我这个问题？”赫尔说道。但他意识到自己从未真正考虑过折纸是否是图灵完备的。 “我当时想，可能是这样，但我实际上不知道。”

因此，他和扎哈列维奇开始证明可以用折纸制作计算机。首先，他们必须将计算输入和输出以及 AND 和 OR 等基本逻辑运算编码为纸张折叠。如果他们能够证明他们的方案可以模拟其他一些已知的图灵完备的计算模型，他们就可以实现他们的目标。

逻辑运算接受一个或多个输入（每个输入写为 TRUE 或 FALSE），并根据给定规则输出一个输出（TRUE 或 FALSE）。为了用纸进行运算，数学家设计了一种称为折痕图案的线图，它指定了纸张的折叠位置。纸上的褶皱代表输入。如果沿折痕图案中的一条线折叠，褶皱会翻转到一侧，指示输入值为 TRUE。但是，如果您沿着不同的（附近的）线折叠纸张，褶皱会翻转到其相反的一侧，指示“FALSE”。

其中两个输入褶皱形成复杂的褶皱，称为小工具。小工具对逻辑操作进行编码。为了完成所有这些折叠，并且仍然让纸张折叠平整（这是赫尔和扎哈列维奇提出的要求），他们添加了第三个褶皱，该褶皱被迫以特定方式折叠。如果褶皱向一侧翻转，则意味着输出为 TRUE。如果翻转方向相反，则输出为 FALSE。

数学家设计了不同的小工具，根据各种逻辑运算将输入转换为输出。 “我们花了很多时间在纸上玩耍，互相发送图片……然后写出严格的证明，证明这些东西按照我们所说的方式工作，”赫尔说。

自 1990 世纪 XNUMX 年代末以来，人们就知道一种更简单的方法 一维模拟 康威的生命游戏是图灵完备的。赫尔和扎哈列维奇想出了如何用逻辑运算来编写这个版本的《生活》。 “我们最终只需要使用四个门：AND、OR、NAND 和 NOR，”Zakharevich 说，他指的是另外两个简单的门。但为了将这些不同的门结合起来，他们必须建造新的小工具来吸收无关信号并允许其他信号转动和交叉而不互相干扰。 “这是最难的部分，”扎哈列维奇说，“弄清楚如何让一切都正确排列。”在她和赫尔设法将他们的小玩意组装在一起后，他们可以将他们需要的所有东西编码在纸折叠中，从而表明折纸是图灵完整的。

折纸计算机效率极低且不切实际。但原则上，如果你有一张非常大的纸并且手上有很多时间，你可以使用折纸来计算 $latex pi$ 的任意位数，确定世界上每个送货司机的最佳路线，或者运行一个程序来预测天气。 “最后，折痕图案非常巨大，”赫尔说。 “虽然很难折叠，但它可以完成任务。”

几十年来，数学家们都被折纸所吸引，因为“它看起来很有趣而且没什么用，”说 Erik Demaine麻省理工学院的计算机科学家，对折纸数学做出了广泛贡献。但最近它也引起了工程师的注意。

折纸数学已被用来设计可以折叠并运输到太空的大型太阳能电池板、在水中游泳以收集环境数据的机器人、穿过微小血管的支架等等。 “现在有数百甚至数千人在使用我们在设计新机械结构时开发的所有折纸数学和算法，”Demaine 说。

因此，“我们做这样的事情越多，”赫尔说，“我认为我们在折纸和成熟的数学分支之间建立深度交叉的机会就越大。”