Математическая логика и теория алгоритмов. Анкудинов Г.И - 69 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

• следования S(x)=x+1=x',
• константы ноль 0(x)=0,
,...,x )=x (1≤m≤n),
• тождества Im(x
n m1
• либо функция, которая может быть получена из простейших
функций с помощью применения конечного числа
операторов подстановки и примитивной рекурсии.
Все ПР-функции всюду определенные. В предыдущем примере
мы имели ПР-функцию f(x)=x*(x-1). Ниже мы рассмотрим и другие
примеры ПР-функций. В дальнейшем изложении и примерах мы
предполагаем, что области определения и значения ПР-функций –
множества неотрицательных целых чисел (что не уменьшает
общности выводов).
Примеры ПР-функций
Функция сложения:
f
с
(x; 0)=x,
f
с
(x; 1)=h(x; 0; f
с
(x; 0))=S(f
с
(x; 0)),
...
f
с
(x; m+1)=S(f
с
(x; m)).
Функция умножения:
(x; 0)=0,
f
у
(x; 1)=h(x; 0; f (x; 0))=f
f
у у с
(x; f (x; 0)),
у
...
f
(x; m+1)=f
у с
(x; f (x; m)).
у
Функции сигнум и антисигнум. Поскольку мы не используем
отрицательных чисел, определим функцию сигнум следующим
образом
()
⎩
⎨
⎧
>
=
=
,0 если ,1
;0 если ,0
sgn
x
x
x
и антисигнум как
()
⎩
⎨
⎧
>
=
=
.0 если ,0
;0 если ,1
sgn
x
x
x
Обе эти функции рекурсивны и могут быть заданы схемами:
153

Страницы