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

Отображение $f:X\to\omega$ , где $X\subseteq\omega^n$ , называют частичной функцией.

Если $X=\omega^n$ , то частичная функция $f$ называется всюду определённой.

Если $X=\varnothing$ , то частичная функция $f$ называется нигде не определённой.

Базисными функциями называют следующие функции:

1. $\theta(x)=0$ — нулевая функция.

2. $s(x)=x+1$ — функция следования.

3. $I^i_n(x_1,\ldots,x_n)=x_i$ — функция выбора (проекции).

Обозначим через $F_n$ множество всех $n$ -местных частичных функций.

Оператор суперпозиции

$\mathcal{S}:F_m\times\underbrace{F_n\times\ldots\times F_n}_{m}\to F_n$ ,

где

$\mathcal{S}(f,g_1,\ldots,g_m)=h$ ,

$h(x_1,\ldots,x_n)=f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n)).$

Оператор примитивной рекурсии

$\mathcal{R}:F_{n-1}\times F_{n+1}\to F_n$ ,

где

$\mathcal{R}(g,f)=h$ ,

$\begin{cases} h(x_1,\ldots,x_{n-1},0)=g(x_1,\ldots,x_{n-1}),\\ h(x_1,\ldots,x_{n-1},k+1)=f(x_1,\ldots,x_{n-1},k,h(x_1,\ldots,x_{n-1},k)).\end{cases}$

Оператор минимизации

$\mu:F_{n+1}\to F_n$ ,

где $\mu(f)=h$ и $h(x_1,\ldots,x_n)=y$ тогда и только тогда, когда $f(x_1,\ldots,x_n,0),\ldots,f(x_1,\ldots,x_n,y-1)$ определены, $f(x_1,\ldots,x_n,k)\ne0$ для всех $k<y$ и $f(x_1,\ldots,x_n,y)=0$ .

Обозначение: $h(x_1,\ldots,x_n)=\mu_y[g(x_1,\ldots,x_n,y)]$ .

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

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

Версия для печати