Can all calculations be performed using only a piece of white paper?

Although many people regard origami as an interesting but useless trick, in fact, origami has been proven to be "Turing complete"; origami mathematics is gaining widespread applications, such as designing large solar panels that can be folded and transported into space, robots that can swim in water to collect environmental data, stents that can pass through tiny blood vessels, and tools that simulate DNA folding. Hundreds of people are now using origami mathematics and algorithms to design new mechanical structures.

Written by | Jiawei

In 1936, British mathematician Alan Turing came up with the idea of ​​a universal computer. It was a simple device: an infinitely long tape filled with 0s and 1s, and a machine that could move back and forth along the tape, changing 0s to 1s and vice versa according to certain rules. He showed that such a device could be used to perform any calculation.

Turing didn’t intend for the machine in his thought experiment to solve real problems. Instead, it provided a valuable way to explore the nature of computation and its limits. In the decades since this seminal idea, mathematicians have come up with a host of less practical computational schemes. In principle, games like the classic Minesweeper or Magic: The Gathering could be used as general-purpose computers. So too 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.

About the Game of Life and Cellular Automata

In 1970, British mathematician John Horton Conway invented a two-dimensional cellular automaton that can simulate the evolution and complexity of life.

The rules of the Game of Life are very simple, involving only the survival (brightness) and death (darkness) of each pixel, and their interaction with the eight surrounding cells. Specifically, each pixel, which we call a cell, has two states: alive or dead. The state of each cell at the next moment depends on the following four rules:

1. If a cell has fewer than two living cells around it, it will die from loneliness.

2. If a cell is surrounded by two or three surviving cells, it will continue to survive.

3. If a cell has more than three living cells around it, it will die due to crowding.

4. If a dead cell is surrounded by exactly three living cells, it will be revived.

The charm of Conway's Game of Life is that it uses extremely simple rules to produce extremely complex and diverse phenomena. During the game, various cell structures can appear, some of which are stable, some are periodic, some are moving, some are growing, some are interactive, and some are even computable.

Although it is abstract and obscure, this video actually shows the process of searching for prime numbers using the spaceship shape constructed in Conway's Game of Life. In other words, we turned the Game of Life into a generalized computer that can run programs to calculate prime numbers. These spaceships just represent prime numbers. It was invented by Dean Hickerson in 1991. 丨Source: Conway's Game of Life (conwaylife.com)

In September 2023, Inna Zakharevich of Cornell University and Thomas Hull of Franklin & Marshall College proved that anything that can be computed can be computed using origami. They proved that origami is "Turing complete" - meaning that, like a Turing machine, it can solve any computable problem given enough time.

Zakarevich is an origami enthusiast. In 2021, she began to think about this question after she accidentally saw a video explaining the Turing completeness of the "Game of Life". "I thought at the time that origami is much more complicated than the Game of Life." Zakarevich said, "If the Game of Life is Turing complete, then origami should also be Turing complete."

The nature of computing

There is a niche opinion in the scientific community called the broad computational worldview (computationalism in the narrow sense is a kind of epistemology). The most radical advocates, such as Stephen Wolfram (who developed the famous mathematical software Wolfram Mathematica), believe that the entire universe is nothing more than a cellular automaton. Our laws of physics and even matter itself are the result of some kind of calculation. Just like the game of life. And real science is to find the core calculation rules. In the past two years, he even proved that the second law of thermodynamics is the result of a specific calculation rule.

Given the ubiquity of computing, it’s hard to even say he’s wrong.

Common examples of calculations are mathematical equations and computer algorithms. A machine or electronic device (or historically a person) that performs a specific calculation is called a computer (in the narrower sense).

Well-defined means that a mathematical statement or computation can be unambiguously expressed as the initial parameters of a Turing machine. A Turing machine is an abstract computational model that can simulate any computable process. Therefore, any mathematical statement or computation that has the property of being well-defined is called computable, and the statement or computation itself is called a computation. This type of research constitutes the field of computability, which is a subfield of mathematical logic and computer science.

However, computation can also be viewed as a purely physical process that occurs in a closed physical system. Turing's proof in 1937 showed that there is a formal equivalence between computable statements and certain physical systems, which are collectively referred to as (broadly speaking) computers.

So, by folding a piece of paper according to some common rules, can this operation also turn paper into a computer?

Unfortunately, computational science was not Zakarevich’s area of ​​expertise. Although she had loved origami since she was a child—“If you want to give me something super complicated that requires a 24-inch sheet of paper and has 400 steps, I’ll do it myself,” she said—her mathematical research involved more abstract areas such as algebraic topology and category theory. So she emailed Hull, who was fully committed to origami mathematics.

“She emailed me out of the blue, and I was like, why is an algebraic topologist asking me this?” Hull said. But he realized he had never thought about whether origami could be Turing complete. “I thought, maybe, but I wasn’t actually sure.”

So he and Zacharevich set out to prove that origami could be turned into a computer. First, they had to encode computational inputs and outputs, as well as basic logical operations like AND and OR, into paper folds. If they could prove that their scheme could simulate other known Turing-complete computational models, they would have achieved their goal.

