В данном проекте реализованы несколько базовых вариаций машины Тьюринга, а именно классическая машина Тьюринга, машина Тьюринга с полубесконечной лентой и машина Тьюринга с несколькими бесконечными лентами.
В данном проекте есть 3 готовых программы для машины Тьюринга: одна для классической и полубесконечной и две для машины Тьюринга с несколькими бесконечными лентами. Каждая машина Тьюринга описывается json файлом. Программы для классической машины Тьюринга и для машины Тьюринга с несколькими лентами не совместимы. При запуске main.py вас попросят выбрать json файл с описанием машины Тьюринга и тип самой машины. Если для json файла, который был написан под классическую версию машины Тьюринга, выбрать машину Тьюринга с несколькими лентами, то вы получите ошибку. Обратное тоже верно. Также если запустить invert_bits.json на маине Тьюринга с полубесконечной лентой, то получится ошибка, так как программа invert_bits.json допускает переход через границу.
Вся программа это list из следующих компонент (перечислены по порядку):
- Список состояний. Каждое состояние это целое число. Должен содержать начальное состояние.
- Список символов ленточного алфавита. Может сожержать как строки, так и целые числа. Должен включать в себя пустой символ. Строки нужно прописывать в одинарных кавычках.
- Начальное состояние. Целое число.
- Пустой символ. Целое число или символ.
- Функция дельта. Задаётся как словать, где ключи - это кортеж (состояние, текущий символ), а значения - это кортеж (новое состояние, новый символ, смещение каретки). Смещение каретки это строка 'R', 'N' или 'L'.
- Множество конечных состояний. Результатом работы машины Тьюринга считается непрерывный список непустых символов, который начинается с финального положения каретки.
- Стартовое заполнение ленты. Предстваляет из себя словарь, где ключи - строки, содержащие целые числа, а значения это элементы ленточного алфавита.
Программы пожожи на программы для машин Тьюринга с одной кареткой за следующими исключениями:
- Первый элемент списка программы - это целое положительное число, определяющее количество лент.
- Функция дельта описывается немного иначе: ключами в данном случае выступают кортежи в которых первый элемент - это состояние, а второй - это кортеж символов на которые указывают соответсвующие каретки; значениями выступают кортежи, в которых первый элемент - это новое состояние, а остальные это кортежи из двух элементов: новый символ и смещение каретки.
- Стартовое заполнение ленты задаётся списком словарей, где каждый словарь описывает начальное состояние соответсвующей ленты.
Вы можете написать свой json файл и положить его в одну директорию с файлом main.py, а затем при запуске ввести его имя, затем выбрать нужную машину Тьюринга и если программа написана корректно, то код завершится успешно, иначе вылетит ошибка, подсказывающая какой из элементов описание программы некорректен. Есть уже готовый invert_bits.json для машин Тьюринга с одной лентой, который инвертирует биты, заданные на входе. Также есть готовый invert_bits_two_tapes.json, который делает то же самое, только на двух лентах, и factorial.json, который вычсляет факториал в унарной системе счисления (ответ записывается на четвёртую ленту и для удобства проще выводить просто размер результата на четвёртой ленте). В уже готовых проектах вы также можете менять входные данные и смотреть как будет вести себя программа.