Hoe je een origami-computer bouwt Quanta-tijdschrift

In 1936 kwam de Britse wiskundige Alan Turing met een idee voor een universele computer. Het was een eenvoudig apparaat: een oneindige strook tape bedekt met nullen en enen, samen met een machine die heen en weer kon bewegen over de tape, waarbij hij nullen in enen veranderde en omgekeerd, volgens een aantal regels. Hij toonde aan dat een dergelijk apparaat voor elke willekeurige berekening kon worden gebruikt.

Het was niet de bedoeling van Turing dat zijn idee praktisch zou zijn voor het oplossen van problemen. Het bood eerder een manier van onschatbare waarde om de aard van berekeningen en de grenzen ervan te verkennen. In de decennia sinds dat baanbrekende idee hebben wiskundigen een lijst van nog minder praktische computersystemen verzameld. Games als Minesweeper of Magic: The Gathering kunnen in principe worden gebruikt als computers voor algemene doeleinden. Dat geldt ook voor zogenaamde cellulaire automaten zoals die van John Conway Spel van het leven, een reeks regels voor het evolueren van zwart-witte vierkanten op een tweedimensionaal raster.

In september 2023, Inna Zakharevich van Cornell Universiteit en Thomas Hul van Franklin & Marshall College heeft aangetoond dat alles berekend kan worden kan worden berekend door papier te vouwen. Ze bewezen dat origami ‘Turing compleet’ is – wat betekent dat het, net als een Turing-machine, elk hanteerbaar computerprobleem kan oplossen, als het maar voldoende tijd krijgt.

Zakharevich, een levenslange origami-liefhebber, begon in 2021 over dit probleem na te denken nadat hij een video tegenkwam die de Turing-volledigheid van het Game of Life uitlegde. “Ik dacht: origami is veel ingewikkelder dan het Spel van het Leven”, zei Zakharevich. “Als het Spel van het Leven Turing compleet is, zou origami ook Turing compleet moeten zijn.”

Maar dit was niet haar vakgebied. Hoewel ze al sinds haar jeugd origami vouwde – “als je me iets supercomplexs wilt geven waarvoor een vel papier van 24 inch nodig is en dat 400 stappen heeft, ben ik daar helemaal mee bezig”, zei ze – haar wiskundig onderzoek hield zich bezig met de veel abstractere gebieden van de algebraïsche topologie en categorietheorie. Dus mailde ze Hull, die fulltime de wiskunde van origami bestudeerde.

"Ze mailde me zomaar uit het niets, en ik dacht: waarom vraagt ​​een algebraïsche topoloog mij hierover?" zei Hul. Maar hij besefte dat hij er eigenlijk nooit over had nagedacht of origami Turing compleet zou kunnen zijn. “Ik dacht: dat is waarschijnlijk zo, maar eigenlijk weet ik het niet.”

Dus wilden hij en Zakharevich bewijzen dat je van origami een computer kunt maken. Eerst moesten ze computerinvoer en -uitvoer – evenals logische basisbewerkingen zoals AND en OR – coderen als papierplooien. Als ze vervolgens zouden kunnen aantonen dat hun schema een ander computermodel zou kunnen simuleren waarvan al bekend is dat het Turing Complete is, zouden ze hun doel bereiken.

Een logische bewerking neemt een of meer invoergegevens op (elk geschreven als WAAR of ONWAAR) en spuugt een uitvoer uit (WAAR of ONWAAR) op basis van een bepaalde regel. Om een ​​bewerking uit papier te maken, ontwierpen de wiskundigen een lijnendiagram, een vouwpatroon genoemd, dat aangeeft waar het papier moet worden gevouwen. Een plooi in het papier vertegenwoordigt een invoer. Als u langs één lijn in het vouwpatroon vouwt, draait de plooi naar één kant, wat de invoerwaarde TRUE aangeeft. Maar als je het papier langs een andere (dichtbij gelegen) lijn vouwt, draait de plooi naar de andere kant, wat FALSE aangeeft.

Twee van deze invoerplooien monden uit in een ingewikkelde reeks plooien die een gadget wordt genoemd. Het gadget codeert de logische bewerking. Om al deze vouwen te maken en toch het papier plat te laten vouwen – een vereiste die Hull en Zakharevich opleggen – hebben ze een derde plooi toegevoegd die gedwongen wordt om op een bepaalde manier te vouwen. Als de plooi één kant op draait, betekent dit dat de uitvoer WAAR is. Als het de andere kant op draait, is de uitvoer FALSE.

De wiskundigen ontwierpen verschillende gadgets die input in output veranderen volgens verschillende logische bewerkingen. “Het was een hoop spelen met papier en het sturen van foto’s naar elkaar … en vervolgens het schrijven van rigoureuze bewijzen dat deze dingen werkten zoals we zeiden dat ze werkten,” zei Hull.

Het is al sinds eind jaren negentig bekend dat het eenvoudiger is eendimensionaal analoog van Conway's Game of Life is Turing voltooid. Hull en Zakharevich ontdekten hoe ze deze versie van Life moesten schrijven in termen van logische bewerkingen. “Uiteindelijk hoefden we maar vier poorten te gebruiken: AND, OR, NAND en NOR,” zei Zakharevich, verwijzend naar twee extra eenvoudige poorten. Maar om deze verschillende poorten te combineren, moesten ze nieuwe gadgets bouwen die signalen van buitenaf absorbeerden en andere signalen lieten draaien en kruisen zonder elkaar te hinderen. ‘Dat was het moeilijkste deel’, zei Zakharevich, ‘uitzoeken hoe je alles goed op één lijn kon krijgen.’ Nadat zij en Hull erin waren geslaagd hun gadgets in elkaar te passen, konden ze alles wat ze nodig hadden in papiervouwen coderen, waarmee ze lieten zien dat origami Turing compleet is.

Een origamicomputer zou enorm inefficiënt en onpraktisch zijn. Maar in principe zou je, als je een heel groot stuk papier had en veel tijd over had, origami kunnen gebruiken om willekeurig veel cijfers van $latex pi$ te berekenen, de optimale route te bepalen voor elke bezorger ter wereld, of voer een programma uit om het weer te voorspellen. "Uiteindelijk is het vouwpatroon gigantisch", zei Hull. "Het is moeilijk op te vouwen, maar het klaart de klus."

Decennia lang voelden wiskundigen zich aangetrokken tot origami omdat ‘het leuk en nutteloos leek’ Erik Demaine, een computerwetenschapper aan het Massachusetts Institute of Technology die uitgebreid heeft bijgedragen aan de wiskunde van origami. Maar de laatste tijd heeft het ook de aandacht getrokken van ingenieurs.

De wiskunde van origami is gebruikt om enorme zonnepanelen te ontwerpen die kunnen worden opgevouwen en de ruimte in kunnen worden getransporteerd, robots die door water zwemmen om omgevingsgegevens te verzamelen, stents die door kleine bloedvaten reizen, en meer. "Nu zijn er honderden, zo niet duizenden mensen die alle origami-wiskunde en algoritmen gebruiken die we hebben ontwikkeld bij het ontwerpen van nieuwe mechanische structuren," zei Demaine.

En dus: “hoe meer we dit soort dingen doen,” zei Hull, “des te groter de kans denk ik dat we diepgaande kruisbestuivingen tot stand zullen brengen tussen origami en gevestigde takken van de wiskunde.”