Turing Complete Origami

A large array of triangles and colored lines showing the folding pattern of the origami computer

Origami can be an interesting starting point for a project, but we weren’t expecting [Thomas C. Hull] and [Inna Zakharevich]’s Turing complete origami computer.

Starting with the constraint of flat origami (the paper folds back on top of itself), the researchers designed a system that could replicate all the functionality of the previously-proven Turing complete Rule 110 automaton. The researchers walk us through the construction of AND, OR, NAND, NOR, and NOT gates via paper as well as the various “wires” and “gadgets” that connect the operators or filter out noise.

Everything ends up a large mess of triangles and hexagons with optional creases to make the whole thing work. While the origami computer probably won’t be helping you slice 3D prints anytime soon, much like a Magic computer, the engineering and math involved may prove useful in other applications.

We’re no strangers to origami here, having covered origami machines, medical robots, or using a desktop vinyl cutter to pre-score your project.

6 thoughts on “Turing Complete Origami

    1. I believe Demaine has done some work (I know he didn’t originate the proof, but I thought he may have extended it?) relating to NP-completeness of flat folding – or at least I was first introduced to these ideas in his class / textbook.

  1. So if you crumple a paper napkin to much you can create an AI that will take over the world if the wind flips it not so randomly? WE ARE DOOMED!
    Origami is fun, but sometimes, at fold 50 out of 100 you cannot find a paper flap to fold because 20 folds before you’ve made a mistake. Nightmare.

Leave a Reply

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.