Как построить компьютер оригами » вики полезно Журнал Кванта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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