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

Определение 4.2.1. Говорят, что функция f(x₁,x,₂,…x_n) получена из функции g(x₁,x,₂,…x_n, z) с помощью оператора минимизации (-оператора), и обозначают f(x₁,x,₂,…x_n)= z[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)= y[f(y)=x] – («наименьший y такой, что, f(y)=x») является обратной для функции f(x).

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

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

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

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

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

В.Аккерман

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

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

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

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

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

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

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

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

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

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

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

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

При использовании далее терминов «алгоритм», «вычислимая функция» имеется в виду любая возможная их формализация в терминах машин Тьюринга, нормальных алгорифмов или рекурсивных функций. Все рассматриваемые множества – суть подмножества натурального ряда. Дополнением множества MN является множество N\M.

Определение 5.1.1. Множество MN называется разрешимым, если существует алгоритм, позволяющий для каждого nN определить, принадлежит ли это число множеству M или нет. Такой алгоритм называется разрешающим для множества M.

В иной терминологии это определение формулируется так.

Определение 5.1.1*. Множество MN называется разрешимым, если его характеристическая функция:

является общерекурсивной.

Теорема 5.1.1. Если множества А и В разрешимы, то разрешимы множества N\А, АВ, АВ.

Доказательство. Если характеристические функции и– общерекурсивны, то и характеристические функции множествN\А, АВ, АВ:

,

.

также являются общерекурсивными функциями.

Теорема 5.1.2. Любое конечное множество MN – разрешимо.

Определение 5.1.2. Непустое множество MN перечислимо, если существует алгоритм, перечисляющий (порождающий) его элементы. Этот алгоритм называют порождающим алгоритмом для множества M.

Пустое множество считается перечислимым по определению.

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

Определение 5.1.2*. Непустое множество MN перечислимо, если существует общерекурсивная функция _M(x) такая, что: M={y: y=_M(x), xN}.

Теорема 5.1.3. Если множества А и В перечислимы, то перечислимо множество АВ.

Доказательство. Положим

Так как функция rest(x, 2) нахождения остатка от деления x на 2 является общерекурсивной (доказательство этого факта остается за читателем), то общерекурсивной будет и функция:

, где – целая часть числа.

В этом случае множество

АВ={y: ,xN}

по определению будет перечислимым.

Теорема доказана.

Теорема 5.1.4. Если множества А и В перечислимы, то перечислимо множество АВ.

Доказательство. Введем в рассмотрение следующие функции:

1) функцию ограниченного вычитания:

2) функции большого размаха:

где .

3) где:

_A(x) – общерекурсивная функция, порождающая множество A;

_B(x) – общерекурсивная функция, порождающая множество B;

Все перечисленные функции являются общерекурсивными, и потому общерекурсивной функцией будет функция _AB(x)=_A(n(s(x))), порождающая множество AB.

Теорема доказана.

Теорема 5.1.5. Непустое разрешимое множество MN перечислимо.

Доказательство. Пусть – характеристическая функция множестваMN, . Тогда функция

является общерекурсивной и порождающей множество М.

Если М={m₀, m₁, m₂, …, m_n, ..} и m₀,<m₁<m₂ <…<m_n , то график функции имеет вид:

Теорема 5.1.6. Множество MN разрешимо тогда и только тогда, когда M и N\М перечислимы.

Доказательство. Если множество M разрешимо, то по теореме 5.1 разрешимо его дополнение N\М. По теореме 5.4 перечислимы оба множества. В одну сторону теорема доказана.

Пусть далее M и N\М перечислимы, что означает существование общерекурсивных функций _М, _N\М.

Определим общерекурсивную функцию (x), значением которой является наименьшее число z, при котором либо _М(z)=x, либо _N\М(z)=x, следующим образом: .

Тогда характеристическая функция множества М может быть записана так:. Так как:общерекурсивная функция, то теорема доказана.

Следствие. Если множество M перечислимо, но неразрешимо, то множество N\М не перечислимо.

Теорема 5.1.7. Множество записей машин Тьюринга является перечислимым множеством.

Теорема 5.1.8. Множество записей самоприменимых машин Тьюринга перечислимо, но не разрешимо.

Следствие. Дополнение множества записей самоприменимых машин Тьюринга неперечислимо.