Визуализация машины Тьюринга средствами СИ/С++



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

Существует большое количество похожих реализаций, большинство из них выполнено в виде веб-приложений. Главная особенность моей реализации в том, что она является десктопным приложением. Благодаря этому достигается более высокая отзывчивость и скорость работы. Однако, приложение не проигрывает в универсальности своим веб-аналогам, так как может выполняться на большинстве современных операционных систем.

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

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

В начале выполнения машина находится в некотором состоянии, определенном пользователем. Каретка, в зависимости от своего состояния и содержимого текущей ячейки, выполняет действия, определенные соответствующей строчкой кода: записывает в ячейку новый символ, переходит в следующее состояние и выполняет смещение (переходит либо на следующую ячейку, либо на предыдущую, либо стоит на месте). Этот процесс происходит до тех пор, пока не будет достигнуто одно из нескольких состояний, отмеченных пользователем как терминальные.

Интерфейс программы представлен на рис. 1.

Рис. 1. Внешний вид программы

Чтобы запустить машину Тьюринга, пользователь сперва должен ввести в поле редактора кода (см. рис. 2) текст программы, и нажать кнопку «Компилировать». Если программа была скомпилирована успешно, можно загружать исходные данные на ленту, с помощью поля ввода в верхнем левом углу и кнопки «Load».

После этого можно запустить выполнение программы нажатием кнопки «Пуск» (первая слева), и затем контролировать выполнение программы кнопками «Пауза», «Стоп», «Шаг вперед». Ползунок справа позволяет изменять скорость выполнения программы прямо во время выполнения.

Компилятор уведомляет пользователя о синтаксических ошибках в программе, указывая место, где была допущена ошибка, и ее предполагаемый тип (рис. 3).

Рис. 2. Редактор кода

Рис. 3. Уведомление о синтаксической ошибке

Так как машины описывается конечным числом состояний, программа должна включать в себя следующие строчки.

1. Начальное состояние. Синтаксис:
2. Список терминальных состояний. Синтаксис:

3. Список возможных условий. Каждое условие описывается двумя последовательными строками кода, их синтаксис выглядит следующим образом:

Где [перемещение] — это один из трех символов: “ <” — на ячейку влево,”>” — на ячейку вправо,”-” — остаться на месте.

На рис. 4. представлен текст программы, которая проверяет делимость двоичного числа на 3. Это простейшая программа, которая может стать хорошей иллюстрацией возможностей симулятора.

Рис. 4. Текст программы, которая проверяет делимость двоичного числа на 3

В данной статье был рассмотрен завершенный и готовый к использованию программный продукт, который может быть использован в образовательных целях. Исходный код программы распространяется по открытой лицензии GNU GPLv2 и размещен на Github, поэтому его может использовать и улучшать любой желающий. У меня есть некоторые идеи по дальнейшему улучшению проекта. Возможно, в будущем будет добавлен статический анализатор кода программы, каталог примеров программ. Также многие проекты-аналоги умеют работать с несколькими лентами (концепция машины Тьюринга допускает такие модификации). Это могло бы стать следующим шагом в развитии проекта.

Литература:

1. B. Jack Copeland. The Essential Turing: Seminal Writings in Computing, Logic, Phi-losophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma / Claren-don Press (Oxford University Press), Oxford UK, 2013
2. Павловская, Т. А. C/C++. Процедурное и объектно-ориентированное программи-рование / Т. А. Павловская. — СПб.: Питер, 2015. — 496 с.
3. Qt Documentation [Электронный ресурс]. — Режим доступа: https://doc.qt.io/ сво-бодный (01.06.2019).
4. Орлов. С. Программная инженерия. Технологии разработки программного обеспечения / С. Орлов — СПб.: Питер, 2018–640с.
5. Eckel B. Thinking in C++. / Bruce Eckel — Prentice Hall, 1995.
6. Stroustrup B. The C++ Programming Language. / Bjarne Stroustrup — Addison-Wesley, 1985.