Классы вычислимых и рекурсивных функций

P _выч – класс всех вычислимых функций.

- класс всех частичных функций из . P_выч.

Простейшими будем называть в дальнейшем следующие функции:

1. S(x) = x + 1 – функция следования;

2. O(x)  0 – нулевая функция;

3. ( x₁, x₂,…, x_n) = x_m ( , n = 1,2,…) – селекторная функция или функция выбора аргумента.

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

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

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

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

Нетрудно показать, что P_пр P_oр P_{чр .}

Исследования показали, что P_чр эквивалентен P_выч. Более того, другие формализации понятия вычислимой функции также оказались равносильными. В настоящее время общепринятым является следующее предложение:

Тезис Черча. P_выч = P_{чр .}

Тезис Тьюринга. Всякий алгоритм может быть реализован машиной Тьюринга.

Эквивалентность класса рекурсивных функций и функций, вычислимых на машинах Тьюринга

Утверждение. Функция вычислима машиной Тьюринга  она частично рекурсивна.

Доказательство данного утверждения разобьем на две теоремы:

Теорема 1.

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

Доказательство.

Идея:

1. сначала доказывается, что простейшие функции вычислимы, - это очевидно.

2. Затем доказывается, что операции суперпозиции, примитивной рекурсии, минимизации сохраняют вычислимость – а для этого для этих операций строим машину Тьюринга.

Ограничимся построением машины Тьюринга для оператора примитивной рекурсии . Рассмотрим случай n = 1.

Пусть , т.е. определена схемой

,

h(x,y+1) = g(x,y,h(x,y)),

где функции f и g вычислимы машинами M_f и M_g, соответственно работающими с правой полулентой. Построим машину M_h, вычисляющую h. Машина M_h должна воспроизводить процесс вычисления по схеме примитивной рекурсии, т.е. последовательно вычислять ; ; ,…, ,… до тех пор, пока не вычислит g(x,y,h(x,y)). Будем считать, что машина M_h, реализующая оператор примитивной рекурсии для n = 1, построена. Для n > 1 все остается таким же, увеличится лишь число переменных. Реализации трех рекурсивных операторов позволяют по рекурсивному описанию любой частично – рекурсивной функции построить реализующую ее машину Тьюринга.

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

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

Идея доказательства :

Деятельность машины Тьюринга рассмотрим как преобразование чисел, т.е. как вычисление числовой функции. Именно такая интерпретация и подразумевается. Доказательство заключается в следующем, чтобы точно описать эту интерпретацию (называемую арифметизацией) и показать, что любое преобразование, реализуемое машиной Тьюринга, если его интерпретировать как вычисление, является частично – рекурсивным.

Сначала опишем арифметизацию машин Тьюринга.

Далее докажем, что на каждом шаге машина Тьюринга осуществляет примитивно – рекурсивное вычисление.

Когда дойдем до заключительного состояния, видно, что функция h, описывающая результат работы машины Тьюринга, построена из примитивно – рекурсивных функций с помощью оператора минимизации, и, следовательно, является частично – рекурсивной.