Hvordan bygge en Origami-datamaskin | Quanta Magazine

I 1936 kom den britiske matematikeren Alan Turing med en idé om en universell datamaskin. Det var en enkel enhet: en uendelig stripe med tape dekket av nuller og enere, sammen med en maskin som kunne bevege seg frem og tilbake langs båndet, endre nuller til enere og omvendt i henhold til et sett med regler. Han viste at en slik enhet kunne brukes til å utføre en hvilken som helst beregning.

Turing hadde ikke til hensikt at ideen hans skulle være praktisk for å løse problemer. Snarere tilbød det en uvurderlig måte å utforske naturen til beregning og dens grenser. I tiårene siden den banebrytende ideen har matematikere samlet en liste over enda mindre praktiske datasystemer. Spill som Minesveiper eller Magic: The Gathering kan i prinsippet brukes som datamaskiner for generell bruk. Det samme kunne såkalte cellulære automater som John Conways Livets lek, et sett med regler for å utvikle svarte og hvite firkanter på et todimensjonalt rutenett.

I september 2023, Inna Zakharevich fra Cornell University og Thomas Hull fra Franklin & Marshall College viste at alt som kan beregnes kan beregnes ved å brette papir. De beviste at origami er "Turing komplett" - noe som betyr at den, som en Turing-maskin, kan løse ethvert håndterbart beregningsproblem, gitt nok tid.

Zakharevich, en livslang origami-entusiast, begynte å tenke på dette problemet i 2021 etter å ha snublet over en video som forklarte Turing-fullstendigheten til Game of Life. "Jeg tenkte at origami er mye mer komplisert enn Game of Life," sa Zakharevich. "Hvis Game of Life er Turing komplett, bør origami også være Turing komplett."

Men dette var ikke hennes ekspertiseområde. Selv om hun hadde brettet origami siden hun var ung - "hvis du vil gi meg en superkompleks ting som krever et 24-tommers ark og har 400 trinn, er jeg over den tingen," sa hun - hennes matematisk forskning omhandlet de mye mer abstrakte rikene av algebraisk topologi og kategoriteori. Så hun sendte en e-post til Hull, som studerte matematikk origami på heltid.

"Hun sendte meg bare en e-post ut av det blå, og jeg tenkte, hvorfor spør en algebraisk topolog meg om dette?" sa Hull. Men han innså at han faktisk aldri hadde tenkt på om origami kunne være Turing komplett. "Jeg trodde, det er det sannsynligvis, men jeg vet faktisk ikke."

Så han og Zakharevitsj forsøkte å bevise at du kan lage en datamaskin av origami. Først måtte de kode datainnganger og -utganger - så vel som grunnleggende logiske operasjoner som OG og ELLER - som papirbrett. Hvis de så kunne vise at ordningen deres kunne simulere en annen beregningsmodell som allerede er kjent for å være Turing-komplett, ville de oppnå målet sitt.

En logisk operasjon tar inn en eller flere innganger (hver skrevet som TRUE eller FALSE) og spytter ut en utgang (TRUE eller FALSE) basert på en gitt regel. For å gjøre en operasjon av papir, designet matematikerne et diagram av linjer, kalt et brettemønster, som spesifiserer hvor papiret skal brettes. Et brett i papiret representerer et innspill. Hvis du bretter langs én linje i brettemønsteret, snur folden til den ene siden, noe som indikerer en inngangsverdi på TRUE. Men hvis du bretter papiret langs en annen (nærliggende) linje, vipper folden over på motsatt side, noe som indikerer FALSE.

To av disse innleggsfoldene strømmer inn i en komplisert snerring av folder som kalles en gadget. Gadgeten koder for den logiske operasjonen. For å lage alle disse brettene og fortsatt få papiret til å brettes flatt – et krav som Hull og Zakharevitsj stiller – inkluderte de en tredje fold som er tvunget til å brette på en spesiell måte. Hvis folden snur én vei, betyr det at utgangen er TRUE. Hvis den snur den andre veien, er utgangen FALSE.

Matematikerne designet forskjellige dingser som gjør innganger til utganger i henhold til ulike logiske operasjoner. "Det var mye å leke med papir og sende bilder til hverandre ... og deretter skrive strenge bevis på at disse tingene fungerte slik vi sa de gjorde," sa Hull.

Det har vært kjent siden slutten av 1990-tallet at en enklere endimensjonal analog av Conways Game of Life er Turing komplett. Hull og Zakharevich fant ut hvordan de skulle skrive denne versjonen av Life når det gjelder logiske operasjoner. "Vi endte opp med å bare trenge å bruke fire porter: AND, OR, NAND og NOR," sa Zakharevich og refererte til ytterligere to enkle porter. Men for å kombinere disse forskjellige portene, måtte de bygge nye dingser som absorberte fremmede signaler og lot andre signaler snu og krysse seg uten å forstyrre hverandre. "Det var den vanskeligste delen," sa Zakharevich, "å finne ut hvordan man kan få alt til å stemme riktig." Etter at hun og Hull klarte å passe sammen dingsene deres, kunne de kode alt de trengte i papirbrett, og dermed vise at origami er Turing komplett.

En origami-datamaskin ville være enormt ineffektiv og upraktisk. Men i prinsippet, hvis du hadde et veldig stort stykke papir og mye tid på hendene, kunne du bruke origami til å beregne vilkårlig mange sifre i $latex pi$, bestemme den optimale måten å rute alle leveringssjåfører i verden på, eller kjøre et program for å forutsi været. "Til slutt er brettemønsteret gigantisk," sa Hull. "Det er vanskelig å kaste seg, men det får jobben gjort."

I flere tiår ble matematikere tiltrukket av origami fordi "det virket morsomt og ubrukelig," sa Erik Demaine, en informatiker ved Massachusetts Institute of Technology som har bidratt mye til matematikken til origami. Men nylig har det også fanget blikket til ingeniører.

Matematikken til origami har blitt brukt til å designe massive solcellepaneler som kan brettes sammen og transporteres ut i verdensrommet, roboter som svømmer gjennom vann for å samle inn miljødata, stenter som beveger seg gjennom små blodårer og mer. "Nå er det hundrevis om ikke tusenvis av mennesker som bruker all origami-matematikken og algoritmene som vi har utviklet i utformingen av nye mekaniske strukturer," sa Demaine.

Og så, "jo mer vi gjør ting som dette," sa Hull, "jo større sjanse tror jeg vi vil ha for å etablere dype kryssinger mellom origami og veletablerte grener av matematikk."