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

Эта схема представляет собой сокращенную запись некоторого нормального алгоритма С (в алфавите ^ и ^ и { а , р }), причем в 1)-6) буквы а VIb означают произвольные буквы из А , а строки 8) и 9) означают, что нужно записать все подстановки сначала алгоритма В , затем алгоритма^". Покажем, что нормальный алгоритм С таков, что \/Р ъ А: С{Р)^В{А{Р)), т.е. С есть композиция Л и В. Пусть задано произвольное слово Р, например, Р = {а^,&А ) . Сначала подстановки 1)-8) не применимы к Р, ибо буквы а, Р и буквы-двойники (алгоритм записан в двойниках) не содержатся в слове Р, а таюке в 8) нет подстановок вида A-^Q, ибо они заменены на подстановки a-^aQ. Если алгоритм А не применим к слову Р (перерабатывает его бесконечно), то по 9) и С будет не применим к Р. Если А применим к Р , то в результате мы получили бы некоторое слово R = A { P ) . Пусть, например, R =b^b „^...b„^ (b„, еА ) . Известно, что алго­ ритмы А иА ' вполне эквивалентны, т.е. результаты их применения к любому слову из А совпадают. В § 5 отмечалось, что алгоритм А' всегда заканчивает переработку слова заоючительной подстановкой P j ^ Q i либо А - > » Л . Так как в А " все "в" заменены на "а", то в результате применения 9) получим, что в слове R где-то вкли­ нится буква а , т.е. имеем: b „b„ ...b„ab„ ...b,, ( g < k , b„ eA , l<i < k ) . "L "2 "(I "(4+1) "k > )J, ' J Применяя q раз подстановку 1) к последнему слову, получим После этого, применяя подстановку 2) и к-\ раз подстановку 3), придем к слову ci-Ьщ Ьп^•••Ьп), • 230