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

то к Р применить алгоритм А , в противном случае применить к Р алгоритм Б (рис 6.2). Ясно, что условие U можно задавать самым различным образом, например, можно задать так: условие U выполнимо для заданного слова Р, если P ^ N P (см. главу о сложности вычислений). Решить, выполнимо это условие U или нет, в настоящее время нельзя, ибо указанная проблема еще не решена, несмотря на настойчивые попытки' Поэтому такого рода (типа) условия не будем рассмат­ ривать. Будем считать, что условие U всегда задано с помощью какого-то алгоритма С в алфавите А в следующем виде; условие и для слова Р выполнено, если С { Р ) = Л , условие {/для словаР не выполнено, если С { Р ) ^ Л . Проверка условия и и выполнено и не выполнено А{Р) В(Л Рис,6.2. Разветвление алгооитмов При таком задании условия U описанное предписание будем считать разветвлением алгоритмов в алфавите А . Точнее, пусть А , В и С - алгоритмы в алфавите А. РазветвлениемалгоритмовА я В называется алгоритм УъА,не применимый к Р, если не применим к Р алгоритм С и такой, что ' \В[Р),есшС{р)=АА. Будем говорить, что это разветвление алгоритмов у п р а в л я е т с я алгоритмом С. 232