  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.
