Введение в схемы, автоматы и алгоритмы


Задачи


Задача 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).
  • предикаты равенства и неравенства:

     \def\text#1{#1} eq(x,y)=\left\{ \begin{array}{ll} 1,& \text{ если \ x=y}\\ 0,& \text{ если \ x\neq y}\end{array}\right. \qquad \overline{eq}(x)= \left\{ \begin{array}{ll} 0,& \text{ если \ x=y}\\ 1,& \text{ если \ x\neq y} \end{array}\right.

  • f(x) = 2^{2^x}
    .

Задача 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. Тогда и функция

 \def\text#1{#1} f(x_1,\ldots, x_n)=\left\{ \begin{array}{ll} a,& \text{ если \ x_n \leq b }\\ g(x_1,\ldots,x_n-b),& \text{ если \ x_n > b} \end{array}\right.

является частично (примитивно) рекурсивной.

Задача 8.4. Показать, что следующие функции являются частично ( примитивно) рекурсивными.

  • rt(n,x)=\lfloor\sqrt[n]{x}\rfloor
    - корень n-ой степени из x (целая часть).
  • log(i, x) =\lfloor \log_i x \rfloor
    (пусть при 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, т.е. если
    n=\sum_0^\infty a_i m^i
    , где 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) - примитивно рекурсивна. Доказать, что функция

\def\text#1{#1} f(x_1, ..., x_n,y,z)=\left\{ \begin{array}{ll} \sum_{i=0}^z g(x_1,...x_n,y+i),& \text{ при\ y \leq z}\\ 0,& \text{ при }\ y > z \end{array}\right.

примитивно рекурсивна.

Задача 8.9.

Доказать, что если функции f(x1,...,xn,y), g(x1,...,xn,y) и h(x1,..., xn,y) частично рекурсивны, то и функция




Начало  Назад  Вперед



Книжный магазин