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

Марков Андрей Андреевич (родился в 1903г.), известный русский математик и логик, зав. Кафедрой математической логики МГУ, с 1936 года работал в Математическом институте Академии Наук СССР. Член-корреспондент Академии Наук СССР (с 1953 года). Известен своими работами в области теории алгоритмов. Предложенное им понятие нормального алгорифма явилось крупным вкладом в мировую математическую науку. Ему принадлежит четкое определение таких понятий, как абстракция отождествления и абстракция потенциальной осуществимости. А.А. Марков – основоположник конструктивного направления в математике и математической логике.

Алфавитом называется множество из конечного числа различных символов. Слово в данном алфавите определяется как горизонтальный ряд конечного числа букв этого алфавита. Например, если задан алфавит {a, b}, слова в этом алфавите: a, b, abba, bbba…

Слово без букв – пустое слово. Пустое слово есть в каждом алфавите.

Понятие вхождения слова P в данное слово: слово Р входит в данное слово R, если слово R имеет вид: R₁PR2 (R₁ и R₂ могут быть пустыми словами).

Пример. Пусть в алфавите {a, b} имеем слово R = abaabab, P = ba

R имеет вид R₁PR₂, где R₁ – пустое слово, R₂ – abab;

R₁ = aba, R₂= b

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

Пример. Заменить слова ba в слове aababab на слово а. Результатом будет слово aaaabab.

Если первое вхождение пустого слова в любое слово R заменить на некоторое слово Q, получится слово QR.

Определение1. Обычной формулой подстановки в алфавите А называется слово P  Q где P и Q – слова в алфавите А.

Заключительной формулой подстановки называется слово:

P  Q , где P и Q – слова в алфавите А.

Конечная непустая упорядоченная система подстановок:

Называется нормальной схемой в алфавите А,

где k 1, a_i = { , пустое слово}, P_iQ_i – слова в алфавите А, i =1, k.

Нормальный алгорифм над алфавитом А (н.а.) задается конечным алфавитом В, не содержащим { ,  } и включающим в себя А или совпадающим с А (BA) и нормальной схемой в алфавите В.

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

R, R₁, R₂, R₃, …R_i, R_i+1… (*)

Слово R_i+1 получается из предыдущего слова R_i следующим образом:

просматривается нормальная схема алгорифма, из неё выбирается самая верхняя формула, левая часть которой входит в слово R_i. Пусть это формула P_j  a_jQ_j, a_j {, _}

первое вхождение в слово R_i заменяется на слово Q_i, что и даёт слово R_i+1.

Работа н.а. над словом заканчивается в двух случаях:

существует такое слово R_i , что слово R_i+1 получается из с помощью заключительной формулы подстановки. В этом случае результатом н.а. над словом работы – слово R_i+1

Существует R_j из (*), что ни одна левая часть формул подстановок из нормальной схемы не имеет вхождений в слово R_j. Результат работы н.а.– слово R_j.

В остальных случаях работа н.а. над словом не заканчивается, а последовательность (*) будет бесконечной. Говорят, что данный н.а. неприменим к слову R.

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