Операции над нормальными алгоритмами

Композиция алгоритмов. Пусть A и B два алгоритма в алфавите А. Композицией алгоритмов A и B в алфавите А называют алгоритм C такой, что

Таким образом, композиция алгоритмов A и B представляет собой алгоритм, получающийся в результате последовательного применения алгоритмов к заданному слову Р, что можно продемонстрировать следующей блок-схемой

Композиция алгоритмов A и B обозначается как:

Пусть A ₁, A ₂,..., A _n - алгоритмы в алфавите А, тогда под A_n°A_n-1°... °A₁ будем понимать следующее: A_n°(A_n-1°(...°(A₃°(A₂°A₁))...)).

Теорема 1. Композиция нормальных алгоритмов A₁,A₂,...,A_n в алфавите А есть снова нормальный алгоритм (над алфавитом А).

Теорема 2. Пусть A₁,A₂,...,A_n - нормальные алгоритмы в алфавитах A₁,A₂,...,A_n соответственно и пусть А - объединение этих алфавитов. Тогда существует нормальный алгоритм B над А, называемый соединением алгоритмов A₁,A₂,...,A_n, такой, что

где есть естественное распространение A _i на А.

Разветвление алгоритмов. Пусть заданы алгоритмы A и B в алфавите А и задано некоторое условие U. Тогда можно задать предписание следующего типа: для данного слова Р в алфавите А проверить, удовлетворяет ли оно условию U, если удовлетворяет, то к Р применить алгоритм A, в противном случае применить к Р алгоритм B.

Будем считать, что условие U всегда задано с помощью какого-то алгоритма C в алфавите А в следующем виде:

условие U для слова Р выполнено, если C(Р)=Λ,

условие U для слова Р не выполнено, если C(Р)≠Λ.

При таком задании условия U описанное выше предписание будем считать разветвлением алгоритмов в алфавите А. Точнее, пусть A, B и C -алгоритмы в алфавите А. Разветвлением алгоритмов A и B называется алгоритм V в А, не применимый к Р, если не применим к Р алгоритм С и такой, что`

.

Будем говорить, что это разветвление алгоритмов управляется алгоритмом C.

Теорема 3. Разветвление нормальных алгоритмов, управляемое нормальным алгоритмом, является нормальным алгоритмом.

Повторение алгоритмов. Во многих случаях требуется повторить одну и ту же процедуру многократно, каждый раз применяя ее к результату, полученному на предыдущем шаге. Процедуру повторяем до выполнения некоторого условия U. Будем считать, что условие U задается с помощью алгоритма, как и выше. Такая процедура будет задавать повторение алгоритма. Более точно: пусть A и C - алгоритмы в алфавите А и пусть Р_о- произвольное слово в А. Применим к Р_оалгоритм A. Получим некоторое слово Р₁= A (Р_о), если С (Р₁)=Λ, то процесс заканчивается. Если C (Р₁)≠Λ, то к Р₁применяем A, получаем Р₂= A (Р₁)= A (A (Р_о)). Если C(Р₂)=Λ, то процесс заканчиваем. Если C(Р₂)≠Λ, то к Р₂применяем A, и т.д. Определенный таким образом алгоритм называется повторением алгоритма A, управляемым алгоритмом C.

Повторение алгоритма можно представить следующей блок схемой

Теорема 4. Повторение нормального алгоритма, управляемое нормальным алгоритмом, есть нормальный алгоритм.

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