8.3. Тезис чёрча

Частично-рекурсивные функции  это класс числовых функций, представляемых точно определенными формальными средствами.

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

Класс всех интуитивно вычислимых числовых функций совпадает с классом частичнорекурсивных функций

Приведенное утверждение носит название тезиса Чёрча, по имени сформулировавшего этот тезис американского математика.

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

О справедливости тезиса Чёрча свидетельствуют следующие имеющиеся факты:

1. для всякой конкретной числовой функции удается построить её рекурсивное определение;

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

8.4. Нумерация частично-рекурсивных

ФУНКЦИЙ

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

Для этого полное определение произвольной частично- рекурсивной функции представляется в виде специального нагруженного дерева.

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

Будем считать, что для обозначения переменных функций используются только следующие символы: x₁, . . . , x_i, . . .

При разметке вершин деревьев используются следующие символы:

1) C, P, M для обозначения операций суперпозиции, примитивной рекурсии и минимизации;

2) 1для записи индексов переменных в унарной системе;

3. I, S, O  для обозначения простейших функций.

Определим деревья, представляющие схемы определения частично-рекурсивных функций, с помощью следующих правил:

1. Функции O(x_i), S(x_i) и (x_i1, ... , x_in) представляются следующими деревьями:

O S I

i i m n i₁ . . . in

2. Если h(x_j1, . . . , x_jr) =

= f(g₁(x_1,1, . . . , x_1,m1), . . . , g_k(x_k,1, . . . , x_k,mk)), то она представляется деревом:

C

D f Dg₁ . . . Dg_k

З десь Df, Dg₁, ... , Dg_k  это деревья, представляющие функции, входящие в суперпозицию. В частности, если g_i = x_j, то есть представляет собой переменную, то соответствующее дерево имеет вид:

I

1 1 j

3. Пусть f(x₁, . . . , x_n+1) получается из g(x₁, . . . , x_n) и h(x₁, . . . , x_n, x_n+1, x_n+2) с помощью операции примитивной рекурсии:

f(x₁, . . . , x_n, 0) = g(x₁, . . . , x_n);

f(x₁, . . . , x_n, y+1) = h(x₁, . . . , x_n, y, f(x₁, . . . , x_n, y)).

Тогда f представляется деревом:

P

Dg Dh

4. Если f(x₁, . . . , x_n+1) =  t(g(x₁, . . . , x_n, t) = x_n+1), то дерево, представляющее f, имеет вид:

M

Dg

Пример. Построим дерево, представляющее функцию f(x₁, x₂) = x₁+ x₂.

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

f(x₁, 0) = (x₁);

