Машина Тьюринга
Описание
Машина Тьюринга (МТ) — абстрактная вычислительная машина, предложенная Аланом Тьюрингом для формализации понятия алгоритма.
В состав машины Тьюринга входит неограниченная в обе стороны лента, разделённая на ячейки, и управляющее устройство, способное находиться в одном из конечного множества заранее определённых состояний.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
МТ работает согласно правилам перехода. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо, либо либо остаться на месте. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма. Результатом работы МТ является слово, записанное на ленте после остановки вычислителя.
В данном практическом задании предлагается реализовать систему, визуализирующую процесс вычислений МТ для произвольных программ и входных слов.
Минимальные требования (базовая часть)
Базовая реализация проекта, в которой должны разбираться все участники, должна включать:
- загрузку программы из файла;
- интерфейс для визуализации вычислений на МТ (лента, набор состояний, текущая конфигурация);
- возможность указать входное слово;
- возможность прервать/продолжить/остановить/начать вычисления заново.
Описание программы в виде файла должно также состоять из определения алфавитов и множества состояний, в которых выделены начальное и конечные состояния. Формат описания может быть как придуманным самостоятельно, так и одним из существующих языков разметки (например, JSON, YAML, TOML).
Расширенный интерфейс (индивидуальная часть)
Расширенный интерфейс должен добавлять хотя бы 2 различные возможности к базовому интерфейсу. Ниже перечислены возможные варианты расширения интерфейса, однако этим списком они не ограничены:
- настройки максимального количества шагов, скорости их отображения и т.д.;
- пошаговый режим;
- проверка корректности входных данных;
- и т.д.
Графический интерфейс для построения программ (индивидуальная часть)
Модуль должен включать в себя графический интерфейс для создания программ для МТ. У пользователя должна быть возможность:
- указать используемый алфавит ленты и входных слов;
- построить таблицу переходов;
- обозначить начальное и конечные состояния;
- запустить программы сразу;
- сохранить программу в формате, воспринимаемом интерпретатором, для дальнейшей загрузки;