# Flat origami is Turing Complete

• Published in 2023
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.

## Other information

key
FlatorigamiisTuringComplete
type
article
2023-09-29
date_published
2023-11-28

### 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 = {},
}