|
Н А В И Г А Ц И Я |
|
|
№ |
Понятие, термин |
Неформальное определение, пояснение |
|
1. |
Арифметическая функция |
Функция, которая вместе со своими аргументами принимает значения из множества N0={0, 1, 2, …}. |
|
2. |
Базисные вычислимые функции |
Арифметические функции тождественного
нуля (a1), следования (a2) и проектирования
(a3):
a1. O(x)=0 ("
xÎ N0={0, 1, 2,
…}), a2. x¢ =x+1, a3. |
|
3. |
Базисные операторы |
Операторы подстановки, примитивной рекурсии и минимизации, переводящие вычислимые функции снова в вычислимые функции (см. ниже). |
|
4. |
Оператор подстановки |
Оператор, сопоставляющий функции n переменных f(t1, t2, …, tn) и функциям m переменных gk(x1, x2, …, xm) (k=1, 2, …, n) некоторую новую функцию h() такую, что h(x1, x2, …, xm)=f(g1(x1, x2, …, xm), g2(x1, x2, …, xm), …, gn(x1, x2, …, xm)). |
|
5. |
Оператор примитивной рекурсии |
Оператор, сопоставляющий функции n
переменных j ( x1,
x2, …, xn) и функции (n+2)-х
переменных g(x1,
x2, …, xn, y, t)
некоторую новую функцию h()
удовлетворяющую условиям:
h(x1, x2,
…, xn, 0)=j (
x1, x2, …, xn), h(x1, x2,
…, xn, y+1)=g( x1,
x2, …, xn, y, h(x1,
x2, …, xn, y)), (xkÎ N0,
k=1, 2, …, n). |
|
6. |
Оператор минимизации |
Оператор, сопоставляющий функции (n+1)-й переменой f(x1, x2, …, xn, y) функцию n переменных h() такую, что h(x1, x2, …, xn)= m y(f( x1, x2, …, xn, y)=0). Это соотношение означает, что: a. h(x1, x2, …, xn)=y тогда и только тогда, когда выполнены условия: a1. f( x1, x2, …, xn, t) определены и отличны от нуля для всех t=0, 1, …, y- 1;a2. f( x1, x2, …, xn, y) определено и равно нулю; b. Если величины y с указанными свойствами не существует, то значение h(x1, x2, …, xn) считается неопределенным. |
|
7. |
Рекурсивные функции |
Базисные функции и все функции, получаемые из них с помощью конечного числа применений базисных операторов. |
|
8. |
Примитивно-рекурсивные функции |
Базисные функции и все функции, получаемые из них с помощью конечного числа применений операторов подстановки и примитивной рекурсии (без оператора минимизации). |
|
9. |
Общерекурсивные функции |
Рекурсивные функции, определенные для любых значений своих аргументов из множества N0={0, 1, 2, …}. |
|
10. |
Частично-рекурсивные функции |
Рекурсивные функции, не являющиеся определенными для любых значений своих аргументов из множества N0={0, 1, 2, …}, то есть не являющиеся общерекурсивными. |
.