что следующие функции являются частично
Задача 8.1. Показать, что следующие функции являются частично (примитивно) рекурсивными.
- exp(x,y) = xy;
- fact(x) = x ,!;
- min(x,y)= наименьшее из x и y;
- max(x,y)= наибольшее из x и y;
- div(x,y)= частное от деления y на x (пусть div(0,y)=y).
предикаты равенства и неравенства:
- .
Задача 8.2. Докажите, что если f(x1,…,xn) является ч.р.ф. (п.р.ф.), то и функция g(x1,…,xn)=f(x{i1},…,xin) является ч.р.ф. (п.р.ф.) для любой перестановки (i1, …, in) чисел 1,2,…,n.
Задача 8.3. Оператор сдвига. Пусть g(x1,…, xn) - частично (примитивно) рекурсивная функция, a и b >0 - числа из N. Тогда и функция
является частично (примитивно) рекурсивной.
Задача 8.4. Показать, что следующие функции являются частично ( примитивно) рекурсивными.
- - корень n-ой степени из x (целая часть).
- (пусть при i
{0,1} или x= 0 log(i,x) =0).
- p(x)=1, если x - простое число, и p(x)=0, если x составное.
- pn(k) - k-ое простое число в порядке возрастания (pn(0)=0, pn(1)=2, pn(2)=3, pn(3)=5...).
- t(x) = число pазличных делителей числа x (t(0)=0).
- d(n,m,i) - i-ый знак в m-ичном разложении числа n, т.е. если , где 0
ai
m-1, то d(n,m,i)=ai. - nod(x, y)= наибольший общий делитель чисел x и y (пусть nod(0,y)=nod(x,0) =0).
Задача 8.5.
Пусть F(x) задана соотношениями F(0)=1, F(1)=1, F(x+2)= F(x)+F(x+1) ( элементы последовательности F(x) называются числами Фибоначчи). Покажите, что функция F(x) примитивно рекурсивна.
(Указание: покажите сначала, что функция g(x)= 2F(x) 3F(x+1) примитивно рекурсивна.)
Задача 8.6.
Докажите, что если значения общерекурсивной функции f(x) изменить на конечном множестве, то получившаяся функция f'(x) также будет общерекурсивной.
Задача 8.7.
Доказать, что из функции o(x)=0 и из функций выбора Imn(x1,...,xn)=xm с помощью суперпозиции и примитивной рекурсии нельзя получить функцию s(x)=x+1 и функцию d(x) =2*x.
Задача 8.8. Пусть g(x1,...,xn,y) - примитивно рекурсивна. Доказать, что функция
примитивно рекурсивна.
Задача 8.9.
Доказать, что если функции f(x1,...,xn,y), g(x1,...,xn,y) и h(x1,..., xn,y) частично рекурсивны, то и функция
является частично рекурсивной.
Задача 8.10. Докажите, что определенные выше функция нумерации n-ок cn(x1, … , xn) и обратные ей функции выбора i-го элемента набора cni(z) (1
Задача 8.11. Предположим, что все пары (x,y) натуральных чисел упорядочены по возрастанию суммы (x+y), а внутри группы пар с одинаковой суммой - по возрастанию x-координаты. Этот порядок выглядит так: (0,0), (0,1), (1,0),(0,2),(1,1), (2,0),… , (0,x+y), (1, x+y-1), … , (x,y), … , (x+y, 0), … . Пусть d(x,y) - это номер пары (x,y) в этом порядке (будем считать, что пара (0,0) имеет номер 0). Тогда функция d2 однозначно нумерует все пары.
- Докажите, что
- Найдите обратные функции d1(z) и d2(z) такие, что d1(d(x,y))=x, d2(d(x,y))= y и, следовательно, d(d1(z), d2(z))=z.
