1936 hatte der britische Mathematiker Alan Turing die Idee für einen Universalcomputer. Es handelte sich um ein einfaches Gerät: ein unendliches Band, das mit Nullen und Einsen bedeckt ist, zusammen mit einer Maschine, die sich entlang des Bandes hin- und herbewegen kann und nach bestimmten Regeln Nullen in Einsen umwandelt – und umgekehrt. Turing zeigte, dass ein solches Gerät jede beliebige Berechnung durchführen kann.

Er hatte nicht damit gerechnet, dass seine abstrakte Idee zur Lösung praktischer Probleme genutzt würde. Vielmehr sah er die so genannte Turing-Maschine als eine wertvolle Möglichkeit, das Wesen des Rechnens und seine Grenzen zu erforschen. In den Jahrzehnten seit seinem bahnbrechenden Ansatz haben Mathematiker eine ganze Reihe von noch weniger praktischen Rechenverfahren entwickelt. Spiele wie »Minesweeper« oder »Magic: The Gathering« könnten im Prinzip als Allzweckcomputer dienen. Das Gleiche gilt für so genannte zellulare Automaten wie John Conways »Game of Life«. Diese bestehen aus einer Reihe von Regeln, die bestimmen, wie sich schwarze und weiße Quadrate auf einem zweidimensionalen Raster entwickeln.

Und nun haben Inna Zakharevich von der Cornell University und Thomas Hull vom Franklin & Marshall College gezeigt, dass man alles, was sich berechnen lässt, auch durch das Falten von Papier codieren kann. In ihrer im September 2023 erschienenen Arbeit bewiesen sie, dass Origami »Turing-vollständig« ist. Das heißt, dass Origami – mit genügend Zeit – wie eine Turing-Maschine jedes lösbare Rechenproblem lösen kann.

»Ich dachte mir: Origami ist viel komplizierter als Game of Life. Wenn Game of Life Turing-vollständig ist, sollte Origami das auch sein«Inna Zakharevich, Mathematikerin

Zakharevich, die sich schon seit ihrer Kindheit für Origami begeistert, begann 2021 über dieses Problem nachzudenken, nachdem sie über ein Video gestolpert war, in dem »Game of Life« für Turing-vollständig erklärt wurde. »Ich dachte mir: Origami ist viel komplizierter als Game of Life«, sagt Zakharevich. »Wenn Game of Life Turing-vollständig ist, sollte Origami das auch sein.«

Aber das war nicht ihr Fachgebiet. Obwohl sie schon seit ihrer Jugend Origami faltet – »wenn Sie mir ein superkomplexes Ding geben, das ich mit einem Blatt Papier in 400 Schritten bauen kann, bin ich voll dabei«, sagt sie –, hatte sie beruflich einen anderen Schwerpunkt: Ihre mathematische Forschung befasst mit den viel abstrakteren Bereichen der algebraischen Topologie und der Kategorientheorie. Also schickte sie eine E-Mail an Thomas Hull, der sich hauptberuflich mit Origami-Mathematik beschäftigte.

»Sie mailte mir einfach aus heiterem Himmel, und ich wunderte mich: Warum fragt mich eine algebraische Topologin danach?«, erzählt Hull. Aber ihm wurde klar, dass er noch nie darüber nachgedacht hatte, ob Origami Turing-vollständig sein könnte. »Ich dachte: Wahrscheinlich schon, aber ich weiß es nicht genau.«

Also machten er und 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 codieren. 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.

Origami-Papierfalten als Ein- und Ausgabe

Eine logische Operation nimmt eine oder mehrere Eingaben auf (die jeweils als WAHR oder FALSCH geschrieben werden) und gibt einer logischen Operation folgend ein Ergebnis (WAHR oder FALSCH) aus. Um eine Rechenoperation mit Papier durchzuführen, entwarfen die Fachleute ein Liniendiagramm, ein so genanntes Faltenmuster, das angibt, wo das Papier gefaltet werden muss. Eine Falte im Papier stellt eine Eingabe dar. Wenn man entlang einer Linie faltet, befindet sich die Falte anschließend auf einer Seite, die dem Eingabewert von WAHR entspricht. Wenn man das Papier jedoch entlang einer anderen (nahe gelegenen) Linie faltet, klappt die Falte auf die gegenüberliegende Seite, was FALSCH bedeutet.

