Origami-tietokoneen rakentaminen | Quanta-lehti

Vuonna 1936 brittiläinen matemaatikko Alan Turing keksi idean yleistietokoneesta. Se oli yksinkertainen laite: ääretön teippinauha, joka oli peitetty nolilla ja ykkösillä, sekä kone, joka pystyi liikkumaan nauhaa pitkin edestakaisin vaihtaen nollia ykkösiksi ja päinvastoin joidenkin sääntöjen mukaan. Hän osoitti, että tällaista laitetta voidaan käyttää minkä tahansa laskennan suorittamiseen.

Turing ei halunnut, että hänen ideansa olisi käytännöllinen ongelmien ratkaisemiseksi. Pikemminkin se tarjosi korvaamattoman tavan tutkia laskennan luonnetta ja sen rajoja. Tämän tärkeän idean jälkeisten vuosikymmenten aikana matemaatikot ovat keränneet luettelon vieläkin vähemmän käytännöllisistä laskentamenetelmistä. Pelit, kuten Minesweeper tai Magic: The Gathering, voitaisiin periaatteessa käyttää yleiskäyttöisinä tietokoneina. Samoin voisivat olla niin sanotut soluautomaatit, kuten John Conwayn Elämän peli, sääntöjoukko mustien ja valkoisten neliöiden kehittämiseksi kaksiulotteisessa ruudukossa.

Syyskuussa 2023, Inna Zakharevitš Cornellin yliopistosta ja Thomas Hull Franklin & Marshall Collegen tutkimus osoitti, että kaikki voidaan laskea voidaan laskea taittamalla paperia. He osoittivat, että origami on "Turing-valmis" - mikä tarkoittaa, että se voi Turingin koneen tavoin ratkaista minkä tahansa jäljitettävän laskennallisen ongelman riittävän ajan kuluessa.

Zakharevitš, elinikäinen origami-harrastaja, alkoi pohtia tätä ongelmaa vuonna 2021, kun hän törmäsi videoon, joka selitti Game of Lifen Turingin täydellisyyden. "Olin kuin, origami on paljon monimutkaisempi kuin Game of Life", Zakharevitš sanoi. "Jos Game of Life on Turing valmis, myös origamin pitäisi olla Turing täydellinen."

Mutta tämä ei ollut hänen asiantuntemuksensa. Vaikka hän oli taittanut origamia nuoresta asti - "jos haluat antaa minulle erittäin monimutkaisen asian, joka vaatii 24 tuuman paperiarkin ja jossa on 400 askelmaa, olen kaiken sen päällä", hän sanoi. matemaattinen tutkimus käsitteli algebrallisen topologian ja kategoriateorian paljon abstraktimpia ulottuvuuksia. Joten hän lähetti sähköpostia Hullille, joka opiskeli origamin matematiikkaa kokopäiväisesti.

"Hän lähetti minulle sähköpostin yllättäen, ja minä ajattelin, miksi algebrallinen topologi kysyy minulta tätä?" Hull sanoi. Mutta hän tajusi, ettei ollut koskaan ajatellut, voisiko origami olla Turingin valmis. "Olin niin, että se luultavasti on, mutta en oikeastaan ​​tiedä."

Joten hän ja Zakharevitš päättivät todistaa, että voit tehdä tietokoneen origamista. Ensin heidän piti koodata laskennalliset syötteet ja lähdöt – sekä loogiset perustoiminnot, kuten AND ja OR – paperin taitoksi. Jos he sitten voisivat osoittaa, että heidän suunnitelmansa voisi simuloida jotain muuta laskennallista mallia, jonka tiedetään jo olevan Turingin valmis, he saavuttaisivat tavoitteensa.

Looginen operaatio ottaa yhden tai useamman syötteen (jokainen kirjoitetaan TOSI tai EPÄTOSI) ja sylkee ulostulon (TRUE tai FALSE) tietyn säännön perusteella. Tehdäkseen operaatiota paperista matemaatikot suunnittelivat viivojen kaavion, jota kutsutaan taitekuvioksi, joka määrittää, mihin paperi taitetaan. Paperin laskos edustaa syöttöä. Jos taitat yhtä linjaa pitkin laskostuskuviossa, laskos kääntyy toiselle puolelle, mikä osoittaa syöttöarvon TOSI. Mutta jos taitat paperin erilaista (lähellä olevaa) viivaa pitkin, laskos kääntyy vastakkaiselle puolelle, mikä tarkoittaa EPÄTOSI.

