Визуализация машины Тьюринга средствами СИ/С++
Авторы: Коптенок Елизавета Викторовна, Корж Богдан Андреевич, Пескова Марина Юрьевна, Лядов Вячеслав Сергеевич, Капчерина Алина Алексеевна
Рубрика: 4. Информатика
Опубликовано в
VII международная научная конференция «Исследования молодых ученых» (Казань, февраль 2020)
Дата публикации: 28.01.2020
Статья просмотрена: 445 раз
Скачать электронную версию
Библиографическое описание:Визуализация машины Тьюринга средствами СИ/С++ / Е.
В данной статье описана реализация симулятора машины Тьюринга средствами C++ с использованием визуальной библиотеки Qt. Приложение может быть полезно всем, кто изучает информатику, теорию вычислений и алгоритмов, так как с его помощью можно лучше понять устройство машины Тьюринга — одной из фундаментальных математических концепций в информатике.
Существует большое количество похожих реализаций, большинство из них выполнено в виде веб-приложений. Главная особенность моей реализации в том, что она является десктопным приложением. Благодаря этому достигается более высокая отзывчивость и скорость работы.
Машина Тьюринга — это абстрактная вычислительная машина, предложенная математиком Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Согласно тезису Чёрча-Тьюринга, машина способна имитировать всех исполнителей, каким-либо образом реализующих в котором каждый шаг вычисления достаточно элементарен.
Машина Тьюринга состоит из двух частей — ленты и автомата. Лента используется для хранения информации. Она бесконечна в обе стороны и разбита на клетки, которые никак не нумеруются и не именуются. В каждой клетке может быть записан один символ или ничего не записано. Содержимое клетки может меняться — в неё можно записать другой символ или стереть находящийся в ней символ.
В начале выполнения машина находится в некотором состоянии, определенном пользователем. Каретка, в зависимости от своего состояния и содержимого текущей ячейки, выполняет действия, определенные соответствующей строчкой кода: записывает в ячейку новый символ, переходит в следующее состояние и выполняет смещение (переходит либо на следующую ячейку, либо на предыдущую, либо стоит на месте).
Этот процесс происходит до тех пор, пока не будет достигнуто одно из нескольких состояний, отмеченных пользователем как терминальные.
Интерфейс программы представлен на рис. 1.
Рис. 1. Внешний вид программы
Чтобы запустить машину Тьюринга, пользователь сперва должен ввести в поле редактора кода (см. рис. 2) текст программы, и нажать кнопку «Компилировать». Если программа была скомпилирована успешно, можно загружать исходные данные на ленту, с помощью поля ввода в верхнем левом углу и кнопки «Load».
После этого можно запустить выполнение программы нажатием кнопки «Пуск» (первая слева), и затем контролировать выполнение программы кнопками «Пауза», «Стоп», «Шаг вперед». Ползунок справа позволяет изменять скорость выполнения программы прямо во время выполнения.
Компилятор уведомляет пользователя о синтаксических ошибках в программе, указывая место, где была допущена ошибка, и ее предполагаемый тип (рис. 3).
Рис. 2.
Редактор кода
Рис. 3. Уведомление о синтаксической ошибке
Так как машины описывается конечным числом состояний, программа должна включать в себя следующие строчки.
- Начальное состояние. Синтаксис:
- Список терминальных состояний. Синтаксис:
- Список возможных условий. Каждое условие описывается двумя последовательными строками кода, их синтаксис выглядит следующим образом:
Где [перемещение] — это один из трех символов: “ ” — на ячейку вправо,”-” — остаться на месте.
На рис. 4. представлен текст программы, которая проверяет делимость двоичного числа на 3. Это простейшая программа, которая может стать хорошей иллюстрацией возможностей симулятора.
Рис. 4. Текст программы, которая проверяет делимость двоичного числа на 3
В данной статье был рассмотрен завершенный и готовый к использованию программный продукт, который может быть использован в образовательных целях.
Исходный код программы распространяется по открытой лицензии GNU GPLv2 и размещен на Github, поэтому его может использовать и улучшать любой желающий. У меня есть некоторые идеи по дальнейшему улучшению проекта. Возможно, в будущем будет добавлен статический анализатор кода программы, каталог примеров программ. Также многие проекты-аналоги умеют работать с несколькими лентами (концепция машины Тьюринга допускает такие модификации). Это могло бы стать следующим шагом в развитии проекта.
Литература:
- 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
- Павловская, Т. А. C/C++. Процедурное и объектно-ориентированное программи-рование / Т. А. Павловская. — СПб.: Питер, 2015. — 496 с.
- Qt Documentation [Электронный ресурс]. — Режим доступа: https://doc.qt.io/ сво-бодный (01.
06.2019). - Орлов. С. Программная инженерия. Технологии разработки программного обеспечения / С. Орлов — СПб.: Питер, 2018–640с.
- Eckel B. Thinking in C++. / Bruce Eckel — Prentice Hall, 1995.
- Stroustrup B. The C++ Programming Language. / Bjarne Stroustrup — Addison-Wesley, 1985.
06.2019).Основные термины (генерируются автоматически): машина Тьюринга, текст программы, GNU, выполнение программы, двоичное число, символ.
Похожие статьи
Применение
машины Тьюринга для реализации алгоритмов…Программа для машины Тьюринга. Сама по себе МТ ничего не делает. Для того, чтобы заставить её работать, надо написать для неё
После этих предварительных действий начинается выполнение программы. В таблице отыскивается ячейка на пересечении первой…
Зарождение и золотой век искусственного интеллекта
Машина Тьюринга — это абстрактная вычислительная машина
, созданная для формализации понятия алгоритма.
В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на…
Основные этапы развития искусственного интеллекта
Машина Тьюринга — это абстрактная вычислительная машина, созданная для формализации понятия алгоритма.
В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на…
Программы для электронно-вычислительных машин как объект…
2. Предоставление экземпляров программы для ЭВМ или базы данных неопределенному кругу лиц , в том числе путем записи в память ЭВМ .
Разработка устройства преобразования 12-разрядного
двоичного…В данной статье представлена разработка устройства преобразования 12-разрядного двоичного кода в двоично-десятичный с индикацией полученных чисел. Ключевые слова: двоично-десятичный код, двоичный код, индикатор, индикация.
Разработка способа представления длинных
чисел в памяти…Закрытое ПО: большинство программ, реализующих вычисления неограниченно больших чисел с любой точностью разрабатываются для шифрования и кодирования и не находятся в открытом доступе. Разработанный программный продукт устраняет большинство недостатков доступных.
..
Анализ применения гомоморфных схем шифрования в алгоритмах…
Ограничение на работу с целыми числами, количество возможных операций сложения и умножения из-за возрастающего криптографического шума, означает, что на практике гомоморфное шифрование позволяет работать только над зашифрованными данными…
Обзор систем машинного перевода | Статья в журнале…
В данной статье рассмотрены основные виды систем машинного перевода. Рас-смотрены основные системы машинного перевода, произведено их сравнение и анализ. Сделаны предположения о возможных путях развития подобных систем.
- Как издать спецвыпуск?
- Правила оформления статей
- Оплата и скидки
Похожие статьи
Применение
машины Тьюринга для реализации алгоритмов…
Программа для машины Тьюринга. Сама по себе МТ ничего не делает. Для того, чтобы заставить её работать, надо написать для неё
После этих предварительных действий начинается выполнение программы. В таблице отыскивается ячейка на пересечении первой…
Зарождение и золотой век искусственного интеллекта
Машина Тьюринга — это абстрактная вычислительная машина, созданная для формализации понятия алгоритма.
В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на…
Основные этапы развития искусственного интеллекта
Машина Тьюринга — это абстрактная вычислительная машина, созданная для формализации понятия алгоритма.
В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на…
Программы для электронно-вычислительных машин как объект…Программы для электронных вычислительных машин (далее — программы для ЭВМ ) можно отнести к одним из самых молодых.
2. Предоставление экземпляров программы для ЭВМ или базы данных неопределенному кругу лиц , в том числе путем записи в память ЭВМ .
Разработка устройства преобразования 12-разрядного
двоичного… В данной статье представлена разработка устройства преобразования 12-разрядного двоичного кода в двоично-десятичный с индикацией полученных чисел.
Ключевые слова: двоично-десятичный код, двоичный код, индикатор, индикация.
Разработка способа представления длинных
чисел в памяти…Закрытое ПО: большинство программ, реализующих вычисления неограниченно больших чисел с любой точностью разрабатываются для шифрования и кодирования и не находятся в открытом доступе. Разработанный программный продукт устраняет большинство недостатков доступных…
Анализ применения гомоморфных схем шифрования в алгоритмах…
Ограничение на работу с целыми числами, количество возможных операций сложения и умножения из-за возрастающего криптографического шума, означает, что на практике гомоморфное шифрование позволяет работать только над зашифрованными данными…
Обзор систем машинного перевода | Статья в журнале.
..В данной статье рассмотрены основные виды систем машинного перевода. Рас-смотрены основные системы машинного перевода, произведено их сравнение и анализ. Сделаны предположения о возможных путях развития подобных систем.
Онлайн курс «Введение в квантовые вычисления»
Лекция 1. Введение. Историческая перспектива и современное состояние области. Зарождение индустрии квантовых вычислений. Представление об особенностях квантовых вычислений на примере простейшего алгоритма Дейча.
Лекция 2. Необходимые сведения из теории вычислительной сложности алгоритмов. Понятие алгоритма, машина Тьюринга, универсальная машина Тьюринга. Вычислимые и невычислимые функции, проблема остановки. Задачи разрешимости, представление о классах вычислительной сложности. Классы P и NP. Вероятностная машина Тьюринга, класс BPP. Задачи пересчёта количества решений, класс сложности #P. Проблема демонстрации квантового превосходства на примере задачи BosonSampling.
Лекция 3.
Гейтовая модель классических вычислений, универсальные вентили. Гейтовая модель квантовых вычислений. Элементарные квантовые логические вентили, однокубитные и двухкубитные вентили. Условные двухкубитные вентили, представление условных многокубитных вентилей через двухкубитные. Описание измерений в квантовой теории, описание измерений в квантовых схемах.
Лекция 4. Универсальность однокубитных вентилей и вентиля CNOT. Дискретизация однокубитных вентилей, универсальные дискретные наборы вентилей. Сложность аппроксимации произвольного унитарного преобразования.
Лекция 5. Квантовое преобразование Фурье. Алгоритм оценки фазы, оценка необходимых ресурсов, упрощённый алгоритм Китаева. Экспериментальные реализации алгоритма оценки фазы и приложения к расчёту молекулярных термов.
Лекция 6. Алгоритм поиска периода функции. Факторизация чисел на простые множители, алгоритм Шора. Экспериментальные реализации алгоритма Шора. Другие алгоритмы, основанные на квантовом преобразовании Фурье.
Лекция 7. Квантовые алгоритмы поиска. Алгоритм Гровера, геометрическая иллюстрация, оценка ресурсов. Подсчёт числа решений поисковой задачи. Ускорение решения NP-полных задач. Квантовые поиск в неструктурированной базе данных. Оптимальность алгоритма Гровера. Алгоритмы, основанные на случайных блужданиях. Экспериментальные реализации поисковых алгоритмов.
Лекция 8. Классические коды коррекции ошибок, линейные коды. Ошибки в квантовых вычислениях, отличие от классического случая. Трехкубитный код, исправляющий X-ошибку. Трехкубитный код, исправляющий Z-ошибку. Девятикубитный код Шора.
Лекция 9. Общая теория исправления ошибок, дискретизация ошибок, модель независимых ошибок. Классические линейные коды, коды Хэмминга. Квантовые коды Кальдербанка-Шора-Стина.
Лекция 10. Формализм стабилизаторов, построение кодов КШС в формализме стабилизаторов. Унитарные преобразования и измерения в формализме стабилизаторов. Понятие о вычислениях, устойчивых к ошибкам. Построение универсального набора устойчивых к ошибкам вентилей.
Измерения, устойчивые к ошибкам. Пороговая теорема. Экспериментальные перспективы реализации квантовой коррекции ошибок и устойчивых к ошибкам вычислений.
Лекция 11. Квантовые симуляции: «цифровые» и аналоговые. Некоторые экспериментальные реализации и перспективы аналоговых квантовых симуляций.
Лекция 12. Квантовые вычисления на NISQ-устройствах. Квантовые вариационные алгоритмы: QAOA и VQE. Приложения к задачам квантовой химии. Возможности реализации на современных квантовых процессорах, перспективы развития.
онлайн -симулятор машины Turing Machine
Библиотека программ
Примеры
UnaryStringDuplication
IntegerMultiplication
Сэкономленные программы
.
Используйте начальное ключевое слово .
Например: initial q0 объявляет q0 начальным состоянием.
Объявить состояние принятия
Используйте ключевое слово accept .
Например: accept qa объявляет qa как состояние принятия.
Объявить состояние отклонения (необязательно)
Используйте ключевое слово reject .
Например: reject qr объявляет qr как состояние отклонения.
Кортежи
Кортеж состоит из следующего:
- текущее состояние
- прочитанный символ (усеченный до первого символа)
- следующее состояние
- Символ записи (усечен до первого символа)
- Направление
L(или-1) означает левый,R(или1). кортеж Q0 a Q1 b rозначает: когда вы находитесь в состоянии Q0 и сталкиваетесь с символ «а» на ленте, переключитесь в состояние Q1, напишите «б» на ленте и двигайтесь вправо.Вызов одной машины с другой
Вы можете создать несколько машинных программ и вызывать одну машину с другой.
- Создайте новую программу с помощью кнопки «Новая программа».
- Объявите начальное состояние машины, состояния принятия/отклонения и кортежи в соответствии с вашими потребностями.
- Дайте этой программе имя, например. IS_EVEN
- Теперь, чтобы вызвать IS_EVEN с другой машины, используйте команду exec .
Например, если вы хотите, чтобы IS_EVEN вызывался, когда вы находитесь в состоянииq1и читаете0вы должны использоватьq1 0 exec IS_EVEN.
Указание состояния родительской машины после выполнения дочерней машины (необязательно)
Вы можете указать состояние родительской машины после того, как дочерняя машина завершила выполнение, в зависимости от того, приняла или отклонила дочерняя машина.Например, следующая команда выполняет машину IS_EVEN, а затем переключается в состояние Qeven, если IS_EVEN принята:
q1 0 exec IS_EVEN Qevenотклонил:
q1 0 exec IS_EVEN Qeven QoddЕсли для сценария принятия или отклонения не указаны состояния, родительская машина сохраняет последнее состояние дочерней машины.
turing-machine-simulator · GitHub Topics · GitHub
Вот 173 публичных репозитория соответствует этой теме…
йедхукришнан / машина Тьюринга
Звезда 660нованта / недетерминированный-симулятор-машины-Тьюринга
Звезда 25диэггси / машина Тьюринга
Звезда 15Шацк / турси
Звезда 13Дракс10 / bf-in-css
Звезда 11сайсубхам / симулятор машины Тьюринга
Звезда 11м-патнэм / пдбл
Звезда 9tfburns / TuringMachine.
jl Звезда
8RuiDGPires / Простой эмулятор машины Тьюринга
Звезда 7л-квартира / квартира
Звезда 7морской берег / эмулятор машины Тьюринга
Звезда 6маргуал56 / ТьюрингМашина
Звезда 6кирка828 / турбина
Звезда 5аропи / Симулятор машины Тьюринга
Звезда 5Леннарт4711 / Пользовательский процессор
Звезда 5Клонекси700 / NSU-opd-dmta-решатель
Звезда 4RullDeef / МатематикаАлгоритмы
Звезда 4заз / Тьюринг
Звезда 4eric11eca / AutomatonStudio
Звезда 5туманная ночь / машина Тьюринга
Звезда 6Улучшить эту страницу
Добавьте описание, изображение и ссылки на симулятор машины Тьюринга страницу темы, чтобы разработчикам было легче узнать о ней.
кортеж 
jl Звезда
8