Hvordan man bygger en Origami-computer | Quanta Magasinet

I 1936 fik den britiske matematiker Alan Turing en idé til en universel computer. Det var en simpel enhed: en uendelig strimmel tape dækket af nuller og ettaller sammen med en maskine, der kunne bevæge sig frem og tilbage langs båndet, ændre nuller til etaller og omvendt i henhold til et sæt regler. Han viste, at en sådan enhed kunne bruges til at udføre enhver beregning.

Turing havde ikke til hensigt, at hans idé skulle være praktisk til at løse problemer. Det tilbød snarere en uvurderlig måde at udforske beregningernes natur og dens grænser. I årtierne siden den banebrydende idé har matematikere samlet en liste over endnu mindre praktiske computersystemer. Spil som Minesweeper eller Magic: The Gathering kunne i princippet bruges som almindelige computere. Det samme kunne såkaldte cellulære automater som John Conways Livets spil, et sæt regler for udvikling af sorte og hvide firkanter på et todimensionelt gitter.

I september 2023, Inna Zakharevich fra Cornell University og Thomas Hull fra Franklin & Marshall College viste, at alt, der kan beregnes kan beregnes ved at folde papir. De beviste, at origami er "Turing komplet" - hvilket betyder, at den ligesom en Turing-maskine kan løse ethvert håndterbart beregningsproblem, givet nok tid.

Zakharevich, en livslang origami-entusiast, begyndte at tænke på dette problem i 2021 efter at have snublet over en video, der forklarede Turing-fuldstændigheden af ​​Game of Life. "Jeg var ligesom, origami er meget mere kompliceret end Game of Life," sagde Zakharevich. "Hvis Game of Life er Turing komplet, burde origami også være Turing komplet."

Men dette var ikke hendes ekspertiseområde. Selvom hun havde foldet origami siden hun var ung - "hvis du vil give mig en super kompleks ting, der kræver et 24-tommers ark papir og har 400 trin, er jeg over den ting," sagde hun - hendes matematisk forskning beskæftigede sig med de meget mere abstrakte områder af algebraisk topologi og kategoriteori. Så hun sendte en e-mail til Hull, som studerede matematik i origami på fuld tid.

"Hun sendte mig lige en e-mail ud af det blå, og jeg tænkte, hvorfor spørger en algebraisk topolog mig om dette?" sagde Hull. Men han indså, at han faktisk aldrig havde tænkt på, om origami kunne være Turing komplet. "Jeg var ligesom, det er det nok, men jeg ved det faktisk ikke."

Så han og Zakharevich satte sig for at bevise, at man kan lave en computer af origami. Først skulle de indkode beregningsmæssige input og output - såvel som grundlæggende logiske operationer som AND og OR - som folder af papir. Hvis de så kunne vise, at deres skema kunne simulere en anden beregningsmodel, der allerede er kendt for at være Turing komplet, ville de nå deres mål.

En logisk operation tager en eller flere input ind (hver skrevet som SAND eller FALSK) og spytter et output (SAND eller FALSK) ud baseret på en given regel. For at lave en operation ud af papir, designede matematikerne et diagram af linjer, kaldet et foldemønster, der specificerer, hvor papiret skal foldes. Et læg i papiret repræsenterer et input. Hvis du folder langs én linje i foldemønsteret, vendes foldet til den ene side, hvilket indikerer en inputværdi på TRUE. Men hvis du folder papiret langs en anden (nærliggende) linje, vendes foldet om på dens modsatte side, hvilket indikerer FALSK.

To af disse inputfolder føres ind i en kompliceret snerren af ​​folder kaldet en gadget. Gadget'en koder den logiske operation. For at lave alle disse folder og stadig få papiret til at folde fladt – et krav, som Hull og Zakharevitj stiller – inkluderede de et tredje læg, der er tvunget til at folde på en bestemt måde. Hvis foldet vender én vej, betyder det, at outputtet er SAND. Hvis det vender den anden vej, er outputtet FALSK.

Matematikerne designede forskellige gadgets, der omdanner input til output ifølge forskellige logiske operationer. "Det var en masse at lege med papir og sende billeder til hinanden ... og derefter skrive strenge beviser på, at disse ting fungerede, som vi sagde, de gjorde," sagde Hull.

Det har været kendt siden slutningen af ​​1990'erne, at en enklere en-dimensionel analog af Conways Game of Life er Turing færdig. Hull og Zakharevich fandt ud af, hvordan man skriver denne version af Life i form af logiske operationer. "Vi endte med kun at behøve at bruge fire porte: AND, OR, NAND og NOR," sagde Zakharevich med henvisning til to yderligere simple porte. Men for at kombinere disse forskellige porte, var de nødt til at bygge nye gadgets, der absorberede fremmede signaler og tillod andre signaler at dreje og krydse uden at forstyrre hinanden. "Det var den sværeste del," sagde Zakharevich, "at finde ud af, hvordan man får alting til at passe ordentligt." Efter at det lykkedes hende og Hull at passe deres gadgets sammen, kunne de kode alt, hvad de havde brug for, i papirfolder og derved vise, at origami er Turing komplet.

En origami-computer ville være enormt ineffektiv og upraktisk. Men i princippet, hvis du havde et meget stort stykke papir og masser af tid på dine hænder, kunne du bruge origami til at beregne vilkårligt mange cifre af $latex pi$, bestemme den optimale måde at dirigere enhver leveringschauffør i verden på, eller køre et program for at forudsige vejret. "I sidste ende er foldermønsteret gigantisk," sagde Hull. "Det er svært at folde, men det får jobbet gjort."

I årtier blev matematikere tiltrukket af origami, fordi "det virkede sjovt og ubrugeligt," sagde Erik Demaine, en datalog ved Massachusetts Institute of Technology, der har bidraget meget til matematikken i origami. Men på det seneste har det også fået øjnene op for ingeniører.

Matematikken om origami er blevet brugt til at designe massive solpaneler, der kan foldes sammen og transporteres ud i rummet, robotter, der svømmer gennem vand for at indsamle miljødata, stenter, der rejser gennem små blodkar og meget mere. "Nu er der hundredvis, hvis ikke tusindvis af mennesker, der bruger al den origami-matematik og algoritmer, som vi har udviklet i designet af nye mekaniske strukturer," sagde Demaine.

Og så, "jo mere vi laver sådan noget," sagde Hull, "jo bedre chance tror jeg, vi har for at etablere dybe krydsninger mellem origami og veletablerede grene af matematik."