So bauen Sie einen Origami-Computer | Quanta-Magazin

1936 hatte der britische Mathematiker Alan Turing die Idee für einen Universalcomputer. Es war ein einfaches Gerät: ein endloser Bandstreifen, der mit Nullen und Einsen bedeckt war, zusammen mit einer Maschine, die sich entlang des Bandes hin und her bewegen konnte und nach bestimmten Regeln Nullen in Einsen und umgekehrt umwandelte. Er zeigte, dass mit einem solchen Gerät beliebige Berechnungen durchgeführt werden können.

Turing hatte nicht die Absicht, dass seine Idee zur Lösung von Problemen praktisch sein sollte. Vielmehr bot es eine unschätzbare Möglichkeit, die Natur der Berechnung und ihre Grenzen zu erkunden. In den Jahrzehnten seit dieser bahnbrechenden Idee haben Mathematiker eine Liste noch weniger praktischer Rechenverfahren zusammengestellt. Spiele wie Minesweeper oder Magic: The Gathering könnten grundsätzlich als Allzweckcomputer eingesetzt werden. Das könnten auch sogenannte zellulare Automaten wie der von John Conway sein Spiel des Lebens, eine Reihe von Regeln für die Entwicklung schwarzer und weißer Quadrate auf einem zweidimensionalen Gitter.

Im September 2023, Inna Sacharevich der Cornell University und Thomas Rumpf vom Franklin & Marshall College zeigte, dass alles berechnet werden kann kann durch Falten von Papier berechnet werden. Sie bewiesen, dass Origami „Turing-vollständig“ ist – was bedeutet, dass es wie eine Turing-Maschine jedes handhabbare Rechenproblem lösen kann, wenn genügend Zeit zur Verfügung steht.

Zakharevich, ein lebenslanger Origami-Enthusiast, begann 2021 über dieses Problem nachzudenken, nachdem er auf ein Video gestoßen war, das die Turing-Vollständigkeit des Spiels des Lebens erklärte. „Ich dachte, Origami ist viel komplizierter als das Spiel des Lebens“, sagte Sacharewitsch. „Wenn das Spiel des Lebens Turing vollständig ist, sollte Origami auch Turing vollständig sein.“

Aber das war nicht ihr Fachgebiet. Obwohl sie seit ihrer Jugend Origami faltet – „Wenn Sie mir ein superkomplexes Ding geben wollen, das ein 24-Zoll-Blatt Papier erfordert und 400 Schritte hat, bin ich ganz begeistert von dem Ding“, sagte sie – sie Die mathematische Forschung befasste sich mit den viel abstrakteren Bereichen der algebraischen Topologie und der Kategorientheorie. Also schickte sie eine E-Mail an Hull, der sich ganztägig mit Origami-Mathematik beschäftigte.

„Sie hat mir einfach aus heiterem Himmel eine E-Mail geschickt und ich fragte mich: Warum fragt mich ein algebraischer Topologe danach?“ Hull sagte. Aber ihm wurde klar, dass er nie wirklich darüber nachgedacht hatte, ob Origami Turings Vollständigkeit sein könnte. „Ich dachte, das ist es wahrscheinlich, aber ich weiß es eigentlich nicht.“

Also machten er und Zakharevich sich daran, zu beweisen, dass man aus Origami einen Computer bauen kann. Zuerst mussten sie rechnerische Eingaben und Ausgaben sowie grundlegende logische Operationen wie UND und ODER als Papierfalten kodieren. Wenn sie dann zeigen könnten, dass ihr Schema ein anderes Rechenmodell simulieren könnte, von dem bereits bekannt ist, dass es Turing-vollständig ist, würden sie ihr Ziel erreichen.

Eine logische Operation nimmt eine oder mehrere Eingaben auf (jede wird als WAHR oder FALSCH geschrieben) und gibt basierend auf einer bestimmten Regel eine Ausgabe (WAHR oder FALSCH) aus. Um eine Operation aus Papier durchzuführen, entwarfen die Mathematiker ein Liniendiagramm, ein sogenanntes Faltmuster, das angibt, wo das Papier gefaltet werden soll. Eine Falte im Papier stellt eine Eingabe dar. Wenn Sie entlang einer Linie im Faltenmuster falten, dreht sich die Falte auf eine Seite, was einen Eingabewert von TRUE anzeigt. Wenn Sie das Papier jedoch entlang einer anderen (nahe gelegenen) Linie falten, dreht sich die Falte auf die gegenüberliegende Seite, was FALSCH anzeigt.

