5. Содержание работы

Запустить программу-эмулятор машины Тьюринга. Ознакомиться с работой эмулятора и набором команд. Воспроизвести (не сохраняя в файл) предложенные выше примеры. По указанию преподавателя выбрать варианты из папки \..Exampleпрограммы-эмулятора, а, также вариант из Приложения Ж. По завершении работы результаты сохранить в файл.

6. Требования к отчету

Отчет должен содержать:

• название работы, постановку задачи и сведения о последовательности её выполнения;

• скриншот работающей программы (результаты работы);

• ответы на контрольные вопросы из Приложения Б, указанные преподавателем.

7. Изучение нормальных алгоритмов Маркова

Цель занятия – изучение особенностей нормальных алгоритмов Маркова на программном эмуляторе, решение задач по реализации простых программ.

Объем занятия – 2 часа.

1. Общие сведения

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

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

2. Принцип работы

Описание нормальных алгоритмов.Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах.

Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам, из символов которого алгорифм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида , гдеи– два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида, гдеи– два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквыине принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

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

Процесс применения нормального алгорифма к произвольному слову в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть– слово, полученное на предыдущем шаге работы алгорифма (или исходное слово, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в, то работа алгорифма считается завершённой, и результатом этой работы считается слово. Иначе среди формул подстановки, левая часть которых входит в, выбирается самая первая. Если эта формула подстановки имеет вид, то из всех возможных представлений словав видевыбирается такое, при котором– самое короткое, после чего работа алгорифма считается завершённой с результатом. Если же эта формула подстановки имеет вид, то из всех возможных представлений словав видевыбирается такое, при котором– самое короткое, после чего словосчитается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.

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

Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот – любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Варианттезиса Чёрча-Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».

Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования – например, в языкеРефал.