Flat origami is Turing Complete
2023/09/13 by Thomas C. Hull, Inna Zakharevich, Hull, Thomas C. +1 · 17 voices · 1 citation
Biochemistry, Genetics and Molecular Biology · Engineering · #Advanced Materials and Mechanics #Cellular Mechanics and Interactions #Structural Analysis and Optimization #cs.CC #math.CO
paper · pdf · doi:10.48550/arxiv.2309.07932
openalex publication_date 2023/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Abstract
"Flat origami" refers to the folding of flat, zero-curvature paper such that the finished object lies in a plane. Mathematically, flat origami consists of a continuous, piecewise isometric map f:P⊆ℝ2→ℝ2 along with a layer ordering λf:P× P→ \-1,1\ that tracks which points of P are above/below others when folded. The set of crease lines that a flat origami makes (i.e., the set on which the mapping f is non-differentiable) is called its "crease pattern." Flat origami mappings and their layer orderings can possess surprisingly intricate structure. For instance, determining whether or not a given straight-line planar graph drawn on P is the crease pattern for some flat origami has been shown to be an NP-complete problem, and this result from 1996 led to numerous explorations in computational aspects of flat origami. In this paper we prove that flat origami, when viewed as a computational device, is Turing complete, or more specifically P-complete. We do this by showing that flat origami crease patterns with "optional creases" (creases that might be folded or remain unfolded depending on constraints imposed by other creases or inputs) can be constructed to simulate Rule 110, a one-dimensional cellular automaton that was proven to be Turing complete by Matthew Cook in 2004.
Cited by
Discussions
- Flat origami is Turing complete [lobsters, 19 points, 1 comments]
- Me: Origami's so mathematical! You can solve cubics, there's combinatorics in the colouring schemes! arXiv: Origami is Turing-complete. Me: ????? arXiv: Oh, and it involves Tortillas and Tacos. #origa [bsky, 13 points, 0 comments]
- Flat origami is Turing Complete [hn, 4 points, 1 comments]
- Flat origami is Turing complete (2023) [hn, 4 points, 1 comments]
- Er lebt im Kallax-Regal, liebt Kibbelinge, findet jeden Bug, aber beim Phishing hört der Spaß bei ihm auf. Seine Lieblingslektüre: arxiv.org/abs/2309.07932). Tagsüber programmiert er, nachts träumt er [bsky, 3 points, 1 comments]
- Flat origami is Turing Complete [hn, 2 points, 1 comments]
- Flat origami is Turing Complete [hn, 2 points, 0 comments]
- Flat origami is Turing Complete (2023) [hn, 2 points, 1 comments]
- Spending a few cycles this evening cleaning up browser tabs from earlier this year (and earlier). In reading this paper (which is :chefs_kiss:) I am driven to ask a stupid undergrad gotcha reversal qu [bsky, 2 points, 2 comments]
- A win is a win Flat origami is Turing Complete Thomas C. Hull, Inna Zakharevich arxiv.org/abs/2309…. [bsky, 1 points, 0 comments]
- There's a lot of computational power in geometric transformations. [bsky, 1 points, 0 comments]
- https://arxiv.org/abs/2309.07932 この海外論文は、平面折り紙がチューリング完全であることを証明しています。 平面折り紙の折り目パターンが、Rule 110という一次元セルオートマトンをシミュレートできることを示しています。 Rule 110はMatthew Cookによってチューリング完全であることが証明されています。 [bsky, 1 points, 0 comments]
- 折り紙はチューリング完全 arxiv.org/abs/2309.07932 [bsky, 0 points, 1 comments]
- Flat origami is Turing complete (2023) https://arxiv.org/abs/2309.07932 (https://news.ycombinator.com/item?id=43758762) [bsky, 0 points, 0 comments]
- Flat origami is Turing complete https://lobste.rs/s/tanhwa #math [bsky, 0 points, 0 comments]
- https://bsky.app/profile/lobste.rs.web.brid.gy/post/3lmryrkjswpl2 [bsky, 0 points, 0 comments]
- Flat origami is Turing complete (2023) https://arxiv.org/abs/2309.07932 [bsky, 0 points, 0 comments]
Related