Jak zbudować komputer origami | Magazyn Quanta

W 1936 roku brytyjski matematyk Alan Turing wpadł na pomysł uniwersalnego komputera. Było to proste urządzenie: nieskończony pasek taśmy pokryty zerami i jedynkami wraz z maszyną, która mogła przesuwać się po taśmie tam i z powrotem, zamieniając zera na jedynki i odwrotnie, zgodnie z pewnymi regułami. Pokazał, że za pomocą takiego urządzenia można wykonać dowolne obliczenia.

Turingowi nie zależało na tym, aby jego pomysł był praktyczny w rozwiązywaniu problemów. Zamiast tego oferował bezcenny sposób na poznanie natury obliczeń i ich ograniczeń. W ciągu dziesięcioleci, które upłynęły od tego nowatorskiego pomysłu, matematycy stworzyli listę jeszcze mniej praktycznych schematów obliczeniowych. Gry takie jak Minesweeper czy Magic: The Gathering mogłyby w zasadzie służyć jako komputery ogólnego przeznaczenia. Podobnie mogłyby działać tak zwane automaty komórkowe, takie jak automat Johna Conwaya Gra życia, zbiór zasad ewolucji czarno-białych kwadratów na dwuwymiarowej siatce.

We wrześniu 2023, Inna Zachariewiczu Uniwersytetu Cornell i Tomasza Hulla z Franklin & Marshall College wykazały, że wszystko, co można obliczyć można obliczyć składając papier. Udowodnili, że origami jest „kompletne według Turinga” – co oznacza, że ​​podobnie jak maszyna Turinga może rozwiązać każdy możliwy do rozwiązania problem obliczeniowy, jeśli ma wystarczająco dużo czasu.

Zacharevich, wieloletni entuzjasta origami, zaczął myśleć o tym problemie w 2021 roku po natknięciu się na film wyjaśniający kompletność Gry w życie według Turinga. „Pomyślałem, że origami jest o wiele bardziej skomplikowane niż Gra w Życie” – powiedział Zakharevich. „Jeśli Gra w życie jest ukończona przez Turinga, origami również powinno być ukończone przez Turinga.”

Ale to nie była jej dziedzina. Chociaż składała origami od najmłodszych lat – „jeśli chcesz mi dać bardzo złożoną rzecz, która wymaga 24-calowej kartki papieru i ma 400 kroków, nie mam już tego dość” – powiedziała – jej badania matematyczne zajmowały się znacznie bardziej abstrakcyjnymi dziedzinami topologii algebraicznej i teorii kategorii. Wysłała więc e-mail do Hulla, który na pełny etat studiował matematykę origami.

„Po prostu niespodziewanie wysłała mi e-mail, a ja zapytałem: dlaczego topolog algebraiczny pyta mnie o to?” powiedział Hull. Ale zdał sobie sprawę, że nigdy tak naprawdę nie zastanawiał się, czy origami może być ukończone według Turinga. „Pomyślałem, że prawdopodobnie tak jest, ale tak naprawdę nie wiem”.

Dlatego on i Zacharewicz postanowili udowodnić, że z origami można zrobić komputer. Najpierw musieli zakodować wejścia i wyjścia obliczeniowe – a także podstawowe operacje logiczne, takie jak AND i OR – w postaci zgięć papieru. Gdyby mogli następnie wykazać, że ich schemat może symulować inny model obliczeniowy, o którym już wiadomo, że jest kompletny w technologii Turinga, osiągnęliby swój cel.

Operacja logiczna pobiera jedno lub więcej danych wejściowych (każde zapisane jako PRAWDA lub FAŁSZ) i wyrzuca wynik (PRAWDA lub FAŁSZ) w oparciu o daną regułę. Aby wykonać operację na papierze, matematycy opracowali diagram linii, zwany wzorem zagnieceń, który określa, gdzie złożyć papier. Zakładka na papierze oznacza wejście. Jeśli złożysz wzdłuż jednej linii we wzorze zagięcia, zakładka przewróci się na jedną stronę, wskazując wartość wejściową PRAWDA. Ale jeśli złożysz papier wzdłuż innej (bliskiej) linii, zakładka przewróci się na przeciwną stronę, co oznacza FAŁSZ.

