 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Операции примитивной рекурсии
|
|
Операция примитивной рекурсии позволяет строить n+1 одноместную функцию по двум заданным функциям, одна – n - местная, вторая – n+2-местная. f от n+1
g от n
h от n+2
Пусть заданы частичные арифметические функции g(x1,…,xn) и h(x1,…,xn,xn+1, xn+2). Тогда функция f получается из g и h с помощью применения рекурсии:
f(x1,x2,…xn,0) = g(x1,x2,…xn)
f(x1,x2,…xn,y+1) = h (x1,x2,…xn,y, f(x1,x2,…xn,y))
Любая функция с меньшим количеством аргументов может быть получена из функции с большим количеством аргументов.
На основе данного определения можно определить функцию константу.
f(0) = a
f(x+1) = h(x0,f(x))
Если функции g и h существуют, то необходимо установить существует ли функция f получаемая примитивной рекурсией и будет ли она единственная.
f(x1,…,xn,0) = g(x1,…,xn)
f(x1,…,xn,1) = h(x1,…,xn,0,g(x1,…,xn))
f(x1,…,xn,2) = h(x1,…,xn,1,h(x1,…,xn,1))
…………………………………………..
f(x1,…,xn,m+1) = h(x1,…,xn,m,f(x1,…,xn,m))
Вычислим любые значения этой функции
f = x+y
g(x) = x – функция повторения
h(x,y,z) = z+1 – функция следования
f(x,0) = x
f(x,1) = h(x,0,x) = x+1
f(x,2) = h(x,1,x+1) = x+2
Двухместную функцию x*y можно вычислить, используя функции
f = xy
g(x) = 0
h(x,y,z) = z+x
В теории алгоритмов есть операция вычитания:
f = x 
y = 
Дата публикования: 2014-11-26; Прочитано: 1056 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
