Введение в схемы, автоматы и алгоритмы


Определение рекурсивных функций - часть 2


Заметим, что все простейшие функции вычислимы в интуитивном смысле. Кроме того, операторы суперпозиции, примитивной рекурсии и минимизации таже вычислимы: понятны алгоритмы, по которым из программ для исходных функций можно получить программы для результирующих. Следующее определение вводит интересующий нас класс частично рекурсивных функций и его важные подклассы.

Определение 8.5. Частично рекурсивные функции. Функция f называется частично рекурсивной функцией (ч.р.ф.), если она является одной из простейших функций или может получиться из них с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации, т.е. существует последовательность функций f1,f2,…, fn=f, каждая из которых является либо простейшей, либо получена из предыдуших с помощью одного из указанных операторов. Указанная последовательность функций называется частично рекурсивным описанием функции f.

Функция f называется общерекурсивной функцией (о.р.ф.), если она частично рекурсивна и всюду определена.

Функция f называется примитивно рекурсивной функцией (п.р.ф.), если она частично рекурсивна и для нее существует частично рекурсивное описание, использующее лишь операторы суперпозиции и примитивной рекурсии. В таком случае оно называется примитивно рекурсивным описанием функции f.

Нетрудно проверить, что каждая примитивно рекурсивная функция всюду определена, т.е. является общерекурсивной (обратное, вообще говоря, неверно).




Начало  Назад  Вперед



Книжный магазин