Ограничимся тсшько функциями, заданными на множестве на-туралы1ых чисел N.

4.2.1. Примитивно рекурсивные функции

Введем следующие функции

s\x) = x + l,

1т{х1, ...,Хп) = (1 < m < п; п = 1,2,...), называемые далее простейшими.

Пусть даны частичные функции д : N а h : N" -> N.

Частичная функция / : JV -¥ N получена из функций д, h примитивной рекурсией, если

f{xu ...,Хп,0) = д{хи ...,Хп),

f{xi,...,Xn,y-\-l) = h{xi,...,Xn,y,fixi,...,Xn,y]). Для п = О уравнения (4.1) принимают вид [д = const = о) /(0) = а,

(4.2)

fix-i-l) = hix,fix)).

Как видно из этих уравнений, задав исходные данные {xi, ...,Хп,0), можно шаг за шагом найти значения функции для {х1, ...,Хп, 1), (х1,Хп,2), ...,(х1,...,Хп,т),...

Символически задание / через примитивную рекурсию можно записать как

f = 9,h).

Частичная функция / : N" -¥ N называется примитивно рекурсивной относительно множества частичных функций если / получается из функций множества Y1 и простейших функций конечным числом операций подстановки (суперпозиции) и примитивной рекурсии.

Если 5]) = 0, то примитивно рекурсивная относительно множества частичных функций функция получается только из простейших функций и поэтому ее называют просто примитивно рекурсивной.

Нетрудно понять, что примитивно рекурсивные функции являются всюду определенными функциями.

Пример 4.1. Функция f(x,y] = х + у примитивно рекурсивна. В самом деле,

f(x,Q) = x + Q = x = ll(x),

f(x,y + l)=x + (y + l) = (x + y) + l = s(x + y) = s{f(x,y)).

Это означает, то функция х + у строится из примитивно рекурсивных функций l\,h{x,y,z) = Z + 1 = s{z) с помощью примитивной рекурсии. Поэтому х+у примитивно рекурсивная функция.

Пример 4.2. Функция f(x, у] = ху примитивно рекурсивна. Действительно,

f{x,0)=x-0 = o\x), g

f{x, у + 1) = х{у + 1) = ху + X = f{x,y) + X.

Если взять

д{х) = о{х), h{x,y,z]=z + x и вспомнить, что h - это примитивно рекурсивная функция (пример 4.1), то убеждаемся в примитивной рекурсивности функции ху.

4.2.2. Частично рекурсивные функции

Пусть дана частичная функция / : iV" N. Зафиксируем данные (ж1, ...,ж„). Введем функцию

М/(ж1,...,ж„) =niin{/(ii,..., ж„ 1,г/) =Хп}-

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

Пример 4.3. Функция

д(.) = (--1 ->0,

\ не опре

1 определено, X = О

- частично рекурсивна. Действительно,

д{х) = Msx) = min{si(y) = у + 1 = х}.

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

Частичная функция / : N" -¥ N называется частично рекурсивной относительно множества частичных функций YI, если / получается из функций множества Y1 и простейших функций конечным числом операций подстановки (суперпозиции), примитивной рекурсии и минимизации.

Если 5]] = 0, то частично рекурсивная относительно множества частичных функций YI функция получается только из простейших функций, и поэтому ее называют просто частично рекурсивной.

Каждая примитивно рекурсивная функция является частично рекурсивной. Обратное неверно, поскольку в класс частично рекурсивных функция в соответствии с определением попадают частичная функция Ms (пример 4.3) и, например, нигде не определенная функция

f{x) = mm{x-hl+y = 0}.

Обратим внимание на то, что минимизация может быть организована как последовательный (алгоритмический) процесс. Действительно, последовательно находим

/(Ж1, хп-1, 0), f(xi, хп-1, 1),/(Ж1, хп-1,у),...

Наименьшее о, для которого

/(ж1,...,Ж„-1,о) =хп,

- это значение для М/(ж1,хп)-

4.2.3. Тезис Чёрча

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

Напомним, что понятие вычислимости связывалось с понятием алгоритма, поэтому общепринятой является гипотеза, именуемая как

Возможно, что процесс нахождения не будет завершен, но это соответствует тому, что М/ может быть истинной частичной функцией.

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