About Origami

Origami may be seen by Chinese as a trivial skill that is not worthy of being played by adults. It is fine for preschoolers to play with it, but they usually have no time to play with it when they go to school. However, the Japanese do not think so. They regard origami as a national treasure. Not only do they have an origami association, but they also make origami a compulsory subject in primary schools across the country. The Japanese did not decide to make origami a compulsory subject just because it is a traditional art; flower arrangement and tea ceremony, which are also traditional arts of the country, are not included in compulsory courses.

In the 1970s, Japanese scholar Akira Yoshizawa turned his attention to the mathematics of origami, which later led to a climax of research on the mathematics of origami in Japan. Several research groups were formed and many monographs were published.

These early researchers were pleasantly surprised to realize that origami can even solve equations up to cubic degree, and rational numbers like 1/n can naturally be calculated (expressed). Not only that, origami can solve problems that ruler and compass construction cannot solve: trisecting an angle and doubling the cube (however, it still cannot solve the problem of squaring the circle because π is a transcendental number).

Origami has received considerable mathematical analysis in academic circles to date, with areas of interest ranging from the flat foldability of specific paper models (whether a three-dimensional model can be compressed into a flat surface without breaking) to using origami to solve rational equations.

There is also the famous napkin folding problem: Is it possible to fold a square or rectangular piece of paper into a plane figure so that its perimeter is greater than the original square?

