Машина Тьюринга в Minecraft

Машина Тьюринга — одно из базовых устройств в компьютерной науке. Я играю в Minecraft уже более 12 лет и имею большой опыт в реализации различных механизмов внутри игры. Спустя годы университетской учёбы и работы в индустрии пришла идея совместить хобби с фундаментальной теорией — реализовать машину Тьюринга средствами игры и поделиться результатом.
Машина Тьюринга состоит из трёх базовых элементов:

• Лента — последовательность ячеек, расположенных друг за другом (в модели - бесконечная).

• Головка — устройство чтения-записи, позиционированное на текущей ячейке ленты.

• Таблица переходов — программа для машины, набор команд в формализованном виде.

Подробное теоретическое описание МТ легко найти в открытых источниках, поэтому сосредоточимся на реализации.

Редстоун как основа симуляции

Minecraft имеет встроенную механику симуляции электрических сигналов — редстоун. Разберём её базовые составляющие.

Сигнал и его уровни

Редстоун-сигнал имеет 16 уровней мощности — от 0 (нет сигнала) до 15 (максимум). Пыль передаёт сигнал на расстояние до 15 блоков, теряя 1 уровень на каждом блоке.
Провода Редстоун-пыль — основной проводник сигнала. Она соединяется с соседними пылинками, блоками и компонентами автоматически, образуя цепи.

Ключевые компоненты

• Факел — инвертирующий источник: горит по умолчанию и гаснет, если блок, на котором он установлен, получает сигнал. Это фактически элемент NOT

• Рычаг — в положении «включено» полностью запитывает блок, на котором установлен; стабильный источник сигнала.

• Кнопка — аналог рычага, но даёт импульс фиксированной длины.

• Повторитель (репитер) — восстанавливает сигнал до максимального уровня, передаёт его строго в одном направлении и вносит задержку от 1 до 4 тиков. Незаменим для построения длинных цепей и управлением направления сигналом.

• Компаратор — сравнивает два сигнала. В режиме сравнения: пропускает сигнал, только если основной вход ? бокового. В режиме вычитания: вычитает боковой сигнал из основного. Используется для построения более сложной логики

Логические элементы

Из факелов, повторителей и пыли собираются все базовые логические вентили:

• NOT — факел на выходе провода: инвертирует сигнал

• AND — два повторителя направленных в факелы, сходящихся в один блок с факелом на выходе

• OR — два провода, сходящихся в один: сигнал есть, если хотя бы один из входов активен

• NAND / NOR — комбинации вышеперечисленного Именно из этих примитивов будут собраны все крупные блоки нашей машины: память ленты, логика головки и таблица состояний. Алфавит Для удобства выберем алфавит из 4 символов. Это позволяет кодировать не только 0 и 1, но и специальный пустой символ (обозначающий отсутствие записи), а четвёртое значение оставить в резерве.

Реализация

Ячейка памяти

Служит для хранения данных на ленте. Содержит 4 бита и может хранить значения от 0 до 15. Ячейка после активации (см. рис. 1) постоянно выдает записанный сигнал, в данном случае это 0101. На входной группе слева под первой табличкой имеется кнопка для сброса состояния ячейки. 4 бита избыточно в данном случае и взято с оглядкой на будущее.

Сдвиговый регистр

Для того, чтобы добавить возможность указывать на одну из множества ячеек памяти, нужен сдвиговый регистр. Устройство имеет ряд ламп, горящая лампа как раз и есть то, куда будет указывать головка. Справа под табличками (см. рис. 2) есть 3 кнопки, первая — сместить головку на один влево, вторая — сместить головку на один вправо, третья — сбросить состояние сдвигового регистра в начальное положение. Начально положение — горит самая левая лампа. Слева в отстранении стоит опциональная лампа, которая активируется когда битовый сдвигатель завершает каждое смещение. Таким образом можно минимизировать задержку в общем цикле программы и ожидать стабильной работы битового сдвигателя. По факту реализует операцию битового сдвига.

Ячейка программы

Примитив таблицы для хранения состояния. Содержит 10 бит информации.
Первые 4 бита — значение, которое МТ запишет в ячейку на которую указывает головка ленты.
Следующие 2 бита определяют смещение головки. 10 — влево, 01 — вправо, можно увидеть что в данной ячейке выбрано смещение влево.
Следующие 4 бита — состояние, в которое произойдет переход после движения головки. 4 бита избыточно в данном случае и взято с оглядкой на будущее.
Таким образом — после попадания ячейки в цикл исполнения программы она сначала запишет значение на ленту, затем сдвинет головку, затем перейдет в выбранное состояние.

Двоично-десятичный преобразователь

Понадобится для того, чтобы из программы, заданной в двоичных числах, можно было обращаться к реальным объектам. Также опциональный, но сильно упрощает логику работу механизма и построение МТ. На вход справа (см. рис. 4) подается двоичное число, в данном случае 10, а на выходе слева видно полученное десятичное значение — 2.

Схема работы

Таким образом, запуск машины происходит с цикла исполнения. Он работает на фиксированных задержках перед обращениями к компонентам устройств. Например, прочитали ячейку — ждем 2 секунды, записали в ячейку — ждем 2 секунды, и так далее. Механизмы не снабжены сигналом, означающим завершение работы конкретного компонента. Например, был отправлен запрос на смещение головки вправо, но когда она отработает неизвестно. Технической сложности в этом нет, это было сделано для получения более быстрого результата.

Общая схема работы:

1. Запуск машины

2. Чтение символа в ячейке памяти

3. Получение перехода из таблицы на основе текущего состояния и символа в ячейке

4. Запись значения из таблицы перехода в текущую ячейку

5. Смещение головки

6. Перемещение в новое состояние

7. Если состояние пустое, отправить сигнал на завершение цикла исполнения, в противном случае переходим в 2.

Собрав всем компоненты в одну систему и подключив все необходимые линии получаем МТ в Майнкрафт.

Если смотреть сверху вниз на механизм, можно детально рассмотреть его узлы в действии.

1. Закодированная программа, состоящая из 4 состояний (одно из них конечное) и из 4 символов алфавита (один из них ?-символ, пустой символ). Таким образом получаем 20 примитивных ячеек программы.

2. Лента, состоящая из 8 ячеек памяти. Суммарная память всей ленты 32 бита.

3. Битовый сдвигатель.

4. Цикл исполнения.

5. Двоично-десятичные преобразователи.

Оранжевый провод, идущий от 1 к 4 — провод, по которому передается завершающий сигнал. Инициируется при переходе в конечное состояние и завершает работы цикла исполнения программы.

Дополнительные изображения

Заключение

В результате получился интересный полностью функциональный механизм, реализующий частный случай МТ. Пример работы можно посмотреть тут. Представлена программа, которая выполняет операцию инкремента для заранее заполненного числа.Играйте в Майнкрафт и получайте удовольствие!