Berechenbarkeit: Origami ist Turing-vollständig

Alternativer Link @archive.org

Also machten er [Thomas Hull] und [Inna] Zakharevich sich daran zu beweisen, dass man aus Origami einen Computer bauen kann. Zunächst mussten sie die Ein- und Ausgaben von Computern sowie grundlegende logische Operationen wie AND und OR als Papierfalten kodieren. Dann müssten sie nur noch zeigen, dass ihr Schema ein anderes Rechenmodell (von dem bereits bekannt ist, dass es Turing-vollständig ist) simulieren kann.

Seit den späten 1990er Jahren ist bekannt, dass ein einfacheres eindimensionales Analogon von Conways »Game of Life« Turing-vollständig ist. Hull und Zakharevich haben herausgefunden, wie sich diese Version durch logische Operationen ausdrücken lässt und konnten das für ihr Vorhaben nutzen. »Am Ende brauchten wir nur vier Gatter: AND, OR, NAND und NOR«, sagt Zakharevich.

[...] Nachdem es ihr und Hull gelungen war, ihre Gadgets zusammenzufügen, konnten sie alles, was sie brauchten, in Papierfalten kodieren und damit zeigen, dass Origami Turing-vollständig ist.

Origami-Anwendungen:

• Krummes Origami
• Nanomaschinen aus dem Steckbaukasten