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


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

260 СОДЕРЖАНИЕ
некоторой функции <р (т, я). 6. Определение [функции <р (т, п) является двукратной рекурсией со вставками; тем самым еще раз доказывается, что такая рекурсия выводит за пределы класса примитивно-рекурсивных функций. 7. Аналогично определяется некоторан (г + 2)-местная функция, которая совпадает с произвольной (г + 1)-местной примитивно-рекурсивной функцией при надлежащем значении первого аргумента. 8. Применение диагонального метода к А-рекурснвным функциям показывает, что (k + 1)-кратная рекурсия выводит за пределы класса fe-рекурснв-иых функций.
§ 12. Трансфинитные рекурсии.................... НО
1. Ограничение при определении многоместных функции однократными рекурсиями было бы в значительной степени произвольным. 2. Естественным упорядочением наборов значений аргументов ^-местной функции является упорядочение по типу ш*. 3. Упорядочение чисел по типу <вг. 4. Характеристические свойства «характеризующих функций» этого упорядочения. 5. Транс-фнинтная рекурсия. Пример рекурсии типа «в*. 6. Пример вычисления значений функции .с помощью ее значений в последующих точках. Значение функции, определенной трансфииитной рекурсией, может быть вычислено в конечное число шагов. 7—8. Рекурсию типа <о2 можно свести к обычной двукратной рекурсии. При этом используется то, что схема примитивной рекурсии однозначно задает определяемую функцию. 9. Обратно, двукратную рекурсию можно свести к однократной рекурсии типа «в2. 10. Упорядочение чисел по типу <в3 и, как продолжение того же метода, упорядочение по типу «в* и по типу ш™. 11. Обычные ft-кратные рекурсии и трансфинитиые рекурсии типа ш* сводятся друг к другу. Многократные трансфинитные рекурсии также допускают сведение к однократным трансфинитным рекурсиям. 12. Одна особенность трансфинитных рекурсий: здесь и определевие одноместной функции может быть со .вставками, причем без этих вставок нельзя, вообще говоря, обойтись. 13. Диагональный метод в применении к трехместным многократно-рекурсивным функциям показывает, что рекурсия типа <вш выводит за пределы класса многократно-рекурсивных функций.
§ 13. Рекурсии высших ступеней.................. 126
1. Итерация как функция от функций. Сведение двукратной рекурсии, определяющей начинающуюся с произведения итерацию, к однократным рекурсиям, использующим функциональные переменные. 2. Простейшая функция от функций: Vv (п, {(х)) = / (п). 3. Рекурсии и рекурсивные функции высших ступеней. 4. Все двукратные рекурсии перной ступени можно свести к двум однократным рекурсиям второй ступени. 5. Проведение строгого до-

 

1 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 261 262 263


Математика