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

<< >>

Рекурсивные функции

Рассмотрим примитивы, из которых будем собирать выражения:

1. [math]Z: N \rightarrow N[/math], [math]Z(x) = 0[/math]
2. [math]N: N \rightarrow N[/math], [math]N(x) = x'[/math]
3. Проекция. [math]U^n_i: N^n \rightarrow N[/math], [math]U^n_i (x_1, ... x_n) = x_i[/math]
4. Подстановка. Если [math]f: N^n \rightarrow N[/math] и [math]g_1, ... g_n: N^m \rightarrow N[/math], то [math]S\langle{}f,g_1,...g_n\rangle: N^m \rightarrow N[/math]. При этом [math]S\langle{}f,g_1,...g_n\rangle (x_1,...x_m) = f(g_1(x_1,...x_m), ... g_n(x_1,...x_m))[/math]
5. Примитивная рекурсия. Если [math]f: N^n \rightarrow N[/math] и [math]g: N^{n+2} \rightarrow N[/math], то [math]R\langle{}f,g\rangle: N^{n+1} \rightarrow N[/math], при этом [math]R\langle{}f,g\rangle (x_1,...x_n,y) = \left\{\begin{array}{ll} f(x_1,...x_n) & , y = 0\\ g(x_1,...x_n,y-1,R\langle{}f,g\rangle(x_1,...x_n,y-1)) &, y \gt 0 \end{array}\right.[/math]
6. Минимизация. Если [math]f: N^{n+1} \rightarrow N[/math], то [math]\mu \langle{}f\rangle: N^n \rightarrow N[/math], при этом [math]\mu \langle{}f\rangle (x_1,...x_n)[/math] — такое минимальное число [math]y[/math], что [math]f(x_1,...x_n,y) = 0[/math]. Если такого [math]y[/math] нет, результат данного примитива неопределен.

Если некоторая функция [math]N^n \rightarrow N[/math] может быть задана с помощью данных примитивов, то она называется рекурсивной. Если некоторую функцию можно собрать исключительно из первых 5 примитивов (то есть без использования операции минимизации), то такая функция называется примитивно-рекурсивной.

Теорема:

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

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

[math]\triangleright[/math]

[math] \operatorname {plus} = R \langle U^1_1, S\langle N, U^3_3 \rangle\rangle \\ \operatorname {dec} = R \langle Z, U^2_1 \rangle \\ \operatorname {minus} = R \langle U^1_1, S\langle\operatorname {dec}, U^3_3 \rangle\rangle \\ \operatorname {one} = S \langle N, Z \rangle \\ \operatorname {mul} = R \langle Z, S \langle\operatorname {plus}, U^3_1, U^3_3 \rangle\rangle \\ \operatorname {pow} = R \langle\operatorname {one}, S \langle\operatorname {mul}, U^3_1, U^3_3 \rangle\rangle \\ \operatorname {sign} = R \langle Z, S \langle N, S \langle Z, U^2_1 \rangle\rangle \\ [/math]

[math]\triangleleft[/math]

Арифметические функции и отношения. Их выразимость в формальной арифметике

Введем обозначение. Будем говорить, что [math]\alpha (x_1, \dots x_n)[/math] — это формула с [math]n[/math] свободными переменными, если переменные [math]x_1, ... x_n[/math] входят в [math]\alpha[/math] свободно. Запись [math]\alpha (y_1, \dots y_n)[/math] будем трактовать, как [math]\alpha [x_1 := y_1, ... x_n := y_n][/math], при этом мы подразумеваем, что [math]y_1, \dots y_n[/math] свободны для подстановки вместо [math]x_1, \dots x_n[/math] в [math]\alpha[/math].

Также, запись [math]B(x_1, \dots x_n) := \alpha(x_1, \dots x_n)[/math] будет означать, что мы определяем новую формулу с именем [math]B[/math]. Данная формула должна восприниматься только как сокращение записи, макроподстановка.

Определение:

Арифметическая функция --- функция [math]f: N^n \rightarrow N[/math]. Арифметическое отношение --- [math]n[/math]-арное отношение, заданное на [math]N[/math].

Определение:

Арифметическое отношение [math]R[/math] называется выразимым (в формальной арифметике), если существует такая формула [math]\alpha (x_1, \dots x_n)[/math] с [math]n[/math] свободными переменными, что для любых натуральных чисел [math]k_1[/math] ... [math]k_n[/math] если [math]R(k_1, \dots k_n)[/math] истинно, то доказуемо [math]\alpha (\overline{k_1}, \dots \overline{k_n})[/math] если [math]R(k_1, \dots k_n)[/math] ложно, то доказуемо [math]\neg \alpha (\overline{k_1}, \dots \overline{k_n})[/math].

Например, отношение [math](\lt )[/math] является выразимым в арифметике: Рассмотрим формулу [math]\alpha (a_1, a_2) = \exists b (\neg b = 0 \& a_1 + b = a_2)[/math]. В самом деле, если взять некоторые числа [math]k_1[/math] и [math]k_2[/math], такие, что [math]k_1 \lt k_2[/math], то найдется такое положительное число [math]b[/math], что [math]k_1 + b = k_2[/math]. Можно показать, что если подставить [math]\overline{k_1}[/math] и [math]\overline{k_2}[/math] в [math]\alpha[/math], то формула будет доказуема.

Наметим доказательство: Тут должно быть два доказательства по индукции, сперва по [math]k_2[/math], потом по [math]k_1[/math]. Рассмотрим доказательство по индукции: пусть [math]k_1 = 0[/math], индукция по 2-му параметру: Разберем доказательство базы при [math]k_2 = 1[/math]. Тогда надо показать [math]\exists b (\neg b = 0 \& 0 + b = 1)[/math]:

(1)	[math]\neg 1 = 0 \& 0 + 1 = 1[/math]	Несложно показать
(2)	[math](\neg 1 = 0 \& 0 + 1 = 1) \rightarrow \exists b (\neg b = 0 \& 0 + b = 1)[/math]	Cх. акс. для [math]\exists[/math]
(3)	[math]\exists b (\neg b = 0 \& 0 + b = 1)[/math]	M.P. 1 и 2.

Определение:

Введем следующее сокращение записи: пусть [math]\exists ! y \phi (y)[/math] означает [math]\exists y \phi (y) \& \forall a \forall b (\phi(a) \& \phi(b) \rightarrow a=b)[/math] Здесь [math]a[/math] и [math]b[/math] — некоторые переменные, не входящие в формулу [math]\phi[/math] свободно.

Определение:

Арифметическая функция [math]f[/math] от [math]n[/math] аргументов называется представимой в формальной арифметике, если существует такая формула [math]\alpha (x_1, \dots x_{n+1})[/math] с [math]n+1[/math] свободными пременными, что для любых натуральных чисел [math]k_1[/math] ... [math]k_n[/math] [math]f(k_1, \dots k_n) = k_{n+1}[/math] тогда и только тогда, когда доказуемо [math]\alpha (\overline{k_1}, \dots \overline{k_{n+1}})[/math]. Доказуемо [math]\exists ! b (\alpha (\overline{k_1}, \dots \overline{k_n}, b)[/math] Комментарии: Функция называется сильно представимой, если в свойстве 2 натуральные числа заменить на переменные: [math]\exists ! b (\alpha (a_1, \dots a_n, b)[/math]

Комментарии:

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

Теорема:

Функции [math]Z[/math], [math]N[/math], [math]U^n_i[/math] являются представимыми.

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

[math]\triangleright[/math]

Наметим доказательство. Для этого приведем формулы, доказательство корректности этих формул оставим в виде упражнения. Примитив [math]Z[/math] представит формула [math]Z (a, b) := (a=a \& b=0)[/math]. Примитив [math]N[/math] представит формула [math]N (a, b) := (a' = b)[/math]. Примитив [math]U^n_i[/math] представит формула [math]U^n_i (a_1, ...a_n, b) = (a_1=a_1) \& ... \& (a_n=a_n) \& (b= a_i)[/math].

[math]\triangleleft[/math]

Теорема:

Если функции [math]f[/math] и [math]g_1[/math], ... [math]g_m[/math] представимы, то функция [math]S\langle{}f,g_1,\dots g_m\rangle[/math] также представима.

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

[math]\triangleright[/math]

Поскольку функции [math]f[/math] и [math]g_i[/math] представимы, то есть формулы [math]F[/math] и [math]G_1, \dots G_m[/math], их представляющие. Тогда следующая формула представит [math]S\langle{}f,g_1,\dots g_m\rangle[/math]: [math]S (a_1, \dots a_n, b) := \exists b_1 \dots \exists b_m (G_1 (a_1, \dots a_n, b_1) \& \dots \& G_m (a_1, \dots a_n, b_m) \& F (b_1, \dots b_m, b))[/math]

[math]\triangleleft[/math]

Определение:

Характеристическая функция арифметического отношения [math]R[/math] — это функция [math]C_R (x_1, ... x_n) = \left\{\begin{array}{ll}0 &R (x_1,...x_n)\\1 & R (x_1,...x_n) \textrm{ неверно}\end{array}\right.[/math]

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

Определение:

[math]\beta[/math]-функция Геделя - это функция [math]\beta (b,c,i) = b \% (1 + c \cdot (i + 1))[/math]. Здесь операция (%) означает взятие остатка от целочисленного деления.

Лемма:

Функция примитивно-рекурсивна, и при этом представима в арифметике формулой [math]B (b,c,i,d) := \exists q ((b = q \cdot (1 + c \cdot (i+1)) + d) \& (d \lt 1 + c \cdot (i+1)))[/math]

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

[math]\triangleright[/math]

Упражнение.

[math]\triangleleft[/math]

Лемма:

Для любой конечной последовательности чисел [math]k_0[/math] ... [math]k_n[/math] можно подобрать такие константы [math]b[/math] и [math]c[/math], что [math]\beta (b,c,i) = k_i[/math] для [math]0 \le i \le n[/math].

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

[math]\triangleright[/math]

Возьмем число [math]c = max(k_1,\dots k_n,n)![/math]. Рассмотрим числа [math]u_i = 1 + c \cdot (i+1)[/math]. Никакие числа [math]u_i[/math] и [math]u_j[/math] [math](0 \le j \lt i \le n)[/math] не имеют общих делителей кроме 1. Пусть это не так, и есть некоторый общий делитель [math]p[/math] (очевидно, мы можем предположить его простоту — разложив на множители, если он составной). Тогда [math]p[/math] будет делить [math]u_i - u_j = c \cdot (i - j)[/math], при этом [math]p[/math] не может делить [math]c[/math] — иначе окажется, что [math]u_i = (1 + c \cdot (i+1))[/math] делится на [math]p[/math] и [math]c \cdot (i+1)[/math] делится на [math]p[/math]. Значит, [math]p[/math] делит [math]i-j[/math], то есть все равно делит [math]c[/math], так как [math]c[/math] — факториал некоторого числа, не меньшего [math]n[/math], и при этом [math]i-j \le n[/math]. Каждое из чисел [math]k_i[/math] меньше, чем [math]u_i[/math]: в самом деле, [math]k_i \le c \lt 1 + c \cdot (i+1) = u_i[/math]. Согласно китайской теореме об остатках, если некоторые натуральные числа [math]u_0, \dots u_n[/math] попарно взаимно просты, то для любых целых чисел [math]k_0, \dots k_n[/math], таких, что [math]0 \le k_i \lt u_i[/math], найдется такое целое число [math]b[/math], для которого выполнено [math]k_i = b \% u_i[/math]. Возьмем [math]b[/math], подсказываемое теоремой об остатках.

[math]\triangleleft[/math]

Теорема:

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

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

[math]\triangleright[/math]

Представимость первых четырех примитивов уже показана. Покажем представимость примитивной рекурсии и операции минимизации. Пусть есть некоторый [math]R \langle{} f,g \rangle[/math]. Соответственно, [math]f[/math] и [math]g[/math] уже представлены как некоторые формулы [math]F[/math] и [math]G[/math]. Из определения [math]R\langle{}f,g\rangle[/math] мы знаем, что для значения [math]R \langle{} f,g \rangle (x_1,...x_{n+1})[/math] должна существовать последовательность [math]a_0 ... a_{x_{n+1}}[/math] результатов применения функций f и g — значений на одно больше, чем итераций в цикле примитивной рекурсии, а это количество определяется последним параметром функции [math]R \langle{}f,g\rangle[/math]. При этом: Значит, по лемме, должны существовать такие числа [math]b[/math] и [math]c[/math], что [math]\beta (b,c,i) = a_i[/math] для [math]0 \le i \le x_{n+1}[/math]. Приведенные рассуждения позволяют построить следующую формулу, представляющую [math]R\langle{}f,g\rangle (x_1, ... x_{n+1})[/math]: [math] R(x_1, \dots x_{n+1}, a) := \exists b \exists c (\exists k (B (b, c, 0, k) \& F (x_1,...x_n, k)) \& B(b, c, x_{n+1}, a) \& \forall k (k \lt x_{n+1} \rightarrow \exists d \exists e (B (b, c, k, d) \& B (b, c, k', e) \& G (x_1,..x_n, k, d, e)))[/math] Рассмотрим конструкцию [math]\mu\langle{}f\rangle[/math]. [math]f[/math] уже представлено как некоторая формула [math]F[/math]. Тогда формула [math]M (x_1, \dots x_n,y) := F(x_1, \dots x_n,y,0) \& \forall z (z \lt y \rightarrow \neg F (x_1, \dots x_n,z,0))[/math] представит [math]\mu\langle{}f\rangle[/math].

[math]\triangleleft[/math]