Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Петер Р.N. Рекурсивные функции
 
djvu / html
 

160 РЕКУРСИВНЫЕ ФУНКЦИИ
номером ^"(п), то гёделевский номер так построенного выражения будет определяться равенством
T'"(«)=Subst,(n)
Наконец, надо выражение i'" включить на место 5^ (а, Ь, t) в рассматриваемое выражение с номером п. Подвыражение Bx.^a,b, t), как это не раз отмечалось, начинается [х(п)]-м и кончается [x(n) -j-+6-fX(n)+l]-M знаком. Поэтому гёделевский номер выражения, получаемого в результате указанного включения, равен
21. Пусть мы пришли к такому содержащему В выражению, в котором нет части, начинающейся знаками Вх(а,Ь,..., но зато есть часть вида а^ай-..,-аг, где все at—числа и г^>1. В силу п. 7, перше такое подвыражение (в интересующих нас случаях оно, как легко видеть, вообще единственно) следует заменить вычисленным его значением (после чего, как легко видеть, в интересующих нас случаях получается выражение, уже содержащее часть, начинающуюся знаками Вх.(а, Ь, ... , где а и Ь—числа).
Пусть гёделевский номер рассматриваемого выражения равен п. Наше условие можно записать в следующем виде. Прежде всего, согласно п. 14, (?/) [i0 & ехр, (п)= 1 ].
Пусть, далее, т есть гёделевский номер произведения нескольких чисел. Тогда показатели простых делителей числа т равны либо 3, либо четным положительным числам. Введем примитивно-рекурсивную функцию
{], если для всех / таких, что ехр,-(т)>0, значением ехрДт) служит либо 3, либо четное число; О в противном случае.
(Среди строчек, выделяемых этой функцией, содержатся и строчки, не имеющие смысла: например, строчка, состоящая сплошь из знаков умножения. В интересующих нас случаях это, однако, невозможно.)
Пусть п есть гёделевский номер рассматриваемого выражения, содержащего В. Утверждение, что эта строчка содержит произведение нескольких чисел, можно сформулировать следующим образом:

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 161 162 163 164 165 166 167 168 169 170 180 190 200 210 220 230 240 250 260


Математика