Частично-рекурсивные и общерекурсивные функции

Определение 4.2.1. Говорят, что функция f(x₁,x,₂,…x_n) получена из функции g(x₁,x,₂,…x_n, z) с помощью оператора минимизации (m-оператора), и обозначают f(x₁,x,₂,…x_n)= mz[g(x₁,x,₂,…x_n, z)=0],

если f(x₁,x,₂,…x_n)=z тогда и только тогда, когда g(x₁,x,₂,…x_n, k)¹0 при k=0, 1, 2, … z–1, и g(x₁,x,₂,…x_n, z)=0.

Оператор минимизации – удобное средство для построения обратных функций. Функция g(x)= my[f(y)=x] – («наименьший y такой, что, f(y)=x»)является обратной для функции f(x).

Определение4.2.2. Функция называется частично рекурсивной, если она базисная функция или может быть построена из базисных функций конечным числом применения операторов суперпозиции функций, примитивной рекурсии и m-оператора.

Определение4.2.3. Класс частично рекурсивных функций есть транзитивное замыкание множества базисных функций относительно операторов суперпозиции функций, примитивной рекурсии и m-оператора.

Определение 4.2.4. Всюду определенная частичная рекурсивная функция называется общерекурсивной.

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

Первый пример общерекурсивной, но не примитивно рекурсивной функции был построен немецким математиком В.Аккерманом:

В.Аккерман

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

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

Теорема 4.2.1 (Клини). Существует такая примитивно рекурсивная функция g(x), что какова бы ни была частично рекурсивная функция F(x₁, …, x_n), найдетсяпримитивно рекурсивная функция f_F(x₁, …, x_n, z) для которой имеет место равенство:

F(x₁, …, x_n)=g(mz[f_F(x₁, …, x_n, z)=0].

В то же время, функция f(x)= my[x+1+y=0] – пример частично рекурсивной нигде не определенной функции.

Таким образом, иерархия классов рекурсивных функций может быть описана следующим образом:

– класс общерекурсивных функций строго содержит класс частично рекурсивных функций;

– класс частично рекурсивных функций строго содержит класс общерекурсивных функций.

Лекция № 5. Алгоритмическая теория множеств

1. Перечислимые и разрешимые множества.

2. Перечислимость и вычислимость.