# Flat origami is Turing Complete

- Published in 2023
- Added on

In the collections

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\subseteq\mathbb{R}^2\to\mathbb{R}^2$ along with a layer ordering $\lambda_f:P\times P\to \{-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 \textit{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. We do this by showing that flat origami crease patterns with \textit{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.

## Links

## Other information

- key
- FlatorigamiisTuringComplete
- type
- article
- date_added
- 2023-09-29
- date_published
- 2023-05-24

### BibTeX entry

@article{FlatorigamiisTuringComplete, key = {FlatorigamiisTuringComplete}, type = {article}, title = {Flat origami is Turing Complete}, author = {Thomas C. Hull and Inna Zakharevich}, 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\subseteq\mathbb{\{}R{\}}^2\to\mathbb{\{}R{\}}^2{\$} along with a layer ordering {\$}\lambda{\_}f:P\times P\to \{\{}-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 \textit{\{}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. We do this by showing that flat origami crease patterns with \textit{\{}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.}, comment = {}, date_added = {2023-09-29}, date_published = {2023-05-24}, urls = {http://arxiv.org/abs/2309.07932v1,http://arxiv.org/pdf/2309.07932v1}, collections = {basically-computer-science,computational-complexity-of-games,unusual-computers}, url = {http://arxiv.org/abs/2309.07932v1 http://arxiv.org/pdf/2309.07932v1}, year = 2023, urldate = {2023-09-29}, archivePrefix = {arXiv}, eprint = {2309.07932}, primaryClass = {math.CO} }