Функционирование НАМ

1. , – номер подстановки в схеме НАМ.

2. Выбирается -тая МП, пусть она имеет вид

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

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

5.

6. Если не превышает общего числа подстановок, то переход к пункту 2, иначе – алгоритм заканчивает работу, останавливается.

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

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

После применения подстановки осуществляется заново просмотр столбца подстановок, а не продолжается просмотр .

Процесс заканчивается, если:

- не найдена применяемая подстановка;

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

Алфавит называется расширением алфавита , если .

Нормальный алгоритм над алфавитом – это нормальный алгоритм в алфавите , который слова в , если он к ним применим, перерабатывает в слова в . Нормальный алгоритм в может использовать только буквы алфавита .

Нормальный алгоритм над может использовать вспомогательные символы. НАМ над более мощные, чем НАМ в А.

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

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

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

Пусть Тогда, последовательность преобразований имеет вид:

Пример 2. Нормальный алгоритм над алфавитом стирающий все символы входного слова до первого символа включительно.

Здесь вспомогательные символы и , таким образом, алфавит . Буква служит для того, чтобы найти букву 2 последовательным перебором слева направо. Буква позволяет стереть буквы движением справа налево.

Пример функционирования НАМ по переработке слова :

Пример 3. Нормальный алгоритм над алфавитом , который выдает “и”, если в исходном слове, состоящем из нулей и единиц, есть комбинация , и “л”, в противном случае.

Приведем два примера функционирования НАМ:

1)

2)

Пример 4. Пример НАМ, который работает бесконечно.