Zwei dieser Eingangsfalten münden in ein kompliziertes Faltengeflecht, das als Gadget bezeichnet wird. Das Gadget kodiert die logische Operation. Um all diese Falten zu machen und das Papier trotzdem flach falten zu können – eine Anforderung, die Hull und Zakharevich stellen – haben sie eine dritte Falte eingebaut, die dazu gezwungen wird, sich auf eine bestimmte Art und Weise zu falten. Wenn sich die Falte in eine Richtung dreht, bedeutet dies, dass die Ausgabe WAHR ist. Wenn es in die andere Richtung umgedreht wird, ist die Ausgabe FALSE.

Die Mathematiker entwarfen verschiedene Geräte, die Eingaben anhand verschiedener logischer Operationen in Ausgaben umwandeln. „Wir haben viel mit Papier herumgespielt und uns gegenseitig Bilder geschickt … und dann strenge Beweise dafür geschrieben, dass diese Dinge so funktionierten, wie wir es versprochen hatten“, sagte Hull.

Seit Ende der 1990er Jahre ist bekannt, dass eine einfachere eindimensionales Analogon von Conways Spiel des Lebens ist Turing abgeschlossen. Hull und Zakharevich haben herausgefunden, wie man diese Version von Life anhand logischer Operationen schreibt. „Am Ende mussten wir nur vier Gatter verwenden: UND, ODER, NAND und NOR“, sagte Zakharevich und bezog sich dabei auf zwei weitere einfache Gatter. Um diese verschiedenen Tore zu kombinieren, mussten sie jedoch neue Geräte bauen, die Fremdsignale absorbieren und es anderen Signalen ermöglichen, sich zu drehen und zu kreuzen, ohne sich gegenseitig zu stören. „Das war der schwierigste Teil“, sagte Zakharevich, „herauszufinden, wie man alles richtig in Einklang bringt.“ Nachdem es ihr und Hull gelungen war, ihre Geräte zusammenzubauen, konnten sie alles, was sie brauchten, in Papierfalten kodieren und so zeigen, dass Origami Turing vollständig ist.

Ein Origami-Computer wäre äußerst ineffizient und unpraktisch. Aber im Prinzip, wenn Sie ein sehr großes Blatt Papier und viel Zeit zur Verfügung hätten, könnten Sie Origami verwenden, um beliebig viele Ziffern von $latex pi$ zu berechnen, den optimalen Weg zu bestimmen, um jeden Lieferfahrer auf der Welt zu routen, oder Führen Sie ein Programm aus, um das Wetter vorherzusagen. „Letztendlich ist das Faltenmuster gigantisch“, sagte Hull. „Es ist schwer zu falten, aber es erfüllt seinen Zweck.“

Jahrzehntelang fühlten sich Mathematiker zu Origami hingezogen, weil „es lustig und nutzlos erschien“, sagte er Erik Demaine, ein Informatiker am Massachusetts Institute of Technology, der viel zur Mathematik des Origami beigetragen hat. Aber neuerdings ist es auch bei Ingenieuren aufgefallen.

Mithilfe der Origami-Mathematik wurden riesige Sonnenkollektoren entworfen, die zusammengeklappt und in den Weltraum transportiert werden können, Roboter, die durch Wasser schwimmen, um Umweltdaten zu sammeln, Stents, die durch winzige Blutgefäße wandern, und vieles mehr. „Heute nutzen Hunderte, wenn nicht Tausende von Menschen die gesamte Origami-Mathematik und die Algorithmen, die wir für die Konstruktion neuer mechanischer Strukturen entwickelt haben“, sagte Demaine.

Und so: „Je mehr wir solche Dinge tun“, sagte Hull, „desto größer sind meines Erachtens die Chancen, tiefe Überschneidungen zwischen Origami und etablierten Zweigen der Mathematik herzustellen.“