• Abstract 主要内容：“平面折纸”指将平面零曲率纸折叠，使成品在平面内。数学上，它由连续分段等距映射$f:P\subseteq\mathbb{R}^2\to\mathbb{R}^2$和层序$\lambda_f:P\times P\to\{-1,1\}$组成，用于跟踪折叠时$P$的点的上下关系。平面折纸的折痕线集（即映射$f$不可微的集合）称为“折痕图案”。平面折纸映射及其层序结构复杂，如确定给定在$P$上的直线平面图是否为某平面折纸的折痕图案是 NP 完全问题，1996 年的该结果引发了平面折纸计算方面的诸多探索。本文证明平面折纸作为计算设备是图灵完备的，即更具体的 P 完备，通过展示带有“可选折痕”（根据其他折痕或输入的约束可能折叠或保持未折叠的折痕）的平面折纸折痕图案可模拟 2004 年 Matthew Cook 证明为图灵完备的一维细胞自动机 Rule110。
• Subjects：组合数学（math.CO）；计算复杂性（cs.CC）
• Cite as：arXiv:2309.07932 [math.CO]（或此版本的arXiv:2309.07932v4 [math.CO]）；https://doi.org/10.48550/arXiv.2309.07932（通过 DataCite 的 arXiv 发布的 DOI）
• Submission history：从 Inna Zakharevich 提交，查看邮件，[v1]：2023 年 9 月 13 日周三 20:15:49 UTC（32 KB）；[v2]：2024 年 3 月 3 日周日 00:26:46 UTC（32 KB）；[v3]：2025 年 2 月 18 日周二 14:36:43 UTC（32 KB）；[v4]：2025 年 2 月 26 日周三 14:20:22 UTC（34 KB）