Разработчик: Салават Ханов

Email: khanov@me.com

Версия: v 1.0

Данный проект — это имплементация (i.e. имитация) работы машины Тьюринга на C++.

Это консольное приложение. Тесты проводились на Mac OS X 10.7 в Xcode IDE 4.2.

Во время работы над этим проектом я пользовался электронной версией книги ВМК МГУ "Машина Тьюринга и алгоритмы Маркова. Решение задач" (В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая). Я проверял задачи оттуда, моя программа решает их правильно.

В принципе, программа способна решать любые задачи для машины Тьюринга при условии, что таблица составлена правильно.

Главная проблема — бесконечная лента. Программа ею ограничена. Думаю, что все же для большинства задач моя программа подходит; не уверен, что так часто приходится использовать ленту более 4096 символов. Хотя, возможно, есть способ решения проблемы с бесконечной лентой.

Что делает пользователь?

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

CSV (Comma-Separated Values — значения, разделённые запятыми) — текстовый формат, предназначенный для представления табличных данных.

Далее пользователь запускает программу-имплементатор и вводит начальную конфигурацию (слово) на ленте. На экран выведется результат выполнения программы так, как если бы она была выполнена на машине Тьюринга.

Видеодемонстрация (HD)

Как это работает?

Программа состоит из 3 главных частей:

1. Парсер считывает данные из csv файла. Данные в нем разделены символом ";". В первой строке расположен алфавит. Начиная со второй строчки, слева располагаются состояния, после которых команды для машины Тьюринга. Вместо символа "пусто" Λ я использую N.

2. Обработчик команд обрабатывает и сохраняет прочитанные парсером команды в массиве вида:

Это двумерный массив, который подобен исходной таблице с командами. Массив создается автоматически на основе тех данных, которые будут проанализированы парсером в исходной таблице в Excel: количество символов в алфавите alphabetSize и количество состояний states. В каждой ячейке этого массива соответственно хранятся:

3. Основной алгоритм — "сердце" всей программы. Именно здесь осуществляется запись символа в ячейку, сдвиг автомата и переход в новое состояние.

Сначала считывается символ с видимой ячейки currentCellSymbol = tape[currentTapePosition]. Затем в массиве алфавита alphabet[k] находим его индекс и присваиваем переменной currentCellIndex = k. Индекс нужен для того, чтобы определить с каким столбцом массива g[states][alphabetSize] мы работаем. Вся нумерация индексов начинается с 0. Теперь, так как мы знаем номер столбца currentCellIndex и строку (номер состояния currentState; по умолчанию он равен 0), мы находим соответствующую ячейку g[currentState][currentCellIndex] с командами и выполняем их.

Сначала записываем символ в видимую ячейку tape[currentTapePosition] = g[currentState][currentCellIndex].symbol. Затем сдвигаем автомат: увеличиваем или уменьшаем значение переменной currentTapePosition. Наконец, считываем из ячейки в какое состояние нужно перейти дальше и сохраняем его в переменной currentState = g[currentState][currentCellIndex].state.

Все это выполняется в цикле, пока булевая переменная terminator = 0. Она станет равна 1 тогда, когда мы прочитаем символ остановки "!". Символ остановки хранится в переменной состояния массива g[currentState][currentCellIndex].state и равен -1. Встретив его, мы делаем terminator = 1 и выходим из цикла.