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.
Such an amazing topic. For a moment I was surprised Eric Demaine wasn’t the lead author but of course other people need to discover things every once in a while :)
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.
So… can it run folding@home?
I wonder if this can be done with a hexagonal planar structure, such as graphite?
finally my fortune teller can now compute 64 bit integers !
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.