Математическая логика и теория алгоритмов

Теорема 6.3. Разветвление нормальных алгоритаов, управляемое нормальным алгоритмом, является нормальным алгоритмом. Примем без доказательства. Доказательство можно найти, например, в работе [21]. Повторение алгоршпмов. Во многих случаях требуется повторить одну и ту же процедуру многократно, каждый раз применяя ее к результату, полученному на предыдущем шаге. Процедуру повторяем до выполнения некоторого условия U . Будем считать, что условие и задается с помощью алгоритма, как и ранее. Такая процедура будет задавать повторение алгоритма. Более точно: пусть и С - алгоритмы в алфавите ^ и Ро - произвольное слово в А. Применим к Ро алгоритм Л. Получим некоторое слово P\=A{PQ), если C(PI)-A, то процесс заканчивается. Если C(PI)^A, то к Р\ применяем А, получаем Р2=Л{РIY=A{A(P!^). Если С{Р2)-А, то процесс заканчи­ ваем. Если С{Р'2)ФА, ТО К PI применяем А и т.д. Определенный таким образом алгоритм называется повторениемалгоритма А, управляя- емым алгоритмом С. Повторение алгоритма можно представить блок-схемой, показанной на рис. 6.3. р А PrAiP^.,) Проверка условия и и выполнено и не выполнено ' • Рис. 6.3. Повторение алгоритмов Также без доказательства примем следующую теорему. 233