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

алгоритм, позволяющий вычислить значение (p(xi,x2,...,xn) для любых совокупностей значенийXi,X2,...д„. В предыдущем параграфе показано, что для всюду определенных арифметических функций f(x)=0, \/х(хЩ, f(x)=x+l, Vx(x^) существуют нормальные алгоритмы, вычисляющие их значения (примеры 3, 4). Следовательно, эти функции являются вычислимыми по Маркову. § 5. Замыкание, распространение нормального алгоритма Пусть У 4 - произвольный нормальный алгоритм в алфавите^: \Pi А Р\ {*)Qi P i ( ' f e Pyi ('tew его замыканием считается А'- Р2 (•& Pyi ( •tew Известно, что любой нормальный алгоритм заканчивает процесс переработки слова либо после применения заключительной подстановки, либо если все слова Р1,Р2,Рз,---, Рп не содержатся в слове, полученном при предыдущем шаге. Подстановка Л—>»Л применима к любому слову. Следовательно, алгоритм А' заканчивает переработку слов всегда по заключительной подстановке, которая есть, либо некоторая из подстановок Pi^(*)Qi (l<i<n) либо Л^»Л. Отметим, что подстановка добавленная к А для получения А', стоит последней. Поэтому эта подстановка будет применяться только тогда, когда неприменимы все подстановки алгоритма Л, причем применение Л-^»Л к любому слову не изменяет этого слова. Следовательно, результаты применения алгоритмов У 4 и У 4* к любому слову в А будут совпадать, т.е. алгоритмы Л и Л* вполне эквивалентны. Пусть А - нормальный алгоритм в алфавите Ai, а алфавит А2 является расширением ^^7, т.е. AjcA2. Тогда можно рассмотреть нормальный алгоритм Л в алфавите ^2 с той же схемой, что и А . Очевидно, \/Р в алфавите^у: AfFJ =А*(Р), (5.1) М Jt т.е. А Ж А вполне эквиваленты относительно AJ. Нормальный алгоритм А будем называть естественным распространением А на алфавит J1 В некоторых случаях удобнее, чтобы алгоритм Л , удовлетворяющий (5.1), был неприменим к тем словам ъ А2, которые не являются словами ъ Ai. Этого легко достигнуть, приписав к схеме А сверху формулу вида где х - любая 152