[Перевод] Как собрать компьютер из оригами
Два математика показали, что оригами в принципе можно использовать для выполнения любых возможных вычислений.
В 1936 году британский математик Алан Тьюринг выдвинул идею универсального компьютера. Это было простое устройство: бесконечная полоса ленты, покрытая нулями и единицами, вместе с машиной, которая могла двигаться вперед и назад по ленте, меняя нули на единицы и наоборот в соответствии с некоторым набором правил. Он показал, что такое устройство можно использовать для выполнения любых вычислений.
Тьюринг не ставил своей целью идею, которая была бы практичной в решении проблем. Скорее, он предложил бесценный способ изучения природы вычислений и их пределов. За десятилетия, прошедшие после этой плодотворной идеи, математики накопили список ещё менее практичных вычислительных схем. Такие игры, как Minesweeper или Magic: The Gathering, в принципе можно было бы использовать в качестве компьютеров общего назначения. То же самое могли сделать и так называемые клеточные автоматы, например, Game of Life Джона Конвея — набор правил для эволюции чёрных и белых квадратов на двумерной сетке.
В сентябре 2023 года Инна Захаревич из Корнельского университета и Томас Халл из колледжа Франклина и Маршалла показали, что всё вычислимое можно вычислить, сложив бумагу. (Это уточнение про «всё вычислимое» может показаться излишним, но это не так. Ибо существуют вычислимые и невычислимые функции, причём множество первых счётно, а множество вторых — нет.) Они доказали, что оригами является «полным по Тьюрингу» — это означает, что, как и машина Тьюринга, оно может решить любую решаемую вычислительную задачу, если у вас есть достаточно времени.
Захаревич, увлекающаяся оригами всю жизнь, начала задумываться об этой проблеме в 2021 году после того, как наткнулась на видео, объясняющее тьюринговскую полноту Game of Life. «Я подумала, что оригами намного сложнее, чем Game of Life», — сказала Захаревич. «Если Game of Life полна по Тьюрингу, оригами тоже должно быть полным по Тьюрингу».
Захаревич складывает оригами с юных лет, «если вы хотите подарить мне сверхсложную вещь, для которой требуется 24-дюймовый лист бумаги, и которая состоит из 400 шагов, я справлюсь с этой штукой», — говорит она. Но оригами не было её областью компетенции. Её математические исследования касались гораздо более абстрактных областей алгебраической топологии и теории категорий. Поэтому она отправила электронное письмо Халлу, который постоянно изучал математику оригами.
«Она просто ни с того ни с сего написала мне по электронной почте, и я подумал: почему алгебраический тополог спрашивает меня об этом?» — сказал Халл. Но он понял, что никогда на самом деле не задумывался о том, может ли оригами быть полным по Тьюрингу. «Я подумал, что, возможно, так и есть, но на самом деле я не этого знаю».
Поэтому они с Захаревич задались целью доказать, что из оригами можно сделать компьютер. Сначала им пришлось закодировать вычислительные входные и выходные данные, а также базовые логические операции, такие как «И» и «ИЛИ», в виде складок бумаги. Если бы они затем смогли показать, что их схема может моделировать какую-либо другую вычислительную модель, уже известную как полная по Тьюрингу, они достигли бы своей цели.
Логическая операция принимает одно или несколько входных данных (каждое из которых записано как ИСТИНА или ЛОЖЬ) и выдает выходные данные (ИСТИНА или ЛОЖЬ) на основе заданного правила. Чтобы выполнить операцию с бумагой, математики разработали диаграмму линий, называемую узором сгиба, которая указывает, где складывать бумагу. Складка на бумаге представляет собой вход. Если вы сложите бумагу по одной линии рисунка, складка перевернётся в одну сторону, что указывает на входное значение ИСТИНА. Но если вы сложите бумагу по другой (ближайшей) линии, складка перевернётся на противоположную сторону, указывая на ЛОЖЬ.
Две из этих входных складок образуют сложную систему изгибов, называемую гаджетом. Гаджет кодирует логическую операцию. Чтобы сделать все эти складки и при этом заставить бумагу сгибаться плоско (требование, которое предъявляют Халл и Захаревич), они включили третью складку, которую заставляют сгибаться определённым образом. Если складка перевёрнута в одну сторону, это означает, что результат ИСТИНА. Если она перевёрнута в другую сторону, результат будет ЛОЖЬ.
Математики разработали различные устройства, которые преобразуют входные данные в выходные в соответствии с различными логическими операциями. «Приходилось много играть с бумагой и отправлять друг другу фотографии…, а затем писать строгие доказательства того, что эти вещи работают так, как мы говорили», — сказал Халл.
С конца 1990-х годов было известно, что более простой одномерный аналог Game of Life Конвея является полным по Тьюрингу. Халл и Захаревич придумали, как написать эту версию Game of Life с помощью логических операций. «В итоге нам нужно было использовать только четыре вентиля: И, ИЛИ, НЕ-И и НЕ-ИЛИ», — сказала Захаревич, имея в виду два дополнительных простых вентиля. Но чтобы объединить эти разные вентили, им пришлось построить новые гаджеты которые поглощали посторонние сигналы и позволяли другим сигналам поворачивать и пересекаться, не мешая друг другу. «Это было самое сложное, — сказала Захаревич, — понять, как всё правильно выстроить». После того, как ей и Халлу удалось соединить свои гаджеты вместе, они смогли закодировать всё необходимое в складках бумаги, тем самым показав, что оригами полно по Тьюрингу.
Компьютер из оригами был бы крайне неэффективен и непрактичен. Но в принципе, если бы у вас был очень большой лист бумаги и много свободного времени, вы могли бы с помощью оригами вычислить произвольное количество цифр числа π, определить оптимальный путь каждого водителя в мире или запустить программу, предсказывающую погоду. «В конце концов рисунок складок получается гигантский», — сказал Халл. «Его сложно сложить, но он справляется со своей задачей».
На протяжении десятилетий математиков привлекало оригами, потому что «оно казалось забавным и бесполезным», — говорит Эрик Демейн, учёный из Массачусетского технологического института, внёсший большой вклад в математику оригами. Но недавно оно также привлекло внимание инженеров.
Математика оригами использовалась для создания массивных солнечных панелей, которые можно складывать и транспортировать в космос, роботов, плавающих в воде для сбора данных об окружающей среде, стентов, перемещающихся по крошечным кровеносным сосудам, и многого другого. «Сейчас сотни, если не тысячи людей используют всю разработанную нами математику и алгоритмы оригами при проектировании новых механических конструкций», — сказал Демейн.
Итак, «чем больше мы будем делать подобные вещи, — сказал Халл, — тем больше шансов, я думаю, у нас будет на создание крепких связей между оригами и устоявшимися разделами математики».
Автор перевода @arielf
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