Dwie z tych zakładek wejściowych tworzą skomplikowany splot fałd zwany gadżetem. Gadżet koduje operację logiczną. Aby wykonać wszystkie te fałdy, a papier nadal składał się na płasko – co jest wymogiem narzuconym przez Hulla i Zacharewicza – dołączyli trzecią zakładkę, która jest zmuszona złożyć się w określony sposób. Jeśli zakładka odwróci się w jedną stronę, oznacza to, że wynik jest PRAWDA. Jeśli odwróci się w drugą stronę, wynik będzie FALSE.

Matematycy zaprojektowali różne gadżety, które przekształcają dane wejściowe w dane wyjściowe zgodnie z różnymi operacjami logicznymi. „Trzeba było dużo bawić się papierem i przesyłać sobie zdjęcia… a potem pisać rygorystyczne dowody na to, że wszystko działa tak, jak twierdziliśmy” – powiedział Hull.

Od końca lat 1990-tych wiadomo, że prościej jednowymiarowy analog Gra w życie Conwaya to Turing. Hull i Zakharevich wymyślili, jak napisać tę wersję Życia w kategoriach operacji logicznych. „Skończyło się na tym, że musieliśmy użyć tylko czterech bramek: AND, OR, NAND i NOR” – powiedział Zacharewicz, odnosząc się do dwóch dodatkowych prostych bramek. Aby jednak połączyć te różne bramki, musieli zbudować nowe gadżety, które pochłaniały obce sygnały i umożliwiały innym sygnałom obracanie się i krzyżowanie bez wzajemnego zakłócania się. „To była najtrudniejsza część” – powiedział Zacharewicz – „zastanawianie się, jak sprawić, by wszystko było odpowiednio ułożone”. Gdy jej i Hullowi udało się dopasować swoje gadżety, mogli zakodować wszystko, czego potrzebowali, w zgięciach papieru, pokazując w ten sposób, że origami jest kompletne.

Komputer origami byłby ogromnie nieefektywny i niepraktyczny. Ale w zasadzie, jeśli masz bardzo dużą kartkę papieru i mnóstwo czasu, możesz użyć origami do obliczenia dowolnej liczby cyfr $latex pi$, ustalenia optymalnego sposobu trasowania każdego dostawcy na świecie lub uruchomić program do przewidywania pogody. „W ostatecznym rozrachunku wzór zagnieceń jest gigantyczny” – powiedział Hull. „Trudno go złożyć, ale spełnia swoje zadanie.”

Przez dziesięciolecia matematyków interesowało origami, ponieważ „wydawało się zabawne i bezużyteczne” – stwierdził Erik Demaine, informatyk z Massachusetts Institute of Technology, który wniósł ogromny wkład w matematykę origami. Ale ostatnio przykuło to również uwagę inżynierów.

Matematykę origami wykorzystano do zaprojektowania ogromnych paneli słonecznych, które można złożyć i przetransportować w przestrzeń kosmiczną, robotów pływających po wodzie w celu gromadzenia danych środowiskowych, stentów przemieszczających się przez maleńkie naczynia krwionośne i nie tylko. „Teraz setki, jeśli nie tysiące ludzi korzysta z matematyki i algorytmów origami, które opracowaliśmy przy projektowaniu nowych konstrukcji mechanicznych” – powiedział Demaine.

Zatem „im częściej będziemy robić takie rzeczy” – stwierdził Hull – „tym większa szansa, że ​​będziemy mieli, moim zdaniem, głębokie powiązania między origami i dobrze ugruntowanymi gałęziami matematyki”.