f(x₁, x₂ + 1)= (x₁, x₂, S(f(x₁, x₂)).

Здесь определения функций g и h, из схемы примитивной рекурсии, даны в полном виде с указанием всех переменных (в том числе и несущественных) этих функций в определении схемы примитивной рекурсии.

Поэтому дерево определения f имеет вид, приведенный на рис. 8.1:

P

I C

I I I S

1 1 1

<3><3>1 1 1 1 1 1 1 1 <2> 1

Рис. 8.1

Здесь записи <2> и <3> использованы для представления чисел 2 и 3 в унарной системе счисления.

Упражнение. Построить дерево, представляющее функцию умножения p(x₁, x₂) = x₁  x₂.

Возьмем алфавит A= {I, S, O, P, C, M, 1, $}, состоящий из специального символа $ и символов, c помощью которых осуществлялась разметка вершин деревьев, представляющих частично-рекурсивные функции.

Символ $ будем называть разделителем.

Если D  дерево, представляющее определение некоторой частично - рекурсивной функции, то осуществим левосторонний обход D сверху вниз, выписывая слова в алфавите A, приписанные вершинам дерева в порядке их прохождения. При этом выписываемые слова разделяются символом $.

Полученное в результате слово _D назовем кодом дерева D.

Например, дерево, представляющее функцию f(x₁, x₂) = x₁+x₂, которое приведено ранее, имеет код:

P$I$1$1$1$C$I$<3>$<3>$1$1$1$I$1$1$1$I$1$1$2$S$1.

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

Действительно, всякая внутренняя вершина дерева помечена одним из символов операций или функций. Если это символы O, S, P или M, то число потомков такой вершины заранее известно.

Если же внутренняя вершина дерева помечена символом C, то число потомков этой вершины определяется числом переменных функции, дерево представления которой имеет корнем самого левого потомка исходной вершины. Если же корень дерева помечен символом I, то число потомков этой вершины равно n + 2, где n – число, унарная запись которого размечает вершину левого потомка корня дерева.

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

Вершина дерева является висячей, если она помечена числом в унарной системе.

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

Рассмотрим последовательность всех слов в алфавите A, выписанных в порядке возрастания их длин, а слов одинаковой длины в лексикографическом порядке.

Из этой последовательности выделим подпоследовательность слов:

D1, D2, . . . , Di, . . . ,

(1)

являющихся кодами деревьев.

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

Последовательности (1) соответствует последовательность (2), состоящая из частичнорекурсивных функций, представляемых деревьями, имеющими коды последовательности (1).

g1, g2, . . . , gi, . . .

(2)

Обозначим как Dg_i  дерево, представляющее функцию g_i.

Существует эффективная процедура, которая по всякому числу n строит определение частично рекурсивной функции g_n.

Следовательно, зная порядковый номер n частично рекурсивной функции g_n в последовательности (2), можно эффективно найти рекурсивную схему определения этой функции. То есть по номеру функции в последовательности (2) может быть восстановлено описание метода вычисления значений этой функции.

Отметим простейшие свойства последовательности (2):

 всякая частично рекурсивная функция встречается в (2) бесконечное число раз;

 последовательность (2) содержит счетно-бесконечное множество различных функций;

 существуют числовые функции, не содержащиеся в (2).

По последовательности (2) определим последовательность (3), содержащую все одноместные частично-рекурсивные функции.

f1, f2, . . . , fi, . . .

(3)

Здесь функция f_i задается деревом, полученным из дерева Dg_i, отождествлением всех переменных, т.е. функция f_i получается из функции g_i отождествлением переменных.

Введем обозначения F  для множества всех частично-рекурсивных функций и F¹ для множества всех одноместных частично-рекурсивных функций.

Отображение , которое всякому числу n ставит в соответствие функцию f_n, назовем нумерацией множества F¹.

При этом индекс n функции f_n назовём  номером этой функции в нумерации : N  F¹.

Отображение : N  F, которое всякому числу n ставит в соответствие функцию g_n, назовем нумерацией множества F.

Заметим, что обе нумерации  и  являются вычислимыми, поскольку существуют эффективные процедуры, которые для каждого значения целого неотрицательного числа n строят рекурсивные определения соответствующих функций.

ОПРЕДЕЛЕНИЕ

Вычислимая числовая функция h(x₁, x₂), для которой выполняется условие  iN  n(h(n, x) = f_i(x)), называется универсальной функцией для класса F¹.

ТЕОРЕМА 8.3

Существует универсальная функция для F¹.

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

Определим функцию h(n, x) = f_n(x).

Покажем, что эта функция является вычислимой. Для этого сформулируем интуитивно понятный алгоритм вычисления значений функции h .

Пусть (n, x)  произвольная пара чисел. Выполним следующие действия:

1. По номеру n функции f_n найдем код D_n дерева, определения функции g_n.

2. По найденному коду построим само такое дерево Dg_n.

3. По дереву D_n найдем дерево Df_n для функции f_n.

Для этого изменим разметку вершин в D_k, выполнив отождествление переменных. В результате получим дерево D, представляющее схему рекурсивного определения f_n.

4. По схеме рекурсивного определения f_n вычислим значение y = f_n(x).

5. Закончим вычисление, взяв в качестве результата значение h(n, x) = y.

Приведенная процедура позволяет вычислять функцию h., которая оказывается вычислимой, а значит и частично-рекурсовной.

Нетрудно убедиться, что  n(h(n, x) = f_n(x)).

Следовательно, h является универсальной функцией.

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