Kuidas ehitada origami arvutit Quanta ajakiri

1936. aastal tuli Briti matemaatik Alan Turing välja universaalse arvuti ideega. See oli lihtne seade: lõputu nullide ja ühtedega kaetud lindiriba koos masinaga, mis sai mööda linti edasi-tagasi liikuda, muutes mingite reeglite järgi nullid ühtedeks ja vastupidi. Ta näitas, et sellist seadet saab kasutada mis tahes arvutuste tegemiseks.

Turing ei kavatsenud, et tema idee oleks probleemide lahendamisel praktiline. Pigem pakkus see hindamatut viisi arvutamise olemuse ja selle piiride uurimiseks. Aastakümnete jooksul pärast seda põhjapanevat ideed on matemaatikud kogunud nimekirja veelgi vähem praktilistest arvutusskeemidest. Selliseid mänge nagu Minesweeper või Magic: The Gathering saaks põhimõtteliselt kasutada üldotstarbeliste arvutitena. Nii võiksid olla ka nn rakuautomaadid nagu John Conway oma Elu mäng, reeglistik mustade ja valgete ruutude arendamiseks kahemõõtmelisel ruudustikul.

Septembris 2023, Inna Zahharevitš Cornelli ülikoolist ja Thomas Hull Franklini ja Marshalli kolledži uuring näitas, et kõike, mida saab arvutada saab arvutada paberi voltimise teel. Nad tõestasid, et origami on "Turingi lõpetamine" – see tähendab, et sarnaselt Turingi masinaga suudab see piisava aja jooksul lahendada mis tahes jälgitavad arvutusprobleemid.

Eluaegne origami-entusiast Zahharevitš hakkas sellele probleemile mõtlema 2021. aastal pärast seda, kui ta komistas videole, mis selgitas elumängu Turingi täielikkust. "Mulle tundus, et origami on palju keerulisem kui elumäng," ütles Zakharevitš. "Kui elumäng on Turing valmis, peaks ka origami olema Turing täielik."

Kuid see ei olnud tema pädevusvaldkond. Kuigi ta oli noorest peale origami voltinud – "kui soovite mulle kinkida ülikeerulist asja, mis nõuab 24-tollist paberilehte ja millel on 400 astet, siis olen sellest asjast täiesti möödas," ütles ta. matemaatilised uuringud käsitlesid algebralise topoloogia ja kategooriateooria palju abstraktsemaid valdkondi. Nii saatis ta meili Hullile, kes õppis täiskohaga origami matemaatikat.

"Ta saatis mulle lihtsalt ootamatult meili ja ma mõtlesin, miks algebraline topoloog minult selle kohta küsib?" ütles Hull. Kuid ta mõistis, et pole kunagi mõelnud, kas origami võib Turingi lõpetada. "Ma arvasin, et see ilmselt on, aga ma ei tea tegelikult."

Nii asusid ta koos Zahharevitšiga tõestama, et origamist saab arvuti teha. Kõigepealt pidid nad kodeerima arvutuslikud sisendid ja väljundid – samuti põhilised loogilised toimingud, nagu JA ja VÕI – paberivoltidena. Kui nad suudaksid seejärel näidata, et nende skeem võib simuleerida mõnda teist arvutusmudelit, mis on juba teadaolevalt Turingi valmis, saavutaksid nad oma eesmärgi.

Loogikatehe võtab sisse ühe või mitu sisendit (igaüks neist on kirjutatud kui TRUE või FALSE) ja väljutab antud reegli alusel väljundi (TRUE või FALSE). Paberist tehte tegemiseks koostasid matemaatikud joonte diagrammi, mida nimetatakse kortsumustriks, mis määrab, kuhu paber voltida. Volt paberil tähistab sisendit. Kui voldid kortsumustris mööda ühte joont, libiseb volt ühele küljele, mis näitab sisendväärtust TÕENE. Kui aga voldid paberi mööda teist (lähedal asuvat) joont, libiseb volt vastasküljele, mis näitab FALSE.

Kaks neist sisendvoldidest toidavad kokku keerulist voltide mürinat, mida nimetatakse vidinaks. Vidin kodeerib loogilise toimingu. Kõigi nende voltide tegemiseks ja paberi tasaseks voltimiseks – see on Hulli ja Zahharevitši nõue – lisasid nad kolmanda volti, mis on sunnitud teatud viisil voltima. Kui pliss pöördub ühes suunas, tähendab see, et väljund on TRUE. Kui see pöörab teistpidi, on väljund FALSE.

Matemaatikud kavandasid erinevaid vidinaid, mis muudavad sisendid väljunditeks vastavalt erinevatele loogilistele operatsioonidele. "Oli palju paberiga mängimist ja üksteisele piltide saatmist … ja seejärel rangete tõendite kirjutamine selle kohta, et need asjad toimisid nii, nagu me ütlesime," ütles Hull.

Alates 1990. aastate lõpust on teada, et lihtsam ühemõõtmeline analoog Conway elumäng on Turing valmis. Hull ja Zahharevitš mõtlesid välja, kuidas seda Elu versiooni loogiliste operatsioonide mõttes kirjutada. "Lõpuks oli meil vaja kasutada ainult nelja väravat: JA, VÕI, NAND ja NOR," ütles Zakharevitš, viidates kahele täiendavale lihtsale väravale. Kuid nende erinevate väravate kombineerimiseks pidid nad ehitama uusi vidinaid, mis neelasid kõrvalisi signaale ja võimaldasid teistel signaalidel üksteist segamata pöörata ja ristuda. "See oli kõige raskem osa," ütles Zahharevitš, "mõista, kuidas kõik õigesti kokku panna." Pärast seda, kui tema ja Hull suutsid oma vidinad kokku sobitada, said nad kõik vajaliku paberivoltidesse kodeerida, näidates sellega, et origami on Turingi valmis.

Origami arvuti oleks tohutult ebaefektiivne ja ebapraktiline. Kuid põhimõtteliselt, kui teil oli väga suur paberitükk ja teil on palju aega, võite kasutada origamit, et arvutada suvaliselt palju $latex pi$ numbreid, määrata optimaalne viis iga tarnejuhi suunamiseks maailmas või käivitage programm ilma ennustamiseks. "Lõpuks on kortsumuster hiiglaslik," ütles Hull. "Seda on raske voltida, kuid see teeb töö tehtud."

Aastakümneid tõmbas matemaatikuid origami, sest "see tundus lõbus ja kasutu," ütles Erik Demaine, Massachusettsi Tehnoloogiainstituudi arvutiteadlane, kes on palju kaasa aidanud origami matemaatikas. Kuid viimasel ajal on see silma jäänud ka inseneridele.

Origami matemaatikat on kasutatud massiivsete päikesepaneelide, mida saab kokku voltida ja kosmosesse transportida, robotite, mis ujuvad läbi vee keskkonnaandmete kogumiseks, stentide, mis liiguvad läbi tillukeste veresoonte, konstrueerimiseks ja palju muud. "Nüüd kasutavad sajad, kui mitte tuhanded inimesed kogu origami matemaatikat ja algoritme, mille oleme uute mehaaniliste struktuuride kujundamisel välja töötanud," ütles Demaine.

Ja nii, "mida rohkem me selliseid asju teeme," ütles Hull, "seda suurem on minu arvates võimalus luua origami ja väljakujunenud matemaatikaharude vahel sügavaid ristumisi."