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


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

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
где f и g — ранее определенные функции, является лишь частным слунаем рекурсивных определений. Однако в первых параграфах книги показывается, что повторное применение этой схемы и подстановок позволяет из одной- единственной исходной функции
о0(п)=п+1
построить все наиболее употребительные арифметические функции. Пример функции, ке принадлежащей к получаемому таким образом классу примитивно-рекурсивных функций, дается только в § 9, Такого рода функция двух переменных ф (т, п) получается из
«КО, п)=в0(я)=л+1 «двойной рекурсией» по формулам
0)=ф(т, 1),
После того как выяснена (при помощи приведенного сейчас примера) недостаточность «примитивной» рекурсии, в §§ 10 — 15 обсуждаются разнообразные варианты более общих типов рекурсивных определений. Все эти варианты, однако, естественным образом объединяются в определении обще-рекурсивной функции, приведенном в п. 5 § 16. Произвольная обще-рекурсивная функция получается из исходной функции <з0(п)=п +1 при помощи некоторой «системы соотношений». Для точного понимания смысла определения обще-рекурсивной функции читатель должен уяснить себе формальный смысл терминов «терм», «соотношение» (два терма, соединенных знаком равенства) и «подстановка». При образовании термов употребляются функциональные знаки <р и о,. Однако, по формальному смыслу определения, только со знаком if следует связывать представление о функции в реальном понимании этого термина, и то только тогда, когда в заключительной" стадии определения выдвигается требование, чтобы для любых фиксированных пг, nz,...,nr значение m=y(nv л2,..., пг) могло быть «вычислено» при помощи изложенных в определении правил. В процессе же этого вычисления знаки <р и о( являются лишь оперативными 'символами, с которыми вычисляют по определенным правилам. Что касается знаков at, то им может и не соответствовать никакой реальной функции: не требуется ни того, чтобы e,(nv n2,..., ns) могло быть вычислено при любых фиксированных п1? л2,..., ns, ни того, чтобы в процессе вычислений была исключена возможность получения противоречивых равенств.
Например, система соотношений
п-И = 1, <р(п)=0
в соответствии со строгим смыслом определения может служить определяющей системой соотношений для функции ?(л), равной

 

1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260


Математика