Основные определения
Рассмотрим следующие правила преобразования функций.
- Рассмотрим [math] k [/math]-местную функцию [math] f(x_1,\ldots,x_k) [/math] и [math] k [/math] [math]n [/math]-местных функций [math] g_i(x_1,x_2,\ldots,x_n) [/math]. Тогда после преобразования у нас появится [math] n [/math] - местная функция [math] F = f(g_1(x_1,\ldots,x_n),\ldots, g_k(x_1,\ldots,x_n)) [/math].
Это правило называется правилом подстановки
- Рассмотрим [math] k [/math]-местную функцию [math] f [/math] и [math] k + 2 [/math]-местную функцию [math] h [/math]. Тогда после преобразования у нас будет [math] k+1 [/math] -местная функция [math] g [/math], которая определена следующим образом:
- [math]g(x_1,\ldots,x_n,0)=f(x_1,\ldots,x_n)[/math]
- [math]g(x_1,\ldots,x_n,y+1)=h(x_1,\ldots,x_n,y,g(x_1,\ldots, x_n,y))[/math]
- Это правило называется правилом рекурсии.
| Определение: |
| Примитивно рекурсивными называют функции, которые можно получить с помощью правил подстановки и рекурсии из константной функции [math] \textbf 0 [/math], функции [math] I(x) = x + 1, [/math] и набора функций [math] P_{n,k}(x_1,\ldots,x_n) = x_k,[/math] где [math] k \le n [/math]. |
Заметим, что если [math] f [/math] — [math] n [/math]-местная примитивно рекурсивная функция, то она определена на всем множестве [math] \mathbb {N}^{n} [/math], так как [math] f [/math] получается путем правил преобразования из всюду определенных функций, и правила преобразование не портят всюду определенность. Говоря не формальным языком, рекурсивные функции напоминают программы, у которых условия останова для всех циклов и рекурсий не зависят от входных данных. Из-за того что у нас есть P_{x,y} - в правиле подстановки можно подставлять функции с разным числом аргументов и тогда количество переменных от которых зависит результирующая функция будет равно максимальному количеству аргументов среди всех подставляемых функций.
Арифметические операции на примитивно рекурсивных функциях
n -местный ноль
[math] \textbf 0 [/math] - функция нуля аргументов.
Выразим сначала [math] \textbf 0^1 [/math]
[math] \textbf 0^{1}(0) = \textbf 0 [/math]
[math] \textbf 0^{1}(y+1) = h(y,\textbf 0^{1}(y)) [/math], где [math] h(x,y) = P_{2,1}(x,y) [/math]
Теперь выразим [math] \textbf 0^n [/math]
[math] \textbf 0^{n}(x_1,\ldots,x_{n-1},0) = \textbf 0^{n-1} [/math]
[math] \textbf 0^{n}(x_1,\ldots,x_{n-1},y+1) = h(x_1,\ldots,x_{n-1},\textbf 0^{n}(y)) [/math], где [math] h(x,y) = P_{n,n}(x,y) [/math]
Константа [math] \textbf M [/math] равна [math] I(\textbf{M-1}) [/math]
[math] \textbf M^n [/math] - n местная константа, получается аналогичным к [math] \textbf 0^n [/math] образом.
Сложения
[math] sum(x,0) = \textbf P_{1,1}(x) [/math]
[math] sum(x,y+1) = h(x,y,sum(x,y)) [/math] , где [math] h(x,y,z)=I(P_{3,3}(x,y,z)) [/math]
Умножения
[math] prod(x,0) = \textbf 0^1(x) [/math]
[math] prod(x,y+1) = h(x,y,prod(x,y)) [/math], где [math] h(x,y,z)=sum(P_{3,1}(x,y,z),P_{3,3}(x,y,z)) [/math]
Вычитания
Если [math] x \lt y [/math], то [math] sub(x,y) = 0 [/math] , иначе [math] sub(x,y) = x - y [/math].
Рассмотрим сначала вычитания единицы [math] sub_{1}(x) = x - 1 [/math]
[math] sub_1(0) = \textbf 0 [/math]
[math] sub_1(x+1) = h(x,sub_1(x)) [/math], где [math] h(x,y) = P_{2,1}(x,y) [/math]
Теперь рассмотрим [math] sub(x,y) [/math]
[math] sub(x,0) = P_{1,1}(x) [/math]
[math] sub(x,y+1) = h(x,y,sub(x,y)) [/math], где [math] h(x,y,z) =sub_1(P_{3,3}(x,y,z)) [/math]
Операции сравнения
[math] eq(x,y) = 1 [/math] если [math] x = y [/math], иначе [math] eq(x,y) = 0 [/math]
[math] le(x,y) = 1 [/math] если [math] x \le y [/math], иначе [math] lq(x,y) = 0 [/math]
[math] lower(x,y) = 1 [/math] если [math] x \lt y [/math], иначе [math] lower(x,y) = 0 [/math]
Сначала выразим [math] eq_{0}(x) = eq(x,0) [/math]
[math] eq_0(0) =I(\textbf 0) [/math]
[math] eq_0(y+1) = h(y,eq(y)) [/math] , где [math] h(y,eq(y)) = \textbf 0^2(x,y) [/math]
[math] le(x,y) = eq_0(sub(x,y)) [/math]
[math] eq(x,y) = mul(le(x,y),le(y,x)) [/math]
[math] lower(x,y) = mul(le(x,y),le(I(x),P_{1,1}(y))) [/math]
Деление
[math] divide(x,y) = \frac{x}{y} [/math], если [math] y \gt 0 [/math], иначе [math] divide(x,y) = 0 [/math]
divmax(y,0) = 0
divmax(y,x+1) = h(y,x,divmax(x)), где [math] h(y,x,z) = if (x+1 - divmax(x) == y) then x+1 else y
sub(I(P_{3,1}(x,y,z)t
Сначала выразим \lt tex\gt mod(x,y) [/math] - модуль от деления.
<tex> count(x,y) =
