Exploring the Limits of Computation: Origami as a Turing Complete Device

Thursday - February 1 2024, 12:40 UTC - 9 months ago

In 2023, mathematicians Inna Zakharevich and Thomas Hull proved that origami is Turing complete, meaning it can solve any tractable computational problem. Their research showcases the potential of unconventional computing devices and has garnered attention from both mathematicians and origami enthusiasts.

In 1936, the British mathematician Alan Turing came up with an idea for a universal computer. It was a simple device: an infinite strip of tape covered in zeros and ones, together with a machine that could move back and forth along the tape, changing zeros to ones and vice versa according to some set of rules. He showed that such a device could be used to perform any computation. Turing did not intend for his idea to be practical for solving problems .

Rather, it offered an invaluable way to explore the nature of computation and its limits. In the decades since that seminal idea, mathematicians have racked up a list of even less practical computing schemes. Games like Minesweeper or Magic: The Gathering could, in principle, be used as general-purpose computers. So could so-called cellular automata like John Conway’s Game of Life, a set of rules for evolving black and white squares on a two-dimensional grid .

In September 2023, Inna Zakharevich of Cornell University and Thomas Hull of Franklin & Marshall College showed that anything that can be computed can be computed by folding paper. They proved that origami is "Turing complete" — meaning that, like a Turing machine, it can solve any tractable computational problem, given enough time. Zakharevich, a lifelong origami enthusiast, started thinking about this problem in 2021 after stumbling on a video that explained the Turing completeness of the Game of Life .

"I was like, origami is a lot more complicated than the Game of Life," Zakharevich said. "If the Game of Life is Turing complete, origami should be Turing complete too." But this wasn’t her area of expertise. Although she’d been folding origami since she was young — "if you want to give me a super complex thing that requires a 24-inch sheet of paper and has 400 steps, I’m all over that thing," she said — her mathematical research dealt with the much more abstract realms of algebraic topology and category theory .

So she emailed Hull, who studied the math of origami full time. "She just emailed me out of the blue, and I was like, why is an algebraic topologist asking me about this?" Hull said. But he realized he’d never actually thought about whether origami might be Turing complete. "I was like, it probably is, but I don’t actually know." So he and Zakharevich set out to prove that you can make a computer out of origami .

First they had to encode computational inputs and outputs — as well as basic logical operations like AND and OR — as folds of paper. If they could then show that their scheme could simulate some other computational model already known to be Turing complete, they would accomplish their goal. A logical operation takes in one or more inputs (each one written as TRUE or FALSE) and spits out an output (TRUE or FALSE) based on a given rule .

To make an operation out of paper, the mathematicians designed a diagram of lines, called a crease pattern, that specifies where to fold the paper. A pleat in the paper represents an input. If you fold along one line in the crease pattern, the pleat flips to one side, indicating an input value of TRUE. But if you fold the paper along a different (nondiagonal) line in the same pattern, the pleat flips to the opposite side (FALSE) .

This transformation lets you convert TRUE inputs into FALSE ones and vice versa, much like with the truth table for an XOR operation.