Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

сложности вычислений). Решить, выполнимо это условие U или нет, в настоящее время нельзя, ибо указанная проблема еще не решена, несмотря на настойчивые попытки. Поэтому такого рода (типа) условия не будем рассматривать. Будем считать, что условие U всегда задано с помощью какого- то алгоритма С в алфавите^ в следующем виде: условие и для слова Р выполнено, если С(Р) =Л, условие и для слова Р не выполнено, если С(Р)^Л. При таком задании условия U описанное предписание будем считать разветвлением алгоритмов в алфавите А. Точнее, пусть Л, в и С-алгоритмы в алфавите^. Разветвлением алгоритмов А и В называется алгоритм V в А, неприменимый к Р, если алгоритм С неприменим к Р и такой, что Будем говорить, что это разветвление алгоритмов управляется алгоритмом С. Теорема 5.3. Разветвление нормальных алгоритмов, управляемое нормальным алгоритмом, является нормальным алгоритмом. Примем без доказательства. Доказательство см., например, в работе [21]. Повторение алгоритмов. Во многих случаях требуется повторить одну и ту же процедуру многократно, каждый раз применяя ее к результату, полученному на предыдущем шаге. Процедуру повторяем до выполнения некоторого условия U. Будем считать, что условие U задается с помощью алгоритма, как и ранее. Такая процедура будет задавать повторение алгоритма. Более точно: пусть Л и С - алгоритмы в алфавите Avi.Po- произвольное слово в А. Применим к Ро алгоритм А. Получим некоторое слово Pi=A(Po), если C(Pi)=A, то процесс заканчивается. Если C(Pi)^A, то к Р] применяем А, получаем P2=A(Pi)=A(A(Po)). Если С (Р2 )=А, то процесс заканчиваем. Если С ( Р2)^ А , ТО К Р2 применяем А и т.д. Определенный таким образом алгоритм называется повторением алгоритма А, управляемым алгоритмом С. Повторение алгоритма можно представить следующей блок схемой, см. Также без доказательства примем следующую теорему. Теорема 5.4. Повторение нормального алгоритма, управляемое нормальным алгоритмом, есть нормальный алгоритм. Основным и важнейшим результатом этого параграфа является то, что различные операции (комбинации) над нормальными алгоритмами снова приводят к нормальному алгоритму. если если Рис. 5.3. 156