Визуализация машины Тьюринга средствами СИ/С++ | Статья в сборнике международной научной конференции

Отправьте статью сегодня! Журнал выйдет 17 августа, печатный экземпляр отправим 21 августа.

Опубликовать статью в журнале

Библиографическое описание:

Коптенок Е. В., Корж Б. А., Пескова М. Ю., Лядов В. С., Капчерина А. А. Визуализация машины Тьюринга средствами СИ/С++ [Текст] // Исследования молодых ученых: материалы VII Междунар. науч. конф. (г. Казань, февраль 2020 г.). — Казань: Молодой ученый, 2020. — С. 3-6. — URL https://moluch.ru/conf/stud/archive/361/15617/ (дата обращения: 22.02.2020).



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На рис. 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.
Основные термины (генерируются автоматически): машина Тьюринга, текст программы, GNU, выполнение программы, двоичное число, символ.

Похожие статьи

Применение машины Тьюринга для реализации алгоритмов...

Программа для машины Тьюринга. Сама по себе МТ ничего не делает. Для того, чтобы заставить её работать, надо написать для неё

После этих предварительных действий начинается выполнение программы. В таблице отыскивается ячейка на пересечении первой...

Зарождение и золотой век искусственного интеллекта

Машина Тьюринга — это абстрактная вычислительная машина, созданная для формализации понятия алгоритма.

В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на...

Основные этапы развития искусственного интеллекта

Машина Тьюринга — это абстрактная вычислительная машина, созданная для формализации понятия алгоритма.

В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на...

Программы для электронно-вычислительных машин как объект...

Программы для электронных вычислительных машин (далее — программы для ЭВМ ) можно отнести к одним из самых молодых.

2. Предоставление экземпляров программы для ЭВМ или базы данных неопределенному кругу лиц , в том числе путем записи в память ЭВМ .

Разработка устройства преобразования 12-разрядного двоичного...

В данной статье представлена разработка устройства преобразования 12-разрядного двоичного кода в двоично-десятичный с индикацией полученных чисел. Ключевые слова: двоично-десятичный код, двоичный код, индикатор, индикация.

Разработка способа представления длинных чисел в памяти...

Закрытое ПО: большинство программ, реализующих вычисления неограниченно больших чисел с любой точностью разрабатываются для шифрования и кодирования и не находятся в открытом доступе. Разработанный программный продукт устраняет большинство недостатков доступных...

Анализ применения гомоморфных схем шифрования в алгоритмах...

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

Обзор систем машинного перевода | Статья в журнале...

В данной статье рассмотрены основные виды систем машинного перевода. Рас-смотрены основные системы машинного перевода, произведено их сравнение и анализ. Сделаны предположения о возможных путях развития подобных систем.

Похожие статьи

Применение машины Тьюринга для реализации алгоритмов...

Программа для машины Тьюринга. Сама по себе МТ ничего не делает. Для того, чтобы заставить её работать, надо написать для неё

После этих предварительных действий начинается выполнение программы. В таблице отыскивается ячейка на пересечении первой...

Зарождение и золотой век искусственного интеллекта

Машина Тьюринга — это абстрактная вычислительная машина, созданная для формализации понятия алгоритма.

В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на...

Основные этапы развития искусственного интеллекта

Машина Тьюринга — это абстрактная вычислительная машина, созданная для формализации понятия алгоритма.

В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на...

Программы для электронно-вычислительных машин как объект...

Программы для электронных вычислительных машин (далее — программы для ЭВМ ) можно отнести к одним из самых молодых.

2. Предоставление экземпляров программы для ЭВМ или базы данных неопределенному кругу лиц , в том числе путем записи в память ЭВМ .

Разработка устройства преобразования 12-разрядного двоичного...

В данной статье представлена разработка устройства преобразования 12-разрядного двоичного кода в двоично-десятичный с индикацией полученных чисел. Ключевые слова: двоично-десятичный код, двоичный код, индикатор, индикация.

Разработка способа представления длинных чисел в памяти...

Закрытое ПО: большинство программ, реализующих вычисления неограниченно больших чисел с любой точностью разрабатываются для шифрования и кодирования и не находятся в открытом доступе. Разработанный программный продукт устраняет большинство недостатков доступных...

Анализ применения гомоморфных схем шифрования в алгоритмах...

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

Обзор систем машинного перевода | Статья в журнале...

В данной статье рассмотрены основные виды систем машинного перевода. Рас-смотрены основные системы машинного перевода, произведено их сравнение и анализ. Сделаны предположения о возможных путях развития подобных систем.