Zwei dieser Eingangsfalten münden in ein kompliziertes Knäuel von Falten, das »Gadget« genannt wird. Das Gadget codiert die logische Operation. Damit das Papier trotz all dieser Falten flach bleibt – eine Anforderung, die Hull und Zakharevich stellen –, haben sie eine dritte Falte eingebaut, die automatisch auf eine bestimmte Weise fällt. Wenn die Falte in eine Richtung umschlägt, ist die Ausgabe WAHR. Wenn sie in die andere Richtung klappt, ist die Ausgabe FALSCH.

Die Mathematikerin und der Mathematiker entwarfen verschiedene Gadgets, die Eingaben gemäß logischer Operationen in entsprechende Ausgaben umwandeln. »Wir haben viel mit Papier herumgespielt und uns gegenseitig Bilder geschickt«, erinnert sich Hull, »und dann haben wir bewiesen, dass diese Dinge tatsächlich so funktionieren, wie wir es behauptet hatten.«

»Herauszufinden, wie man alles richtig anordnet, war der schwierigste Teil«Inna Zakharevich, Mathematikerin

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. Aber um diese verschiedenen Gatter zu kombinieren, mussten sie neue Gadgets bauen, die Fremdsignale absorbieren und anderen Signalen erlauben, sich zu drehen und zu kreuzen, ohne sich gegenseitig zu stören. »Das war der schwierigste Teil«, sagt Zakharevich, »herauszufinden, wie man alles richtig anordnet.« Nachdem es ihr und Hull gelungen war, ihre Gadgets zusammenzufügen, konnten sie alles, was sie brauchten, in Papierfalten codieren und damit zeigen, dass Origami Turing-vollständig ist.

Ein Origami-Computer wäre natürlich trotzdem ziemlich ineffizient und unpraktisch. Doch im Prinzip könnte man – jedenfalls wenn man ein sehr großes Stück Papier und sehr viel Zeit zur Verfügung hätte – mit Origami beliebig viele Ziffern von π berechnen, den optimalen Weg für jeden Lieferfahrer auf der Welt bestimmen oder ein Programm zur Wettervorhersage ausführen. »Letztendlich ist das Faltmuster gigantisch«, so Hull. »Es ist schwer zu falten, aber es erfüllt seinen Zweck.«

»Jetzt gibt es Hunderte, wenn nicht Tausende von Menschen, die unsere Origami-Algorithmen nutzen, um neue mechanische Strukturen zu entwerfen«Erik Demaine, Informatiker

Jahrzehntelang haben sich vor allem Mathematiker von Origami angezogen gefühlt, »weil es Spaß macht und nutzlos scheint«, sagt Erik Demaine. Der Informatiker am Massachusetts Institute of Technology in Boston hat sich intensiv mit der Mathematik von Origami beschäftigt. Neuerdings interessieren sich allerdings auch Ingenieurinnen und Ingenieure sowie andere Berufsgruppen dafür.

Die Origami-Mathematik wird zum Beispiel genutzt, um riesige Solarpaneele zu entwerfen, die man zusammengefaltet ins All transportieren könnte, oder Roboter, die durch Wasser schwimmen, um Umweltdaten zu sammeln, oder Stents, die sich durch winzige Blutgefäße bewegen, und vieles mehr. »Jetzt gibt es Hunderte, wenn nicht Tausende von Menschen, die unsere Origami-Mathematik und -Algorithmen nutzen, um neue mechanische Strukturen zu entwerfen«, sagt Demaine. Und auch Hull ist optimistisch, dass die Origami-Mathematik die Nische des scheinbar Nutzlosen verlässt: »Je mehr wir solche Dinge tun, desto größer ist die Chance, dass wir Überschneidungen zwischen Origami und etablierten Zweigen der Mathematik herstellen können.«