BROADCASTS.com

Logic gates and origami? Professor Inna Zakharevich joined us to talk about Turing complete origami crease patterns.\xa0

We started talking about Turing completeness which led to a Conway\u2019s Game of Life-like 2D cellular automaton called Rule 110 (Wikipedia) which can be implemented with logic gates (AND, OR, NOT). These logic gates can be implemented as creases in paper (with the direction of the crease indicating 0 or 1).\xa0

The paper describing the proof is called Flat Origami is Turing Complete (arxiv and PDF). Quanta Magazine has a summary article: How to Build an Origami Computer.

Inna\u2019s page at Cornell University also has the crease patterns for the logic gates (pdf).

Inna is an aficionado of the origami work by Satoshi Kamiya who creates complex and lifelike patterns.\xa0

Some other origami mentioned:

• Origami Stegosaurus by John Montroll YouTube Folding video (Part 1 of 3)

• Ilan Garibi\u2019s Pineapple Tessellation (PDF instructions)

• Eric Gjerde Spread Hex Origami Tessellation (This also has the equilateral triangle grid needed to fold Inna\u2019s gate logic)

• Peter Engel

• Amanda Ghassaei\u2019s Origami Simulator (Mooser\u2019s is under Examples->Origami)

Some other math mentioned:

• Veritasium\u2019s Math's Fundamental Flaw talks about Goerthe\u2019s Incompleteness Theorem

• Physical Logic Game: Turing Tumble - Build Marble-Powered Computers

• Mathematics of Paper Folding (Wikipedia)

Transcript