Лекция: Примитивно-рекурсивные и частично-рекурсивные функции. (с43)

Функция называется примитивно – рекурсивной, если она может быть получена из константы 0 и функции x’ с помощью конечного числа применений операторов тождества, суперпозиции и п-р.

Большинство вычислимых функций относится к классу примитивно-рекурсивных функций.

Если некоторые функции являются примитивно-рекурсивными, то в результате применения к ним операторов суперпозиции или примитивной рекурсии можно получить новые примитивно-рекурсивные функции.

Существует три возможности доказательства того, что функция является примитивно-рекурсивной:

а) показать, что заданная функция является простейшей;

б) показать, что заданная функция построена с помощью оператора суперпозиции;

в) показать, что заданная функция построена с помощью оператора примитивной рекурсии.

Тем не менее примитивно-рекурсивные функции не охватывают все вычислимые функции, которые могут быть определены конструктивно. При построении этих функций могут использоваться другие операции.

Функция называется частично-рекурсивной (вычислимой по Черчу), если она может быть получена из простейших функций с помощью конечного числа операторов суперпозиции, примитивной рекурсии и минимизации.

Указанные операции могут быть выполнены в любой последовательности и любое конечное число раз.

Таким образом, мы не просто задаем функцию, но и точно знаем, как её вычислять.

Если такие функции оказываются всюду определенными, то они называются общерекурсивными функциями.

Частично-рекурсивные функции вычислимы путем определенной процедуры механического характера. Практически понятием частично-рекурсивных функций пользуются для доказательства алгоритмической разрешимости или неразрешимости проблем.

Всякая функция, вычислимая с помощью машины Тьюринга, является частично рекурсивной.

Всякая частично рекурсивная функция вычислима на машине Тьюринга.

Всякая примитивно рекурсивная функция f является всюду определенной функцией.

Примеры: (с44-46)