Flat origami is Turing Complete

• Published in 2023
• Added on 2023-09-29

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

• http://arxiv.org/abs/2309.07932v1
• http://arxiv.org/pdf/2309.07932v1

Other information

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-12-07},
	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}
}