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

bni Ьп2 bnk Если алгоритм в применим к слову R=A{P), то в результате его применения получили бы слово В{А{Р)), например: В{А{РУ) Cmi Cml { Cffii ^ A, 1 ). Тогда, как легко видеть, что в результате применения (8) получим ос с уп1 с yyi2 .. С yyig f5 С ms+1-•• Сml (^— ^mi ^ А, 1 ^ i ^ I) Теперь ^--кратное применение (4) приводит к слову ^ ml ^ т2 •• ^ml- Далее, применяя (5), а затем (1-1) раз (6), имеем ар Ст1 Сщ2 •• Суп арВ(А(Р)). Применяя заключительную подстановку (7), получим результат В{А{Р)). Таким образом, С{Р) = В{А{Р)), и так как слово Р было произвольным, теорема доказана. Соединение алгоритмов. Теорема 5.2. Пусть Л 7,Л 2,...,Л „-нормальные алгоритмы в алфавитах Ai,A2,---,An соответственно и пусть А - объединение этих алфавитов. Тогда существует нормальный алгоритм В над А, называемый соединением алгоритмов у47,у42,...,у4„ такой, что \tPeA: В(Р) =А,' (/'И/ (Р)..А„' (Р), где Aj - есть естественное распространение Л, на А. Теорему примем без доказательства. Доказательство см., например, в работе [21]. Разветвление алгоритмов. Пусть заданы алгоритмы Л и в в алфавите А и некоторое условие U. Тогда можно задать предписание следующего типа: для данного слова Р в алфавите А проверить, удовлетворяет ли оно условию U. Если удовлетворяет, токР применить алгоритм А , в противном случае применить к Р алгоритмД см. рис 5.2. и выполнено А(Р) В(Р) и не Проверка условия Рис.5.2. Разветвление алгоритмов Ясно, что условие U можно задавать самым различным образом, например, так: условие U выполнимо для заданного слова Р, если P^NP (см. главу о 155