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


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

J50 ... РЕКУРСИВНЫЕ ФУНКЦИИ
а=9; если же ОФО, мы заменяем его на результат подстановки в t (Xi) на место xt выраженля
Здесь I' (л^) получается из t (x^ переименованием всех переменных, кроме Х[. Это переименование можно осуществить следующим образом. Пусть наибольший из индексов переменных, встречающихся в t(j^), есть w. В таком случае заменим каждое (кроме х^ переменное Xj, входящее в t (xt), переменным xj+w.
7. Пусть в процессе преобразований мы пришли к такому содержащему В выражению, которое не содержит части, начинающейся с Вх (а, &,..., где а и Ь — числа, но содержит подвы-
ражение вида a^a^-...-а,., где все сомножители являются числами. Тогда это произведение замещается своим вычисленным значением.
8. В результате конечного числа таких шагов мы получаем произведение численных множителей. Это произведение вычисляется, и мы получаем, наконец, численное значение ф (т, п).
... 9. С помощью конечного числа шагов, описанных в предыдущих пунктах, мы всегда достигнем цели. Действительно, «выра-йсение» для ф (0, я) имеет вид
2-п,
т. е. при любом п является произведением численных множителей. "Мы получим требуемое значэние, если поступим, как указано в п. 8. Пусть, далее, при некотором т и произвольном п мы уже 'умеем вычислять значение «выражения» для <]) (т, п). Тогда значе-'ние выражения, соответствующего <ь(т+1,п), можно при произвольном п вычислять следующим образом. '. Запишем равенство
<|> (т+1, п)=Вх (т, п, <|> (т, х)).
"Мы получим «выражение» для ф (т+1, п), если подставим сюда •вместо ф (т, х) соответствующее «выражение» (строящееся при яГ>0 посредством суперпозиций из В-выражений), которое для краткости обозначим через ф* (т, х). Принимая во внимание определение В, получим последовательно
Вх (т, п, ф* (т, ж))=ф* (т, Вх (т -1 , п, ф* (т, х)))=
= ф* (т, ф* (т, Вх (т -2, я, f (т, *))))= . . .= m раз
- ф* (т, ф* (m,...,f(m; Вх (0, п, ф* (т, х))),...))= m-f 1 раз
= f (т, * («, f (т, я)),...))-

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 151 152 153 154 155 156 157 158 159 160 170 180 190 200 210 220 230 240 250 260


Математика