30. Рекурсивные функции. Примеры

Определение 2 Функция f называется частично рекурсивной функцией, если она может быть получена из простейших функций с помощью операции суперпозиции, примитивной рекурсии и минимизации, взятых конечное число раз в любой последовательности.

Класс частично рекурсивных функций обозначим Prp.

Обозначим через Pp­­– класс рекурсивных функций, т.е. всех числовых функций из Prp.

Пример 9 Доказать, что частично числовая функция частично рекурсивна.

Вначале заметим, что данная функция получается из функции с помощью операции минимизации, т.е.= My.

Согласно примерам 2 и 4 функция примитивно рекурсивна. А это значит, что– частично рекурсивная функция.

Данный пример показывает, что класс Prp существенно шире, чем класс Pp. Можно сказать, что и класс Pp существенно шире, чем класс Pnp, т.е.

Pnp С Pp С Prp.