Цитата:
Необходим ли оператор рекурсии в определении частично рекурсивных функций (ЧРФ)?
ДА
Например, при построении функций из 0, x+1 с помощью только суперпозиции и минимизации будет сохраняться следующий инвариант:
построенную функцию f(x1,...,xn) можно доопределить до функции, существенно зависящей не более, чем от одной переменной.
Кроме того, эта функция от одной переменной g(x) равна x+a (а - целое число) везде, кроме, быть может, конечного числа точек.
Цитата:
Совпадает ли объединение всех ПР(к) с классом всех ЧРФ?
НЕТ
Как минимум потому, что ПР(k) состоит только из всюду определённых рекурсивных функций (РФ). Но и с классом всех РФ это объединение не совпадает, потому что не существует языка программирования, на котором можно реализовать все РФ и только их, а для объединения ПР(k) такой существует.
Цитата:
3. Все вычислимые функции можно перенумеровать (рекурсивной функцией): Ф(к). Тогда определяется всюду определенная функция Ф(х), равная Ф(х)(х)+1, если Ф(х)(х) определенная, и 0 в противном случае. Эта функция отлична от любой функции Ф(к). Относительно функции Ф говорят: невычислима; вычислима в каком-то высшем порядке; противоречива, поэтому оператор рекурсии должна быть применима не только к всюду определенным функциям. Прокомментируйте следующее объяснение: к основным чертам понятия вычислимой функции относится не только требование конечного числа не только используемых операторов, инструкций и т.д, но и требование конечного числа функций, участвующих в построении метода вычисления данной функции.
(Вместо функции Ф можно рассмотреть и частичную функцию Ф(х), равную 0, если Ф(х)(х) определенная, и неопределенная в противном случае.
Не понял. Полученная диагональная функция будет невычислима. Для вычислимости существует конкретное определение, основанное на конечном числе функций и операций. Есть тезис Чёрча-Тьюринга, который говорит, что оно соответствует реальной вычислимости. Этот тезис имеет корень в законах физики.
А твоими рассуждениями можно показать, что нельзя строго зафиксировать понятие "определимость в математике" даже для функций на множестве натуральных чисел. Ибо если мы зафиксировали это понятие, то мы можем таким вот образом построить диагональную функцию Ф(x), она не будет являться "определимой" в этом формальном смысле, но тем не менее мы её как-то определили (описали).
