Hur man bygger en Origami-dator | Quanta Magazine

1936 kom den brittiske matematikern Alan Turing på en idé om en universell dator. Det var en enkel anordning: en oändlig remsa av tejp täckt av nollor och ettor, tillsammans med en maskin som kunde röra sig fram och tillbaka längs bandet, ändra nollor till ettor och vice versa enligt någon uppsättning regler. Han visade att en sådan enhet kunde användas för att utföra vilken beräkning som helst.

Turing hade inte för avsikt att hans idé skulle vara praktisk för att lösa problem. Snarare erbjöd det ett ovärderligt sätt att utforska beräkningens natur och dess gränser. Under decennierna sedan den framstående idén har matematiker samlat ihop en lista med ännu mindre praktiska datorsystem. Spel som Minesweeper eller Magic: The Gathering skulle i princip kunna användas som allmänna datorer. Så kunde så kallade cellulära automater som John Conways Livets spel, en uppsättning regler för att utveckla svarta och vita rutor på ett tvådimensionellt rutnät.

I september 2023, Inna Zakharevich vid Cornell University och Thomas Hull från Franklin & Marshall College visade att allt som kan beräknas kan beräknas genom att vika papper. De bevisade att origami är "turing komplett" - vilket betyder att den, precis som en Turing-maskin, kan lösa alla lösbara beräkningsproblem, givet tillräckligt med tid.

Zakharevich, en livslång origami-entusiast, började tänka på detta problem 2021 efter att ha snubblat på en video som förklarade Turing-fullständigheten i Game of Life. "Jag trodde att origami är mycket mer komplicerat än Game of Life," sa Zakharevitj. "Om Game of Life är Turing komplett, borde origami också vara Turing komplett."

Men det här var inte hennes expertområde. Även om hon hade vikat origami sedan hon var ung - "om du vill ge mig en superkomplicerad sak som kräver ett 24-tums pappersark och har 400 steg, är jag över den saken", sa hon - hennes matematisk forskning behandlade de mycket mer abstrakta områdena av algebraisk topologi och kategoriteori. Så hon mailade Hull, som studerade origami på heltid.

"Hon mailade mig precis direkt, och jag tänkte, varför frågar en algebraisk topolog mig om detta?" sa Hull. Men han insåg att han faktiskt aldrig hade tänkt på om origami kunde vara Turing komplett. "Jag trodde att det förmodligen är det, men jag vet faktiskt inte."

Så han och Zakharevitj gav sig i kast med att bevisa att man kan göra en dator av origami. Först var de tvungna att koda beräkningsingångar och -utgångar - såväl som grundläggande logiska operationer som OCH och ELLER - som pappersveck. Om de sedan kunde visa att deras schema kunde simulera någon annan beräkningsmodell som redan är känd för att vara Turing komplett, skulle de uppnå sitt mål.

En logisk operation tar in en eller flera ingångar (var och en skrivs som TRUE eller FALSE) och spottar ut en output (TRUE eller FALSE) baserat på en given regel. För att göra en operation av papper designade matematikerna ett diagram med linjer, kallat ett veckmönster, som anger var papperet ska vikas. Ett veck i papperet representerar en ingång. Om du viker längs en linje i veckmönstret, vänds vecket åt sidan, vilket indikerar ett inmatningsvärde på TRUE. Men om du viker papperet längs en annan (nära) linje, vänds vecket på motsatt sida, vilket indikerar FALSK.

Två av dessa ingångsveck matas in i en komplicerad snurr av veck som kallas en gadget. Gadgeten kodar den logiska operationen. För att göra alla dessa veck och ändå få papperet att vikas platt – ett krav som Hull och Zakharevitj ställer – inkluderade de en tredje veck som tvingas vika på ett speciellt sätt. Om vecket vänder åt ett håll betyder det att utmatningen är TRUE. Om den vänder åt andra hållet är utdata FALSE.

Matematikerna designade olika prylar som gör ingångar till utgångar enligt olika logiska operationer. "Det var mycket att leka med papper och skicka bilder till varandra ... och sedan skriva rigorösa bevis på att dessa saker fungerade som vi sa att de gjorde," sa Hull.

Det har varit känt sedan slutet av 1990-talet att en enklare endimensionell analog av Conways Game of Life är Turing komplett. Hull och Zakharevich kom på hur man skriver den här versionen av Life när det gäller logiska operationer. "Det slutade med att vi bara behövde använda fyra grindar: AND, OR, NAND och NOR," sa Zakharevich och hänvisade till ytterligare två enkla grindar. Men för att kombinera dessa olika portar var de tvungna att bygga nya prylar som absorberade främmande signaler och lät andra signaler svänga och skära sig utan att störa varandra. "Det var den svåraste delen," sa Zakharevitj, "att ta reda på hur man får allt att ställa upp på rätt sätt." Efter att hon och Hull lyckades passa ihop sina prylar kunde de koda allt de behövde i pappersveck, och därigenom visa att origami är Turing komplett.

En origami-dator skulle vara oerhört ineffektiv och opraktisk. Men i princip, om du hade en mycket stor bit papper och mycket tid på dina händer, skulle du kunna använda origami för att beräkna godtyckligt många siffror av $latex pi$, bestämma det optimala sättet att dirigera alla leveransförare i världen, eller köra ett program för att förutsäga vädret. "I slutändan är veckmönstret gigantiskt," sa Hull. "Det är svårt att vika ihop, men det blir jobbet gjort."

I decennier drogs matematiker till origami eftersom "det verkade roligt och värdelöst", sa de Erik Demaine, en datavetare vid Massachusetts Institute of Technology som har bidragit mycket till matematiken i origami. Men på senare tid har det också fångat ingenjörernas blick.

Matematiken för origami har använts för att designa massiva solpaneler som kan vikas upp och transporteras ut i rymden, robotar som simmar genom vatten för att samla in miljödata, stentar som går genom små blodkärl och mer. "Nu finns det hundratals om inte tusentals människor som använder all origami matematik och algoritmer som vi har utvecklat i utformningen av nya mekaniska strukturer," sa Demaine.

Och så, "ju mer vi gör sånt här," sa Hull, "desto större chans tror jag att vi kommer att ha djupa korsningar mellan origami och väletablerade grenar av matematik."