Машина Тьюринга — одно из базовых устройств в компьютерной науке. Я играю в 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 бита избыточно в данном случае и взято с оглядкой на будущее.

Рис. 1. Ячейка памяти
Рис. 1. Ячейка памяти

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

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

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

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

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

Рис. 3 Ячейка программы
Рис. 3 Ячейка программы

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

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

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

Схема работы

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

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

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

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

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

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

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

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

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


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

Рис. 5 МТ в Майнкрафт
Рис. 5 МТ в Майнкрафт

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

Рис. 6 Вид сверху на МТ
Рис. 6 Вид сверху на МТ

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

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

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

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

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

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

Рис. 7 Основные элементы, вид сверху
Рис. 7 Основные элементы, вид сверху

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

Рис. 8 Вид вблизи
Рис. 8 Вид вблизи
Рис. 9 Вид на цикл исполнения
Рис. 9 Вид на цикл исполнения

Заключение

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