If we cut our folded paper creations, we also have the wonderful folding and cutting theorem : any shape with straight sides can be made from a single (idealized) sheet of paper by folding it flat and cutting it cleanly with a single straight line. These include polygons (which can be concave), shapes with holes, and sets of such shapes (i.e., the regions don't need to be connected).

Computational origami is a new branch of computer science that studies algorithms for solving origami problems. The field of computational origami has come a long way since Robert Lang proposed the TreeMaker algorithm in the 1990s to help accurately fold a base. In origami foldability problems, the goal is to fold something using the creases of an initial configuration. The results of origami design problems are easier to understand than the results of origami foldability problems. Computational origami requires a high level of knowledge in mathematics and computer graphics, and has made great contributions to many fields, such as aerospace materials, rather than just origami crafts.

Whereas these techniques are essentially geometric in nature—giving clear and clever constructions for specific problems—Zakarevic and Hull now want to understand whether they can theoretically implement the abstract functionality of a Turing machine by folding a piece of paper, using some obvious origami rules.

Logical operations take one or more inputs (each written as "true" or "false") and output a value of "true" or "false" according to a given rule. To perform operations "on paper," mathematicians devise a line diagram called a crease pattern that dictates the positions of the folds. The folds in the paper represent the inputs. If you fold along one line in the crease pattern, the fold flips to one side, indicating that the input value is "true." But if you fold the paper along a different (nearby) line, the fold flips to its opposite side, indicating "false."

Creases and wrinkles representing logical truth values ​​| Image source: quantamagazine

Two of the input folds were fed into a complex fold-math compiler gadget. The gadget encodes logical operations. To accomplish all of these folds while still folding the paper flat—a requirement put forward by Hull and Zacharevich—they added a third fold that forced it to fold in a specific way. If the fold flipped one way, the output was “true.” If it flipped the other way, the output was “false.”

The mathematicians designed different gadgets that transformed inputs into outputs based on various logical operations. “We played around with paper for a long time, sending pictures to each other … and then writing rigorous proofs that these things worked the way we said they would,” Hull said.

It has been known since the late 1990s that a simpler one-dimensional analogue of Conway's Game of Life is Turing complete. Hull and Zacharevich figured out how to write this version of the Game of Life using logic operations represented by origami. "We ended up only having to use four gates: AND, OR, NAND and NOR. But to combine these different gates, they had to make new gadgets that absorb extraneous signals and allow other signals to turn around and cross without interfering with each other," Zacharevich said.

That, Zacharevich believes, is the hardest part. Figuring out how to get everything to line up correctly. After she and Hull successfully put their gadget together, they could encode everything they needed in the folds of the paper, showing that origami is Turing complete.

Origami computers are highly inefficient and impractical. But in principle, if we have a large piece of paper and a lot of time, you can use origami to calculate any number of digits of π, determine the best routes for all delivery drivers in the world, or run a program to predict the weather. "Ultimately, the number of folds will be very large," Hull said. "It's physically difficult to do, but in theory it works perfectly." (In the real world, we can hardly fold a piece of paper in half 7 times!)

Useful and useless origami mathematics

Mathematicians have been fascinated by origami for decades. “It seemed both interesting and useless,” said Erik Demaine, a computer scientist at the Massachusetts Institute of Technology.

The landmark paper in computational geometry and computational origami came in 1999, when Eric DeMaine, then a doctoral student at the University of Waterloo, described an algorithm that could determine how to fold a piece of paper into any conceivable three-dimensional shape. But the approach did not yield very practical folding patterns, but was mainly intended to demonstrate theoretical feasibility.

At a computational geometry conference in July 2017, DeMoines and computational geometer Tomohiro Tachi of the University of Tokyo found an algorithm with the fewest seams.

Researchers have created a general algorithm for folding origami shapes that minimizes the number of seams.

Robert Long, a member of the American Mathematical Society, is the most famous researcher of origami mathematics and computer origami. He proved that no matter how complex origami works are, they can be modeled through mathematics. His book Origami Design Secrets is known as the Bible of origami.

But lately, origami has also attracted the attention of engineers.

There are several well-known problems in the field of origami mathematics. For example, the problem of rigid origami, where the fold is regarded as a hinge, and the paper areas on both sides of the fold are two rigid planes connected by hinges. Research in this area has great practical value. For example, the Miura map fold is a rigid fold that has long been used to deploy large solar panel arrays for space satellites.

In the past, satellite antennas were made using a four-fold or eight-fold method. However, this folding method not only requires complicated procedures during operation, but also wastes a lot of space and is easily damaged, requiring frequent repair and maintenance. For this reason, Japanese scholar Miura worked hard to invent a new technology that could solve the above problems. As a result, he found that the pleated structure on the surface of the elliptical cylinder is conducive to saving space and avoiding damage, and has high strength [3]. This ultimately led him to invent a folding method of "pull the two diagonal ends to unfold the object, and push it in the opposite direction when shrinking." 丨Image source: Miura fold - Wikipedia

Origami mathematics has been used to design large solar panels that can be folded and transported into space, robots that can swim in water to collect environmental data, stents that can navigate tiny blood vessels, and tools that simulate DNA folding. "There are hundreds of people now using all the origami mathematics and algorithms that we have developed to design new mechanical structures," DeMaine said.

So “the more we do things like this,” Hull said, “I think the more opportunities we have to create deep intersections between origami and established branches of mathematics.”

Supplementary content

Solving cubic equations with origami

In mathematics, Lill's method is an intuitive way to find the real roots of a univariate polynomial of any power. It was proposed by Austrian engineer Eduard Lill in 1867. Later, researchers in origami geometry realized that this technique was also the core algorithm for origami to solve cubic equations. The following mainly shows how Lill visualized the roots of polynomials and equations. The specific origami process and proof are omitted.

Lear's method is to draw straight line segments at right angles, each of length equal to the coefficient of the polynomial. The roots of a polynomial can be found by the slopes of its right-angled paths, which also connect the start and end points, but the vertices are on the straight lines of the first path.

Use origami to find the roots -1/2, -1/√2 and 1/√2 of the cubic equation 4x3+2x2-2x-1=0 with integer coefficients, with an emphasis on intuitively showing how to handle negative coefficients and extend line segments.

Graphical method for cubic algebraic equations | Image source: Lill's method - Wikipedia

To use this method, start at the origin. Draw a line segment to the right from the size of the first coefficient (the coefficient of the highest power term) (so if the coefficient is negative, the end of the line segment will be to the left of the origin). From the end of the first line segment, draw another line segment up from the size of the second coefficient, then to the left from the size of the third coefficient, then down from the size of the fourth coefficient, and so on. The order of directions (not turns) is always right, up, left, down, and repeat. Therefore, each loop is counterclockwise. This is done for every coefficient of the polynomial (including zero), except for negative coefficients, which are "backwards" - this is the case in our example. The last point you reach, where the line segment corresponding to the constant term of the equation ends, is your endpoint.

Then draw the colored lines in the picture according to certain rules. Take the red line as an example. The right angles of the broken lines it forms are all 90°, and the red line must eventually fall on the end point. If the red line can be determined, the first blue line connected to the origin can be determined by symmetry, and then the end point of the blue line can be found based on the right-angled broken line.

Each number shown on the colored line is the opposite of its slope and is also a real root of the polynomial.

Therefore, the problem is essentially to use the origami method to determine the slope of the red line starting from the origin, so that the red line segment can finally fall on the end point. The specific argument is relatively complicated, and those who are interested can refer to the detailed information in reference [7].

refer to

[1] [2309.07932v1] Flat origami is Turing Complete (arxiv.org)

[2] How to Build an Origami Computer | Quanta Magazine

[3] Mathematics of paper folding - Wikipedia

[4] Origami axiom - Wikipedia

[5] TT's Page (tsg.ne.jp)

[6] Lill's method - Wikipedia

[7] Origami Mathematics - Throw away the tools and you can go further (IV) Lillie's Law - Bilibili (bilibili.com)

[8] Nathaniel Johnston » Generating Sequences of Primes in Conway's Game of Life

This article is supported by the Science Popularization China Starry Sky Project

Produced by: China Association for Science and Technology Department of Science Popularization

Producer: China Science and Technology Press Co., Ltd., Beijing Zhongke Xinghe Culture Media Co., Ltd.

Special Tips

1. Go to the "Featured Column" at the bottom of the menu of the "Fanpu" WeChat public account to read a series of popular science articles on different topics.

2. Fanpu provides a function to search articles by month. Follow the official account and reply with the four-digit year + month, such as "1903", to get the article index for March 2019, and so on.

Copyright statement: Personal forwarding is welcome. Any form of media or organization is not allowed to reprint or excerpt without authorization. For reprint authorization, please contact the backstage of the "Fanpu" WeChat public account.