Универсальная машина Тьюринга из оригами.

Не так давно на Ежике была заметка про оригами. Точнее про оригаметрию — объединение оригами (искусства складывать бумагу) с геометрией, которое позволяет наглядно решать некоторые геометрические задачи.

https://vk.com/wall-186208863_42669

То есть мы можем считать оригаметрию неким прототипом геометрического решателя.

Однако совсем недавно, в сентябре 2023 года, Томас Хулл и Инна Захаревич (Thomas Hull & Inna Zakharevich) открыли, что оригами полны по Тьюрингу. То есть из них можно создать гипотетический компьютер, способный реализовать любой алгоритм.

В нашем нынешнем общераспространенном цифровом понимании алгоритма, его реализация возможна на машине, состоящей из элементов, способных выполнять простые логические операции: И, ИЛИ, НЕ. Другими словами, если мы можем сконструировать некие элементы, которые могут механическим, электрическим, оптическим или каким-либо другим путем вычислить значения базовых логических выражений, то из этих элементов мы сможем построить компьютер.

Именно эту задачу — задачу построения из сложенной бумаги базовых логических элементов, и решили упомянутые авторы. Как именно они сложили элементы И, ИЛИ и НЕ, отлично показано в видео.

https://www.youtube.com/watch?v=dvtUWq2N7Fg

Статья авторов, в которой доказано, что эти оригами полны по Тьюрингу, доступна на сервере препринтов:

> Hull & Zakharevich (2023) Flat origami is Turing complete.

> https://arxiv.org/abs/2309.07932

И там же есть последующая работа Михаэля Аззиза (Michael Assis), в которой он доказывает, что из оригами можно построить универсальную машину Тьюринга:

> Assis (2024) An origami Universal Turing Machine design.

> https://arxiv.org/abs/2406.08490

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

Источник: arxiv.org

Комментарии: