ВУЗ:
Составители:
ти дает: совокупность всех частичных функций, частично рекурсивных относи-
тельно заданной системы частичных функций G, есть подалгебра алгебры (1),
порожденная в (1) системой G, I
m
n
, O, S.
Обозначим через Fl совокупность всех всюду определенных функций из F
и рассмотрим частичную подалгебру
<Fl; M
l
, R, S
2
, S
3
,…> (2)
алгебры (1). Тогда совокупность всех общекурсивных функций есть подалгебра
алгебры (2), порожденная в (2) простейшими функциями 0,s,I
m
n
.
59 Доказать, что каждая всюду определенная функция, равная натура-
льному числу a везде, за исключением конечного числа точек, является прими-
тивно рекурсивной.
60 Доказать примитивную рекурсивность двуместных функций [x/y],
rest (x,y), где [x/y] означает (неполное) частное, а rest(x,y) - остаток от деле-
ния x на y . По определению полагаем также, что [x/0]=x и rest (x,0)=x.
ти дает: совокупность всех частичных функций, частично рекурсивных относи-
тельно заданной системы частичных функций G, есть подалгебра алгебры (1),
порожденная в (1) системой G, Imn , O, S.
Обозначим через Fl совокупность всех всюду определенных функций из F
и рассмотрим частичную подалгебру
(2)
алгебры (1). Тогда совокупность всех общекурсивных функций есть подалгебра
алгебры (2), порожденная в (2) простейшими функциями 0,s,Imn.
59 Доказать, что каждая всюду определенная функция, равная натура-
льному числу a везде, за исключением конечного числа точек, является прими-
тивно рекурсивной.
60 Доказать примитивную рекурсивность двуместных функций [x/y],
rest (x,y), где [x/y] означает (неполное) частное, а rest(x,y) - остаток от деле-
ния x на y . По определению полагаем также, что [x/0]=x и rest (x,0)=x.