Kaksi näistä syöttölaskeksista syötetään monimutkaiseen taitteiden snarin, jota kutsutaan vempaimeksi. Gadget koodaa loogisen toiminnan. Jotta kaikki nämä taitokset saataisiin taitettua tasaiseksi – Hullin ja Zakharevitšin asettama vaatimus – he lisäsivät kolmannen laskoksen, joka on pakko taittaa tietyllä tavalla. Jos laskos kääntyy yhteen suuntaan, se tarkoittaa, että tulos on TRUE. Jos se kääntyy toiseen suuntaan, tulos on FALSE.

Matemaatikot suunnittelivat erilaisia ​​vempaimia, jotka muuttavat tulot ulostuloiksi erilaisten loogisten operaatioiden mukaisesti. "Se oli paljon leikkiä paperilla ja lähettää kuvia toisilleen... ja sitten kirjoittaa tiukkoja todisteita siitä, että nämä asiat toimivat niin kuin sanoimme", Hull sanoi.

1990-luvun lopulta lähtien on tiedetty, että yksinkertaisempi yksiulotteinen analogi Conwayn Game of Life on Turing valmis. Hull ja Zakharevitš keksivät kuinka kirjoittaa tämä Elämän versio loogisten operaatioiden kannalta. "Päädyimme käyttämään vain neljää porttia: AND, OR, NAND ja NOR", Zakharevitš sanoi viitaten kahteen ylimääräiseen yksinkertaiseen porttiin. Mutta yhdistääkseen nämä erilaiset portit, heidän täytyi rakentaa uusia laitteita, jotka absorboivat vieraita signaaleja ja antoivat muiden signaalien kääntyä ja leikkaamaan toisiaan häiritsemättä. "Se oli vaikein osa", Zakharevitš sanoi, "keksiä, kuinka saada kaikki järjestykseen kunnolla." Kun hän ja Hull onnistuivat sovittamaan vempaimet yhteen, he pystyivät koodaamaan kaiken tarvitsemansa paperitaitteisiin, mikä osoitti, että origami on Turingin valmis.

Origami-tietokone olisi erittäin tehoton ja epäkäytännöllinen. Mutta periaatteessa, jos sinulla olisi erittäin suuri paperi ja paljon aikaa käsissäsi, voit käyttää origamia laskeaksesi mielivaltaisesti monta $lateksipi$:n numeroa, määrittääksesi optimaalisen tavan reitittää jokainen jakelukuljettaja maailmassa tai ajaa ohjelman sään ennustamiseksi. "Loppujen lopuksi rypistyskuvio on jättimäinen", Hull sanoi. "Se on vaikea taittaa, mutta se saa työn tehtyä."

Vuosikymmenten ajan matemaatikot olivat kiinnostuneita origamista, koska "se vaikutti hauskalta ja hyödyttömältä", sanoi Erik Demaine, Massachusetts Institute of Technologyn tietojenkäsittelytieteilijä, joka on osallistunut laajasti origamin matematiikkaan. Mutta viime aikoina se on kiinnittänyt myös insinöörien huomion.

Origamin matematiikkaa on käytetty massiivisten aurinkopaneelien suunnittelussa, jotka voidaan taittaa kokoon ja kuljettaa avaruuteen, robotteja, jotka uivat veden läpi keräämään ympäristötietoja, stenttejä, jotka kulkevat pienten verisuonten läpi ja paljon muuta. "Nyt sadat elleivät tuhannet ihmiset käyttävät kaikkea origami-matematiikkaa ja -algoritmeja, joita olemme kehittäneet uusien mekaanisten rakenteiden suunnittelussa", Demaine sanoi.

Ja niin, "mitä enemmän teemme tällaisia ​​asioita", Hull sanoi, "se paremmat mahdollisuudet meillä on mielestäni luoda syvällisiä risteyksiä origamin ja vakiintuneiden matematiikan haarojen välillä."