How to Build an Origami Computer
Kristina Armitage/Quanta Magazine
Introduction
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 (nearby) line, the pleat flips onto its opposite side, indicating FALSE.
Merrill Sherman/Quanta Magazine
Two of these input pleats feed into a complicated snarl of folds called a gadget. The gadget encodes the logical operation. In order to make all these folds and still get the paper to fold flat — a requirement that Hull and Zakharevich impose — they included a third pleat that’s forced to fold in a particular way. If the pleat flips one way, it means the output is TRUE. If it flips the other way, the output is FALSE.
The mathematicians designed different gadgets that turn inputs into outputs according to various logical operations. “It was a lot of playing around with paper and sending pictures to each other … and then writing rigorous proofs that these things worked the way we said they did,” Hull said.
It’s been known since the late 1990s that a simpler one-dimensional analogue of Conway’s Game of Life is Turing complete. Hull and Zakharevich figured out how to write this version of Life in terms of logical operations. “We ended up only needing to use four gates: AND, OR, NAND and NOR,” Zakharevich said, referring to two additional simple gates. But to combine these different gates, they had to build new gadgets that absorbed extraneous signals and allowed other signals to turn and intersect without interfering with each other. “That was the hardest part,” Zakharevich said, “figuring out how to make everything line up properly.” After she and Hull managed to fit their gadgets together, they could encode everything they needed in paper folds, thereby showing that origami is Turing complete.
An origami computer would be massively inefficient and impractical. But in principle, if you had a very large piece of paper and lots of time on your hands, you could use origami to calculate arbitrarily many digits of $latex \pi$, determine the optimal way to route every delivery driver in the world, or run a program to predict the weather. “In the end, the crease pattern is gargantuan,” Hull said. “It’s hard to fold, but it gets the job done.”
For decades, mathematicians were drawn to origami because “it seemed fun and useless,” said Erik Demaine, a computer scientist at the Massachusetts Institute of Technology who has contributed extensively to the mathematics of origami. But recently it has also caught the eye of engineers.
The math of origami has been used to design massive solar panels that can be folded up and transported into space, robots that swim through water to collect environmental data, stents that travel through tiny blood vessels, and more. “Now there’s hundreds if not thousands of people using all the origami math and algorithms that we’ve developed in the design of new mechanical structures,” Demaine said.
And so, “the more we do stuff like this,” Hull said, “the better chance I think we’ll have of establishing deep crossovers between origami and well-established branches of math.”
