Определение и функционирование нормального алгоритма

Вначале рассмотрим понятие марковской подстановки.

Марковской подстановкой называется операция над словами a,b,g заключающаяся в следующем. В исходном слове g ищется самое левое вхождение слова a, и если оно существует, a заменяется на b в слове g. Полученное слово g’ является результатом применения марковской подстановки к слову g. Если слово a не входит в слово g, то говорят, что данная марковская подстановка неприменима к слову g.

Марковская подстановка обычно записывается следующим образом:

a®b

Подчеркнем, что длины слов a и b могут в общем случае не совпадать. При этом длина g’ будет отлична от длины слова g. В частном случае длина слова a или слова b (или обоих) может быть равна нулю, соответствующее слово является пустым. В марковских подстановках пустое слово никак не обозначается и не занимает никакого места (в отличие от машин Тьюринга, где пустой символ занимает ячейку на ленте и обозначается буквой l). В любом слове a имеется несколько вхождений пустого слова: перед первой буквой, после последней и между каждой парой букв внутри слова. Так, в слове abcd имеется 5 вхождений пустого слова.

Если в марковской подстановке a®b слово a - пустое (подстановка записывается ®b), то слово b приписывается слева к слову g. Если пустым является b (записывается a®), то слово a исключается из g (при этом пробелы не ставятся).

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

Слово g Подстановка Слово g’

1111 1®0 0111

космонавт навт®с космос

авссваавс сс®в аввваавс

аллгоритм л® алгоритм

zxyz zxyz®

54321 ®76 7654321

01011 ® 01011

alpha x®y подстановка неприменима

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

a®.b

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

Выполнение нормального алгоритма происходит следующим образом:

1. N:=1 (номер подстановки в схеме);

2. Выбирается N- я подстановка;

3. Левая часть подстановки a ищется в преобразуемом слове;

4. Если a найдено, то переход к пункту 7, иначе к пункту 5;

5. N:=N+1;

6. Если N не превышает общего числа подстановок, то переход к пункту 2, иначе конец;

7. Выполняется замена a на b в преобразуемом слове;

8. Если выполненная подстановка является заключительной, то конец, иначе – переход к пункту 1.

Следует подчеркнуть два момента в работе марковского алгоритма:

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

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

Теперь рассмотрим основное понятие - нормальный алгоритм над алфавитом А.

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

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

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

Соответствие между нормальными алгоритмами над алфавитом А и алгоритмами в интуитивном смысле выражает принцип нормализации – аналог тезисов Черча и Тьюринга:

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

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

Дата добавления: 2014-01-07