Третий тип алгоритмических моделей.

Теория нормальных алгоритмов была разработана советским математиком

Марковым в конце 1940-х — начале 1950-х гг. XX в. Эти алгоритмы представляют собой некоторые правила по переработке слов в каком-либо алфавите, так что исходные данные и искомые результаты для алгоритмов являются словами в некотором алфавите.

Марковские подстановки.

Алфавитом называется любое непустое множество. Его элементы называются буквами, а любые последовательности букв — словами в данном алфавите. Допускаются пустые слова. Пустое слово будем обозначать Λ.

Если А и B — два алфавита, причем А B то алфавит В называется расширением алфавита А.

Если слово является составной частью другого слова, то оно называется подсловом.

Определение. Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (Р, Q), состоящая в следующем. В заданном слове R находят первое вхождение слова Р (если таковое имеется) и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q. Полученное слово называется результатом применения марковской подстановки (Р, Q) к слову R. Если же вхождения Р в слово R нет, то считается, что марковская подстановка (Р, Q) неприменима к слову R.

Частными случаями марковских подстановок являются подстановки с пустыми словами: (Λ, Q), (Р, Λ), (Λ,Λ).

Для обозначения марковской подстановки (Р, Q) используется запись Р —> Q. Она называется формулой подстановки (Р, Q). Некоторые подстановки (Р, Q) будем называть заключительными. Для обозначения таких подстановок будем использовать запись Р —>. Q, называя ее формулой заключительной подстановки. Слово Р называется левой частью, a Q — правой частью в формуле подстановки.

Пример (с49).

Нормальные алгоритмы и их применение к словам.

Упорядоченный конечный список формул подстановок (с50)

в алфавите А называется схемой нормального алгоритма в А. (Запись точки в скобках означает, что она может стоять в этом месте, а может отсутствовать.) Данная схема определяет (детерминирует) алгоритм преобразования слов, называемый нормальным алгоритмом Маркова.

Нормальным алгоритмом (Маркова) в алфавите А называется следующее правило построения последовательности Vi слов в алфавите А, исходя из данного слова V в этом алфавите. В качестве начального слова V0 последовательности берется слово V. Пусть для некоторого i >= 0 слово Vi построено и процесс построения рассматриваемой последовательности еще не завершился.

При этом, если в схеме нормального алгоритма нет формул, левые части которых входили бы в Vi , то Vi+1 полагают равным Vi, и процесс построения последовательности считается завершившимся, если же в схеме имеются формулы с левыми частями, входящими в Vi, то в качестве Vi+1, берется результат марковской подстановки правой части первой из таких формул вместо первого вхождения ее левой части в слово Vi. Процесс построения последовательности считается завершившимся, если на данном шаге была применена формула заключительной подстановки, и продолжающимся — в противном случае.

Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгоритм применим к слову V. Последний элемент W последовательности называется результатом применения нормального алгоритма к слову V. Говорят, что нормальный алгоритм перерабатывает V B W.

Последовательность Vi, будем записывать следующим образом:

V0 => V1 => V2 => ... => Vm-1 => Vm,

где V0 = V и Vm = W.

Пример (с51)

Нормально вычислимые функции и принцип нормализации Маркова.

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

Рассмотрим два примера. (с51)

(с 52)

Таким образом, рассмотренный алгоритм реализует (или вычисляет) данную функцию.

Сформулируем теперь точное определение такой вычислимости функций. (с53)

Определение. Функция f, заданная на некотором множестве слов алфавита А, называется нормально вычислимой, если найдется такое расширение B данного алфавита (А В) и такой нормальный алгоритм в В, что каждое слово V (в алфавите А) из области определения функции f этот алгоритм перерабатывает в слово f (V).

В предыдущих двух примерах заданы нормально вычислимые функции, причем алгоритмы построены в том же самом алфавите т.е. В=А.

К пустому слову данный алгоритм не применим (получаем бесконечную последовательность) правило Λ→а

Λ=>a =>аа => ааа => аааа =>...

Если применить теперь алгоритм к слову 499, получим следующую последовательность слов:

499 => a499 (применена последняя формула) => 4a99 (формула из середины второго столбца) => 49а9 => 499b (дважды применена формула из конца второго столбца) => 499b (предпоследняя формула) => 49b0 => 4b00 (дважды применена предпоследняя формула первого столбца) => 500 (применена формула из середины первого столбца).

«Принцип нормализации Маркова».

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

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

Следующие классы функций (заданных на натуральных числах и принимающих натуральные значения) совпадают:

а) класс всех функций, вычислимых по Тьюрингу,

б) класс всех частично рекурсивных функций;

в) класс всех нормально вычислимых функций.