Як створити комп'ютер орігамі | Журнал Quanta

У 1936 році британський математик Алан Тюрінг виступив з ідеєю створення універсального комп’ютера. Це був простий пристрій: нескінченна смужка стрічки, вкрита нулями та одиницями, разом із машиною, яка могла рухатися вперед-назад по стрічці, змінюючи нулі на одиниці та навпаки відповідно до певного набору правил. Він показав, що такий пристрій можна використовувати для виконання будь-яких обчислень.

Тьюрінг не мав на меті, щоб його ідея була практичною для вирішення проблем. Навпаки, він запропонував безцінний спосіб дослідити природу обчислень та їх межі. За десятиліття, що минули після цієї основоположної ідеї, математики склали список навіть менш практичних обчислювальних схем. Такі ігри, як Minesweeper або Magic: The Gathering, у принципі, можна використовувати як комп’ютери загального призначення. Так звані клітинні автомати, як у Джона Конвея Гра Життя, набір правил для еволюції чорних і білих квадратів на двовимірній сітці.

У вересні 2023, Інна Захаревич Корнельського університету та Томас Халл Коледжу Франкліна й Маршалла показали, що все, що можна обчислити можна обчислити, згорнувши папір. Вони довели, що орігамі є «завершеним за Тьюрингом» — це означає, що, як і машина Тьюринга, воно може вирішити будь-яку розв’язану обчислювальну задачу за достатньо часу.

Захаревич, ентузіаст орігамі протягом усього життя, почав замислюватися над цією проблемою у 2021 році після того, як натрапив на відео, яке пояснювало повноту Тюрінга в «Грі життя». «Мені здавалося, що орігамі набагато складніше, ніж Гра в життя», — сказав Захаревич. «Якщо «Гра в життя» завершена за Тьюрингом, орігамі також має бути завершеним за Тьюрингом».

Але це була не її сфера компетенції. Хоча вона складала орігамі з дитинства — «якщо ви хочете дати мені надскладну річ, для якої потрібен аркуш паперу розміром 24 дюйми і має 400 кроків, я впораюся з нею», — сказала вона — її математичні дослідження стосувалися набагато більш абстрактних сфер алгебраїчної топології та теорії категорій. Тож вона надіслала електронний лист Халлу, який повністю вивчав математику орігамі.

«Вона просто надіслала мені електронний лист зненацька, і я запитав, чому алгебраїчний тополог питає мене про це?» Халл сказав. Але він зрозумів, що ніколи не замислювався над тим, чи може орігамі бути завершеним Тьюрингом. «Я думав, що, мабуть, так, але насправді я не знаю».

Тож вони з Захаревичем взялися довести, що з орігамі можна зробити комп’ютер. Спочатку їм довелося закодувати обчислювальні входи та виходи, а також базові логічні операції, такі як І та АБО, у вигляді складок паперу. Якби вони тоді змогли показати, що їхня схема може симулювати якусь іншу обчислювальну модель, яка вже відома як завершена за Тьюрингом, вони б досягли своєї мети.

Логічна операція приймає один або більше вхідних даних (кожен записується як TRUE або FALSE) і видає вихід (TRUE або FALSE) на основі заданого правила. Щоб виконати операцію з папером, математики розробили діаграму ліній, яка називається візерунком складок, яка вказує, де потрібно згинати папір. Складка на папері означає вхід. Якщо ви згинаєте вздовж однієї лінії візерунка складки, складка повертається вбік, вказуючи на введене значення TRUE. Але якщо ви складете папір уздовж іншої (сусідньої) лінії, складка перевернеться на протилежну сторону, що вказує на FALSE.

Дві з цих вхідних складок входять у складне гарчання складок, що називається гаджетом. Гаджет кодує логічну операцію. Для того, щоб зробити всі ці складки і все одно змусити папір згортатися рівно — вимога, яку висувають Халл і Захаревич — вони включили третю складку, яка змушена складатися певним чином. Якщо складка повертається в один бік, це означає, що результат є ІСТИННИМ. Якщо він перевернеться в іншу сторону, результат буде ЛОЖНИЙ.

Математики розробили різні гаджети, які перетворюють вхідні дані на виходи відповідно до різних логічних операцій. «Було багато бавитися з папером і надсилати зображення один одному... а потім писати суворі докази того, що ці речі працювали так, як ми говорили», — сказав Халл.

З кінця 1990-х років відомо, що простіша одновимірний аналог Гра життя Конвея Тьюрінга завершена. Халл і Захаревич придумали, як написати цю версію Життя з точки зору логічних операцій. «Зрештою, нам знадобилося використовувати лише чотири шлюзи: AND, OR, NAND і NOR», — сказав Захаревич, маючи на увазі два додаткових простих шлюзу. Але щоб поєднати ці різні ворота, їм довелося створити нові пристрої, які поглинали сторонні сигнали та дозволяли іншим сигналам повертатися та перетинатися, не заважаючи один одному. «Це було найважче, — сказав Захаревич, — з’ясувати, як все правильно вибудувати». Після того, як їй і Халлу вдалося зібрати свої гаджети разом, вони змогли закодувати все, що їм було потрібно, у складках паперу, тим самим показавши, що орігамі завершено.

Комп’ютер орігамі був би вкрай неефективним і непрактичним. Але в принципі, якби у вас був дуже великий аркуш паперу та багато часу, ви могли б використати орігамі, щоб обчислити довільну кількість цифр $latex pi$, визначити оптимальний спосіб маршрутизації кожного водія доставки у світі або запустити програму прогнозування погоди. «Зрештою візерунок складок грандіозний», — сказав Халл. «Важко скласти, але це робить роботу».

Десятиліттями математиків приваблювало орігамі, тому що «воно здавалося веселим і марним». Ерік Демайн, вчений з інформатики з Массачусетського технологічного інституту, який зробив великий внесок у математику орігамі. Але нещодавно він також привернув увагу інженерів.

Математика орігамі була використана для розробки масивних сонячних панелей, які можна складати та транспортувати в космос, роботів, які плавають у воді для збору даних про навколишнє середовище, стентів, які подорожують через крихітні кровоносні судини, тощо. «Тепер сотні, якщо не тисячі людей використовують усю математику та алгоритми орігамі, які ми розробили для розробки нових механічних конструкцій», — сказав Демейн.

І тому, «чим більше ми будемо займатися подібними речами, — сказав Халл, — тим більше шансів, на мою думку, у нас буде встановити глибокий перехід між орігамі та добре усталеними розділами математики».