Теория алгоритмов. Зюзысов В.М. - 10 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

prod: <x,y> → x y.
Используем примитивную рекурсию
prod(x,0) = 0(x) = 0,
prod(x,y+1) = sum(prod(x,y),x).
Усеченное вычитание 1
δ(x) = x-1, если x>0,
δ(0) = 0.
Эта функция примитивно-рекурсивна, действительно,
δ(0) = 0 = 0(x),
δy+1) = y = pr
2
(<x,y>).
•
•
•
•
•
•
•
Усеченная разность
x÷y = x–y, если x ≥ y,
x÷y = 0, если x < y.
Эта функция примитивно-рекурсивна, действительно,
x÷0 = x,
x÷(y+1) = δ( x÷y).
Модуль разности
|x–y| = x–y, если x≥y,
|x–y| = y–x, если x<y.
Эта функция примитивно-рекурсивна в силу суперпозиции
|x–y| = (x÷y)+(y÷x).
Факториал
Действительно,
0! = 1,
(y+1)! = prod(y!,y+1).
min(x,y) – наименьшее из чисел x и y
В силу суперпозиции: min(x,y) = x÷(x÷y).
Знак числа
sg(x) = 0, если x = 0,
sg(x) = 1, если x
>1.
В силу рекурсии
sg(0) = 0,
sg(y+1) = 1.
rm(x, y) – остаток от деления y на x, если x≠0, и y, если x=0.
В силу рекурсии и суперпозиции
rm(x,0) = 0,
rm(x,y+1) = prod(s(rm(x,y)),sg(|x–s(rm(x,y))|)).
Используя функции, для которых уже установлено
, что они являются частично-
рекурсивными, мы получаем все новые и новые частично-рекурсивные функции.
Существуют критерии, которые позволяют установить частичную рекурсивность сразу
для обширных классов функций (см., например, [17, с. 135–151]).
Используя минимизацию (µ-оператор) можно получать частично-определенные
функции из всюду определенных функций. Например, полагая что f(x,y) есть частично-

Страницы