Этот сайт больше не обновляется. Сайт К. Полякова «Преподавание, наука и жизнь»
переехал по адресу kpolyakov.spb.ru.
Новый адрес страницы, к которой вы обратились:
Пожалуйста, обновите свои закладки. Через 5 секунд вы будете перенаправлены
на новый сайт автоматически.
Нормальные алгорифмы Маркова
тренажер для изучения универсального исполнителя
Что это такое?
Тренажёр «Нормальные алгорифмы Маркова» — это учебная модель
универсального исполнителя, предложенного в 1940-х годах
А.А. Марковым для
уточнения понятия алгоритма.
Марков предположил, что любой алгоритм может быть записан в виде
нормального «алгорифма» (учёный считал, что правильно произносить это
иностранное слово именно так). Позднее было доказано, что нормальные
алгорифмы Маркова эквивалентны по своим возможностям другим универсальным исполнителям:
машине Тьюринга и машине Поста.
Нормальный алгорифм задает метод преобразования строк с помощью системы подстановок. Каждая подстановка состоит
из слова-образца и слова-замены, разделенных цепочкой символов «->».
На каждом шаге замены подстановки просматриваются по порядку сверху вниз, и
выполняется первая из них, которая подошла: первое найденное слово-образец рабочей строки заменяется на слово-замену.
Слова слева и справа от знака «->» могут быть (а могут и не быть) заключены
в апострофы или двойные кавычки. Следующие подстановки равносильны и определяют замену буквы «а»
на сочетание «бв»: а -> бв
'а' -> 'бв'
"а" -> "бв"
'а' -> "бв"
Левая часть (слово-образец) может отсутствовать, в этом случае слово-замена ставится в
самое начало рабочего слова. Обычно такая замена должна стоять последней в списке подстановок
(иначе происходит зацикливание).
Правая часть подстановки тоже может отсутствовать (при стирании образца).
Символ «.» после слова-замены обозначает терминальную подстановку,
после которой выполнение алгоритма заканчивается. Например: 'а' -> 'б'. заменить «а» на «б» и остановить программу * -> . стереть знак «*» и остановить программу
В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.
Система постановок, задающая нормальный алгорифм Маркова, набирается в виде таблице в нижней части окна программы.
Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться,
подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.
Задачи можно сохранять в файлах и загружать из файлов. Сохраняется условие задачи, исходное
слово и система подстановок.
Протокол работы алгоритма, в котором показаны все последовательные замены, вызывается при нажатии клавиш
Ctrl+P.
Если вы заметили ошибку или у вас есть
предложения, замечания, жалобы, просьбы и заявления, пишите.
Технические требования
Программа работает под управлением операционных систем
линейки Windows на любых современных компьютерах.
Лицензия
Программа является бесплатной для некоммерческого использования.
Исходные тексты программы не распространяются.
Программа поставляется «as is», то есть, автор не несет никакой
ответственности за всевозможные последствия ее использования,
включая моральные и материальные потери, вывод оборудования из
строя, физические и душевные травмы.
При размещении программы на других веб-сайтах ссылка на первоисточник обязательна.
Без письменного согласия автора ЗАПРЕЩАЕТСЯ
распространение неполных или измененных материалов;
включение материалов в сборники на любых носителях информации, распространяемые на коммерческой основе;
получение коммерческой выгоды от продажи или другого использования материалов.
Алгорифмы Маркова 
