Как сделать оригами-компьютер

Два математика показали, что оригами, в принципе, можно использовать для выполнения любых возможных вычислений. Сохранить статью Прочитать позже

Введение

В 1936 году британский математик Алан Тьюринг предложил идею универсального компьютера. Это было простое устройство: бесконечная лента, покрытая нулями и единицами, и машина, которая могла двигаться вперёд и назад по ленте, заменяя нули единицами и наоборот по определённому набору правил. Он показал, что такое устройство можно использовать для выполнения любых вычислений.

Тьюринг не стремился к практическому решению задач. Напротив, эта идея предлагала бесценный способ исследования природы вычислений и их пределов. За десятилетия, прошедшие с момента появления этой основополагающей идеи, математики накопили целый список ещё менее практичных вычислительных схем. Игры, такие как «Сапер» или «Magic: The Gathering», в принципе, могут использоваться в качестве компьютеров общего назначения. То же самое можно сказать и о так называемых клеточных автоматах, таких как «Игра жизни» Джона Конвея, представляющая собой набор правил для построения чёрных и белых квадратов на двумерной сетке.

В сентябре 2023 года Инна Захаревич из Корнеллского университета и Томас Халл из Колледжа Франклина и Маршалла продемонстрировали, что всё, что можно вычислить, можно вычислить, складывая бумагу. Они доказали, что оригами «полно по Тьюрингу», то есть, подобно машине Тьюринга, оно может решить любую разрешимую вычислительную задачу, если дать ему достаточно времени.

Захаревич, всю жизнь увлеченный оригами, начал размышлять над этой проблемой в 2021 году, наткнувшись на видео, объясняющее полноту по Тьюрингу Игры Жизни. «Я подумал, что оригами гораздо сложнее Игры Жизни», — сказал Захаревич. «Если Игра Жизни полна по Тьюрингу, то и оригами тоже должно быть полнотой по Тьюрингу».

Но это не было её областью знаний. Хотя она с юности занималась складыванием оригами — «Если вы хотите дать мне суперсложную конструкцию, требующую листа бумаги шириной 60 см и состоящую из 400 шагов, я с этим справлюсь», — говорила она, — её математические исследования касались гораздо более абстрактных областей алгебраической топологии и теории категорий. Поэтому она написала Халлу, который изучал математику оригами на постоянной основе.

«Она просто ни с того ни с сего написала мне, и я подумал: «Почему алгебраический тополог спрашивает меня об этом?» — сказал Халл. Но тут же понял, что никогда на самом деле не задумывался о том, может ли оригами быть полным по Тьюрингу. «Я подумал: «Возможно, так и есть, но я точно не знаю».

Поэтому они с Захаревичем решили доказать, что из оригами можно сделать компьютер. Сначала им нужно было закодировать входные и выходные вычислительные данные, а также базовые логические операции, такие как И и ИЛИ, в виде сгибов бумаги. Если бы им удалось показать, что их схема может имитировать какую-либо другую вычислительную модель, уже известную как полная по Тьюрингу, они бы достигли своей цели.

Логическая операция принимает один или несколько входных данных (каждый из которых записывается как ИСТИНА или ЛОЖЬ) и выдаёт выходной сигнал (ИСТИНА или ЛОЖЬ) в соответствии с заданным правилом. Чтобы создать операцию на бумаге, математики разработали диаграмму линий, называемую шаблоном сгиба, которая указывает, где сгибать бумагу. Складка на бумаге представляет собой входные данные. Если сложить бумагу по одной линии шаблона, складка перевернётся в одну сторону, что соответствует значению ИСТИНА. Но если сложить бумагу по другой (ближайшей) линии, складка перевернётся в противоположную сторону, что соответствует значению ЛОЖЬ.

Две из этих входных складок формируют сложный клубок складок, называемый гаджетом. Гаджет кодирует логическую операцию. Чтобы сделать все эти складки и при этом сохранить бумагу плоской — требование, которое выдвигают Халл и Захаревич, — они добавили третью складку, которая вынуждена складываться определённым образом. Если складка складывается в одну сторону, это означает, что на выходе — ИСТИНА. Если она складывается в другую сторону, это означает, что на выходе — ЛОЖЬ.

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

С конца 1990-х годов известно, что более простой одномерный аналог игры Конвея «Жизнь» является полной по Тьюрингу. Халл и Захаревич придумали, как записать эту версию «Жизни» в терминах логических операций. «В итоге нам понадобилось использовать только четыре вентиля: И, ИЛИ, НЕ-И и НЕ-ИЛИ», — сказала Захаревич, имея в виду два дополнительных простых вентиля. Но чтобы объединить эти разные вентили, им пришлось построить новые устройства, которые поглощали посторонние сигналы и позволяли другим сигналам поворачиваться и пересекаться, не мешая друг другу. «Это было самое сложное», — сказала Захаревич, — «выяснить, как заставить всё правильно выстроиться». После того, как ей и Халлу удалось собрать свои устройства вместе, они смогли закодировать всё необходимое в сгибах бумаги, тем самым показав, что оригами является полной по Тьюрингу.

Компьютер для оригами был бы крайне неэффективным и непрактичным. Но, в принципе, если бы у вас был очень большой лист бумаги и много свободного времени, вы могли бы использовать оригами для вычисления произвольного количества знаков числа $latex pi$, определения оптимального маршрута для каждого водителя доставки в мире или запуска программы для прогнозирования погоды. «В конечном итоге, рисунок сгиба получается гигантским», — сказал Халл. «Его сложно сложить, но он справляется со своей задачей».

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

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

«И поэтому, чем больше мы будем заниматься подобными вещами, — сказал Халл, — тем больше у нас шансов установить глубокие связи между оригами и устоявшимися разделами математики».

Источник: www.quantamagazine.org