Нормальные алгорифмы Маркова

тренажер для изучения универсального исполнителя

Что это такое?

Тренажёр «Нормальные алгорифмы Маркова» — это учебная модель универсального исполнителя, предложенного в 1940-х годах А.А. Марковым для уточнения понятия алгоритма. Марков предположил, что любой алгоритм может быть записан в виде нормального «алгорифма» (учёный считал, что правильно произносить это иностранное слово именно так). Позднее было доказано, что нормальные алгорифмы Маркова эквивалентны по своим возможностям другим универсальным исполнителям: машине Тьюринга и машине Поста.

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

Слова слева и справа от знака «->» могут быть (а могут и не быть) заключены в апострофы или двойные кавычки. Следующие подстановки равносильны и определяют замену буквы «а» на сочетание «бв»:
    а -> бв
    'а' -> 'бв'
    "а" -> "бв"
    'а' -> "бв"

Левая часть (слово-образец) может отсутствовать, в этом случае слово-замена ставится в самое начало рабочего слова. Обычно такая замена должна стоять последней в списке подстановок (иначе происходит зацикливание).

Правая часть подстановки тоже может отсутствовать (при стирании образца).

Символ «.» после слова-замены обозначает терминальную подстановку, после которой выполнение алгоритма заканчивается. Например:
    'а' -> 'б'.  заменить «а» на «б» и остановить программу
        * -> .    стереть знак «*» и остановить программу

Где почитать ещё?

1. Майер Р.В. Алгорифмы Маркова (komp-model.narod.ru).
2. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач, М.: МГУ, 2006.
3. Бекман И.Н. Компьютерные науки. Лекция 7. Алгоритмы (profbeckman.narod.ru)
4. Соловьев А. Дискретная математика без формул (lib.rus.ec)
5. Ершов С.С. Элементы теории алгоритмов, Челябинск, Издательский центр ЮУрГУ, 2009.
6. Нормальный алгоритм Маркова для деления чисел (habrahabr.ru).

Что с этим делать?

В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.

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

Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.

Задачи можно сохранять в файлах и загружать из файлов. Сохраняется условие задачи, исходное слово и система подстановок.

Протокол работы алгоритма, в котором показаны все последовательные замены, вызывается при нажатии клавиш Ctrl+P.

Если вы заметили ошибку или у вас есть предложения, замечания, жалобы, просьбы и заявления, пишите.

Технические требования

Программа работает под управлением операционных систем линейки Windows на любых современных компьютерах.

Лицензия

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

Программа поставляется «as is», то есть, автор не несет никакой ответственности за всевозможные последствия ее использования, включая моральные и материальные потери, вывод оборудования из строя, физические и душевные травмы.

При размещении программы на других веб-сайтах ссылка на первоисточник обязательна.

Использование и скачивание материалов означает, что вы приняли условия этого лицензионного соглашения.

Скачать

Тренажер «Нормальные алгорифмы Маркова» (архив RAR, 195 Кб)

Пароль к архиву — kpolyakov.spb.ru

В архив включены следующие файлы:

После распаковки архива программа находится в работоспособном состоянии и не требует никаких дополнительных установок.