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


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

170 РЕКУРСИВНЫЕ ФУНКЦИИ
С другой стороны, из наших равенств можно вывести, что
°з(2)=4,
откуда
<р(4)=<р(а3(2))=2
и, следовательно,
<р(3)=а15(3,2).
Значение о16(3, 2) вычисляется, далее, из определяющих равенств и подставляется в о15 (2, <р (3)) вместо <с (3). Подсчитав значение полученного таким способом выражения, мы получим искомое значение <р (2).
Шагами вычисления являются подстановка чисел вместо переменных определяющих равенств и замена части равенства эквивалентным выражением.
5. Теперь мы можем сформулировать понятие обще-рекурсивной функции1). Числа, переменные и п+1 назовем «термами». Далее, назовем «термами» все выражения, получающиеся из определяемых вспомогательных функций б/(о1,...,а|.) и определяемой функции <с (а^,...,аг) подстановкой термов на места их переменных. Равенство между термами, в которое входят какие-либо может быть получено из указанной системы конечным числом применений следующих двух операций:
1) подстановка чисел вместо переменных;
2) переход от выражения а и выражения вида 6= с к выражению, получающемуся из а заменой в одном или нескольких местах b на 1.
Здесь нигде не требуется, чтобы значение функции строилось с помощью ее значений в предыдущих точках. Нигде не требуется также, чтобы участвующие в построении (р вспомогательные функции были всюду вычислимы [вспомним, что вычислимость введенной в предыдущем параграфе функции К(п), гёделезирую-щей вычисление изучаемой там функции <|> (т, п), была необходима не всюду, а лишь для точек, являющихся значениями функ-
1) Эрбран [1], § 2, группа аксиом С; Гёдель [2]; Клин [1] и [5], I, п. 2.

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 171 172 173 174 175 176 177 178 179 180 190 200 210 220 230 240 250 260


Математика