Вычислимые функции. Частично рекурсивные и общерекурсивные функции

Для алгоритмических проблем типичным является то обстоятельство, что требуется найти алгоритм для решения задачи, в условия которой входят значения некоторой конечной системы целочисленных параметров x₁, x₂,…, x_n, а искомым результатом также является целое число y. Следовательно, стоит вопрос о существовании алгоритма для вычисления значений числовой функции y, зависящей от целочисленных значений аргументов x₁, x₂,…, x_n.

Определение 1. Функция называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значения.

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

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

1. l(x) = x + 1 (оператор сдвига),

2. O(x) = 0 (оператор аннулирования),

3. I_n^m(x₁, x₂,…, x_n) = x_m (оператор проектирования).

Ясно, что все три простейшие функции всюду определены и интуитивно вычислимы.

Далее вводятся операции над функциями.

1. Суперпозиция функций. Пусть определены функции f₁(x₁, x₂,…, x_n), f₂(x₁, x₂,…, x_n), …, f_m(x₁, x₂,…, x_n) и функция j(x₁, x₂,…, x_m). Говорят, что функция y(x₁, x₂,…, x_n) получена суперпозицией функций f_i(x₁, x₂,…, x_n), если справедливо равенство

y(x₁, x₂,…, x_т) = j(f₁(x₁, x₂,…, x_n), f₂(x₁, x₂,…, x_n), …, f_m(x₁, x₂,…, x_n)).

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

2. Схема примитивной рекурсии. Пусть имеются две функции j(x₂, x₃,…, x_n) и y(x₁, x₂,…, x_n, x_n+1) (n > 1). Рассмотрим новую функцию, которая удовлетворяет следующим равенствам:

f(0, x₂, x₃,…, x_n) = j(x₂, x₃,…, x_n),

f(y + 1, x₂, x₃,…, x_n) = y(y, f(y, x₂, x₃,…, x_n), x₂, x₃,…, x_n).

Отметим, что функция j зависит от n – 1 аргументов, y – от n + 1, а f – от n.

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

В качестве примера рассмотрим функцию f(y, x):

f(0, x) = x,

f(y + 1, x) = f(y, x) + 1.

Здесь функция j(x) = x, а y(y, f(y, x), x) = y + 1. Рассмотрим, как можно вычислить значение функции f(y, x) при y = 5, x = 2. Так как f(0, x) = j(2) = 2, то из второго равенства последовательно имеем (начиная с y = 0):

f(1, 2) = y(0, 2, 2) = 2 + 1 = 3,

f(2, 2) = y(1, 3, 2) = 3 + 1 = 4,

f(3, 2) = y(2, 4, 2) = 4 + 1 = 5,

f(4, 2) = y(3, 5, 2) = 5 + 1 = 6,

f(5, 2) = y(4, 6, 2) = 6 + 1 = 7 – искомое значение функции.

3. Операция минимизации (m-оператор). Пусть задана некоторая функция f(x, y). Зафиксируем значение x и выясним, при каком значении y f(x, y) = 0. Так как результат зависит от x, то наименьшее значение y, при котором f(x, y) = 0, есть функция от x. Принято обозначение

j(x) = my[f(x, y) = 0].

(читается: «наименьшее y такое, что f(x, y) = 0»)

Аналогично можно определить функцию для многих переменных:

j(x₁, x₂,…, x_n) = my[f(x₁, x₂,…, x_n, y) = 0].

Переход от функции f к функции j называется применением m-оператора.

Функция j может быть вычислена следующим образом:

1. Вычислим f(x₁, x₂,…, x_n, 0). Если это значение f = 0, то полагаем j(x₁, x₂,…, x_n) = 0 и завершаем вычисление. Иначе переходим к следующему шагу.

2. Вычислим f(x₁, x₂,…, x_n, 1). Если это значение f(x₁, x₂,…, x_n, 1) = 0, то полагаем j(x₁, x₂,…, x_n) = 1 и завершаем вычисление. Иначе переходим к следующему шагу. И т.д.

Если окажется, что для всех достижимых (т.е. принадлижащих области определения) значений у функция f(x₁, x₂,…, x_n, у) ¹ 0, то функцию j(x₁, x₂,…, x_n) считают неопределенной.

Определение 2. Функция f(x₁, x₂,…, x_n) называется частично рекурсивной, если она может быть получена за конечное число шагов из простейших функций при помощи операций суперпозиции, схем примитивной рекурсии и m-оператора.

Определение 3. Функция f(x₁, x₂,…, x_n) называется общерекурсивной, если она частично рекурсивна и всюду определена.

Примерами общерекурсивных функций являются: f(x, y) = x + y, f(x, y) = x × y, f(x, y) = x + n.

Тезис А. Чёрча. Каждая интуитивно вычислимая функция является частично рекурсивной.

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

Дата добавления: 2015-10-30