Mathematics > Combinatorics

arXiv:2309.07932 (math) [Submitted on 13 Sep 2023 (v1), last revised 26 Feb 2025 (this version, v4)]

Title:Flat origami is Turing Complete

Authors:Thomas C. Hull, Inna Zakharevich View a PDF of the paper titled Flat origami is Turing Complete, by Thomas C. Hull and 1 other authors View PDF

Abstract:"Flat origami"（平面折纸）指的是将平坦、零曲率的纸张进行折叠，使得最终物体位于一个平面内。从数学上讲，平面折纸包含一个连续的分段等距映射 f:P\subseteq\mathbb{R}^2\to\mathbb{R}^2，以及一个层排序 \lambda_f:P\times P\to \{-1,1\}，用于跟踪 P 中哪些点在折叠后位于其他点的上方/下方。平面折纸形成的折痕线集合（即映射 f 不可微的集合）被称为其“crease pattern”（折痕模式）。平面折纸映射及其层排序可以具有非常复杂的结构。例如，确定绘制在 P 上的给定直线平面图是否为某些平面折纸的折痕模式已被证明是一个 NP-complete 问题，并且 1996 年的这一结果导致了对平面折纸计算方面的许多探索。在本文中，我们证明了平面折纸，当被视为一种计算设备时，是图灵完备的，或者更具体地说是 P-complete。我们通过展示具有“optional creases”（可选折痕）的平面折纸折痕模式（根据其他折痕或输入施加的约束，这些折痕可能会被折叠或保持未折叠）可以被构造来模拟 Rule 110，这是一种由 Matthew Cook 在 2004 年证明为图灵完备的一维 cellular automaton。 Subjects: | Combinatorics (math.CO); Computational Complexity (cs.CC)
---|---
Cite as: | arXiv:2309.07932 [math.CO]
(or arXiv:2309.07932v4 [math.CO] for this version)
https://doi.org/10.48550/arXiv.2309.07932 Focus to learn more arXiv-issued DOI via DataCite

Submission history

From: Inna Zakharevich [view email] [v1] Wed, 13 Sep 2023 20:15:49 UTC (32 KB) [v2] Sun, 3 Mar 2024 00:26:46 UTC (32 KB) [v3] Tue, 18 Feb 2025 14:36:43 UTC (32 KB) [v4] Wed, 26 Feb 2025 14:20:22 UTC (34 KB) Full-text links:

Access Paper:

View a PDF of the paper titled Flat origami is Turing Complete, by Thomas C. Hull and 1 other authors