Cum să construiești un computer origami | Revista Quanta

În 1936, matematicianului britanic Alan Turing a venit cu o idee pentru un computer universal. Era un dispozitiv simplu: o bandă infinită de bandă acoperită cu zerouri și unu, împreună cu o mașină care se putea mișca înainte și înapoi de-a lungul benzii, schimbând zerourile în unu și invers, după un set de reguli. El a arătat că un astfel de dispozitiv ar putea fi folosit pentru a efectua orice calcul.

Turing nu a intenționat ca ideea lui să fie practică pentru rezolvarea problemelor. Mai degrabă, a oferit o modalitate neprețuită de a explora natura calculului și limitele acesteia. În deceniile care au trecut de la acea idee fundamentală, matematicienii au strâns o listă de scheme de calcul și mai puțin practice. Jocuri precum Minesweeper sau Magic: The Gathering ar putea fi, în principiu, folosite ca computere de uz general. La fel ar putea așa-zisele automate celulare, cum ar fi ale lui John Conway Jocul Vieții, un set de reguli pentru evoluția pătratelor alb-negru pe o grilă bidimensională.

În septembrie 2023, Inna Zaharevici de la Universitatea Cornell și Thomas Hull de Franklin & Marshall College a arătat că orice poate fi calculat poate fi calculat prin plierea hârtiei. Ei au demonstrat că origami este „Turing complet” – ceea ce înseamnă că, la fel ca o mașină Turing, poate rezolva orice problemă de calcul rezolvabilă, având suficient timp.

Zakharevich, un pasionat de origami de o viață, a început să se gândească la această problemă în 2021, după ce s-a împiedicat de un videoclip care explica completitatea Turing a Jocului Vieții. „Mi-am spus că origami este mult mai complicat decât Jocul Vieții”, a spus Zakharevich. „Dacă Jocul Vieții este Turing complet, origami ar trebui să fie și Turing complet.”

Dar acesta nu era domeniul ei de expertiză. Deși împăturise origami încă de când era tânără – „dacă vrei să-mi dai un lucru super complex care necesită o foaie de hârtie de 24 de inci și are 400 de pași, am terminat totul”, a spus ea. cercetarea matematică s-a ocupat de tărâmurile mult mai abstracte ale topologiei algebrice și ale teoriei categoriilor. Așa că i-a trimis un e-mail lui Hull, care a studiat matematica origami cu normă întreagă.

„Tocmai mi-a trimis un e-mail din senin și am spus, de ce mă întreabă un topolog algebric despre asta?” spuse Hull. Dar și-a dat seama că nu se gândise niciodată dacă origami ar putea fi complet Turing. „Am fost ca, probabil că este, dar de fapt nu știu.”

Așa că el și Zakharevich și-au propus să demonstreze că poți face un computer din origami. Mai întâi au trebuit să codifice intrările și ieșirile computaționale - precum și operațiuni logice de bază precum AND și SAU - ca pliuri de hârtie. Dacă ar putea apoi să arate că schema lor ar putea simula un alt model de calcul deja cunoscut ca fiind complet Turing, și-ar îndeplini scopul.

O operație logică preia una sau mai multe intrări (fiecare scrisă ca TRUE sau FALSE) și scuipă o ieșire (TRUE sau FALSE) pe baza unei anumite reguli. Pentru a face o operație din hârtie, matematicienii au conceput o diagramă de linii, numită model de cute, care specifică unde să îndoiți hârtia. Un pliu în hârtie reprezintă o intrare. Dacă pliați de-a lungul unei linii în modelul de pliuri, pliul se întoarce într-o parte, indicând o valoare de intrare de TRUE. Dar dacă îndoiți hârtia de-a lungul unei linii diferite (din apropiere), pliul se întoarce pe partea sa opusă, indicând FALS.

Două dintre aceste pliuri de intrare se alimentează într-un mârâit complicat de pliuri numit gadget. Gadgetul codifică operația logică. Pentru a face toate aceste pliuri și a face în continuare hârtia să se plieze plat - o cerință pe care Hull și Zakharevich o impun - au inclus un al treilea pliu care este forțat să se plieze într-un anumit mod. Dacă pliul se întoarce într-un sens, înseamnă că rezultatul este TRUE. Dacă se întoarce invers, rezultatul este FALSE.

Matematicienii au proiectat diferite gadget-uri care transformă intrările în ieșiri conform diferitelor operații logice. „A fost mult să ne jucam cu hârtie și să ne trimitem imagini unul altuia... și apoi să scriem dovezi riguroase că aceste lucruri au funcționat așa cum am spus noi”, a spus Hull.

Se știe încă de la sfârșitul anilor 1990 că este mai simplu analog unidimensional din Conway’s Game of Life este Turing complet. Hull și Zakharevich și-au dat seama cum să scrie această versiune a Vieții în termeni de operațiuni logice. „Am avut nevoie să folosim doar patru porți: AND, OR, NAND și NOR”, a spus Zakharevich, referindu-se la două porți simple suplimentare. Dar pentru a combina aceste porți diferite, au fost nevoiți să construiască noi gadget-uri care absorbeau semnale străine și permit altor semnale să se întoarcă și să se intersecteze fără a interfera unele cu altele. „Asta a fost cea mai grea parte”, a spus Zakharevich, „să-ți dai seama cum să faci totul să se alinieze corect”. După ce ea și Hull au reușit să-și potrivească gadgeturile, au putut codifica tot ce aveau nevoie în pliuri de hârtie, arătând astfel că origami este complet Turing.

Un computer origami ar fi extrem de ineficient și nepractic. Dar, în principiu, dacă ai avea o bucată de hârtie foarte mare și mult timp pe mână, ai putea folosi origami pentru a calcula în mod arbitrar multe cifre de $latex pi$, pentru a determina modalitatea optimă de a direcționa fiecare șofer de livrare din lume sau rulați un program pentru a prezice vremea. „În cele din urmă, modelul cutelor este uriaș”, a spus Hull. „Este greu de pliat, dar face treaba.”

Timp de zeci de ani, matematicienii au fost atrași de origami pentru că „părea distractiv și inutil”, a spus Erik Demaine, un informatician la Institutul de Tehnologie din Massachusetts care a contribuit în mod semnificativ la matematica origami. Dar recent a atras și atenția inginerilor.

Matematica origami a fost folosită pentru a proiecta panouri solare masive care pot fi pliate și transportate în spațiu, roboți care înoată prin apă pentru a colecta date de mediu, stenturi care călătoresc prin vase de sânge mici și multe altele. „Acum sunt sute, dacă nu mii de oameni care folosesc toate matematica origami și algoritmii pe care i-am dezvoltat în proiectarea de noi structuri mecanice”, a spus Demaine.

Și așadar, „cu cât facem mai multe astfel de lucruri”, a spus Hull, „cu atât cred că vom avea șanse mai mari de a stabili încrucișări profunde între origami și ramuri bine stabilite ale matematicii”.