Примитивно и частично рекурсивные функции (вопросы)

[Rif]

1. Напомню стандартное определение (см. напр. Мальцев Алгоритмы и рекурсивные функции): функция, полученная из функций нуль-, следования и проектирования при помощи конечного числа операторов подстановки, рекурсии (и минимизации) называется примитивно (частично) рекурсивной функцией. Оператор минимизации необходим для построения даже всюду определенных рекурсивных функций. Необходим ли оператор рекурсии в определении частично рекурсивных функций (ЧРФ)?
2. Двукратной рекурсией определяется функция Аккермана. Она частично, но не примитивно рекурсивна. Через ПР(к) обозначим класс всех функций, определимых при помощи рекурсий кратности не больше к. Совпадает ли объединение всех ПР(к) с классом всех ЧРФ?
3. Все вычислимые функции можно перенумеровать (рекурсивной функцией): Ф(к). Тогда определяется всюду определенная функция Ф(х), равная Ф(х)(х)+1, если Ф(х)(х) определенная, и 0 в противном случае. Эта функция отлична от любой функции Ф(к). Относительно функции Ф говорят: невычислима; вычислима в каком-то высшем порядке; противоречива, поэтому оператор рекурсии должна быть применима не только к всюду определенным функциям. Прокомментируйте следующее объяснение: к основным чертам понятия вычислимой функции относится не только требование конечного числа не только используемых операторов, инструкций и т.д, но и требование конечного числа функций, участвующих в построении метода вычисления данной функции.
(Вместо функции Ф можно рассмотреть и частичную функцию Ф(х), равную 0, если Ф(х)(х) определенная, и неопределенная в противном случае.[/i][/math]

переместил из дискуссионных // нг

[маткиб]

Цитата:

Необходим ли оператор рекурсии в определении частично рекурсивных функций (ЧРФ)?

ДА
Например, при построении функций из 0, x+1 с помощью только суперпозиции и минимизации будет сохраняться следующий инвариант:
построенную функцию f(x1,...,xn) можно доопределить до функции, существенно зависящей не более, чем от одной переменной.
Кроме того, эта функция от одной переменной g(x) равна x+a (а - целое число) везде, кроме, быть может, конечного числа точек.

Цитата:

Совпадает ли объединение всех ПР(к) с классом всех ЧРФ?

НЕТ
Как минимум потому, что ПР(k) состоит только из всюду определённых рекурсивных функций (РФ). Но и с классом всех РФ это объединение не совпадает, потому что не существует языка программирования, на котором можно реализовать все РФ и только их, а для объединения ПР(k) такой существует.

Цитата:

3. Все вычислимые функции можно перенумеровать (рекурсивной функцией): Ф(к). Тогда определяется всюду определенная функция Ф(х), равная Ф(х)(х)+1, если Ф(х)(х) определенная, и 0 в противном случае. Эта функция отлична от любой функции Ф(к). Относительно функции Ф говорят: невычислима; вычислима в каком-то высшем порядке; противоречива, поэтому оператор рекурсии должна быть применима не только к всюду определенным функциям. Прокомментируйте следующее объяснение: к основным чертам понятия вычислимой функции относится не только требование конечного числа не только используемых операторов, инструкций и т.д, но и требование конечного числа функций, участвующих в построении метода вычисления данной функции.
(Вместо функции Ф можно рассмотреть и частичную функцию Ф(х), равную 0, если Ф(х)(х) определенная, и неопределенная в противном случае.

Не понял. Полученная диагональная функция будет невычислима. Для вычислимости существует конкретное определение, основанное на конечном числе функций и операций. Есть тезис Чёрча-Тьюринга, который говорит, что оно соответствует реальной вычислимости. Этот тезис имеет корень в законах физики.
А твоими рассуждениями можно показать, что нельзя строго зафиксировать понятие "определимость в математике" даже для функций на множестве натуральных чисел. Ибо если мы зафиксировали это понятие, то мы можем таким вот образом построить диагональную функцию Ф(x), она не будет являться "определимой" в этом формальном смысле, но тем не менее мы её как-то определили (описали).

[Rif]

1. Не подскажете инвариант, сохраняющийся для нуля, следования, проектирования,, суперпозиции и минимизации, но не рекурсии.
2. Не укажете ли где найти описания программы, описывающей рекурсии от любого числа переменных и только их.