Банк задач по математике

Пример 4.21

Покажите, что add $(m, n)=m+n$ является примитивно рекурсивной.

?

Пример 4.22

Покажите, что mult $(m, n)=m n$ является примитивно рекурсивной.

?

Пример 4.23

Покажите, что постоянные функции $K_{j}^{k}\left(n_{1}, \cdots , n_{k}\right)=j$ , $k, j \geq 1$ , являются примитивно рекурсивными.

?

Пример 4.24

Покажите, что функция minus: $\mathbf{N}^{2} \rightarrow \mathbf{N}$ , определённая как

\operatorname {minus}(m, n)=m-n= \begin{cases} 0 & \text{ если } m \leq n, \\ m-n & \text{ если } m>n,\end{cases}

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

?

Пример 4.25

Предположим, что $f: \mathbf{N} \rightarrow \mathbf{N}$ примитивно рекурсивна. Тогда функция $g: \mathbf{N}^{2} \rightarrow \mathbf{N}$ , определённая как

g(m, n)=f^{(n)}(m) \stackrel{\text{ def }}{=} \underbrace{f(f(\cdots (f(m)) \cdots )),}_{n}

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

?

Пример 4.26

(a)(b)(c)(d)

Покажите, что следующие функции примитивно рекурсивны:

?

(a)

$\operatorname {neg}(x)= \begin{cases} 0 & \text{ если } x \geq 1, \\ 1 & \text{ если } x=0.\end{cases}$

(b)

$\operatorname {and}(x, y)= \begin{cases} 1 & \text{ если } x \geq 1 \text{ и } y \geq 1, \\ 0 & \text{ иначе. }\end{cases}$

(c)

$\operatorname {or}(x, y)= \begin{cases} 1 & \text{ если } x \geq 1 \text{ или } y \geq 1, \\ 0 & \text{ иначе. }\end{cases}$

(d)

$\operatorname {if\text{-}then\text{-}else}(x, y, z)= \begin{cases} y & \text{ если } x \geq 1, \\ z & \text{ иначе }.\end{cases}$

Пример 4.27

Покажите, что следующие функции примитивно рекурсивны:

?

(a)

$\operatorname {eq}(x, y)= \begin{cases} 1 & \text{ если } x=y, \\ 0 & \text{ если } x \neq y.\end{cases}$

(b)

$\operatorname {gr}(x, y)= \begin{cases} 1 & \text{ если } x>y, \\ 0 & \text{ если } x \leq y.\end{cases}$

(c)

$\operatorname {geq}(x, y)= \begin{cases} 1 & \text{ если } x \geq y, \\ 0 & \text{ если } x<y.\end{cases}$

(d)

$\operatorname {ls}(x, y)= \begin{cases} 1 & \text{ если } x<y, \\ 0 & \text{ если } x \geq y.\end{cases}$

(e)

$\operatorname {leq}(x, y)= \begin{cases} 1 & \text{ если } x \leq y, \\ 0 & \text{ если } x>y.\end{cases}$

Пример 4.28

Для каждого $k \geq 1$ функция $\max^{k}\left(n_{1}, n_{2}, \ldots , n_{k}\right)= \max \left\{ n_{1}, n_{2}, \ldots , n_{k}\right\}$ примитивно рекурсивна.

?

Пример 4.30

(a)(b)(c)

Следующие функции примитивно рекурсивны.

?

(a)

$q u o t(m, n)= \begin{cases} \left\lfloor \frac{m}{n}\right\rfloor & \text{ если } n>0, \\ 0 & \text{ иначе. }\end{cases}$

(b)

$\bmod (m, n)= \begin{cases} m-\left\lfloor \frac{m}{n}\right\rfloor \cdot n & \text{ если } n>0, \\ 0 & \text{ иначе }.\end{cases}$

(c)

prime $(n)= \begin{cases} 1 & \text{ если } n \text{ простое число }, \\ 0 & \text{ иначе }.\end{cases}$

Пример 4.31

Пусть $f(0)=1$ и при $n \geq 1$ $f(n)=$ $n$ -я цифра справа от десятичной точки в десятичном разложении $\sqrt{2}$ . Докажите, что $f$ примитивно рекурсивна.

?

Задача 4.6.1

Покажите, что следующие функции примитивно рекурсивны:

?

(a)

$\operatorname {factorial}(n)=n!$ .

(b)

$\left.f_{1}(n)=n^{n^{\cdot n}}\right\} n$ уровней. [Подсказка: сначала рассмотрите более общую функцию $\left.g_{1}(n, m)=n^{n^{. n}}\right\} m$ уровней.]

(c)

$f_{2}(n)=\left\lfloor \log_{2} n\right\rfloor$ .

(d)

$f_{3}(n)= \begin{cases} 1 & \text{ если } n \text{ является суммой двух простых чисел, } \\ 0 & \text{ иначе. }\end{cases}$

(e)

$\phi (n)=$ число простых чисел, не превосходящих $n$ .

(f)

$\operatorname {lcm}(n, m)=$ наименьшее общее кратное $n$ и $m$ .

(g)

$s(n)=$ число цифр в десятичной записи $n$ .

(h)

$h(n, m)=$ $m$ -я по значимости цифра десятичной записи $n$ , если $1 \leq m \leq s(n)$ (и $h(n, m)=0$ , если $m=0$ или $m>s(n)$ ).

Задача 4.6.2

Что не так со следующим доказательством примера 4.25?

Мы докажем это индукцией по $n$ , как в примере 4.28. При $n=0$ $g(m, n)=\pi_{1}^{1}(n)$ ; следовательно, $g(m, 0)$ примитивно рекурсивна. При $n \geq 0$ $g(m, n+1)=f(g(m, n))$ . Поскольку $f$ примитивно рекурсивна и, по индуктивному предположению, $g(m, n)$ примитивно рекурсивна, получаем, что $g(m, n+1)$ также примитивно рекурсивна. Отсюда следует, что $g(m, n)$ примитивно рекурсивна при всех $n \geq 0$ , а значит, $g$ примитивно рекурсивна.

?

Задача 4.6.3

Предположим, что $R: \mathbf{N}^{k+1} \rightarrow \mathbf{N}$ — примитивно рекурсивный предикат. Покажите, что следующая функция $f: \mathbf{N}^{k+1} \rightarrow \mathbf{N}$ также примитивно рекурсивна:

f\left(n_{1}, \ldots , n_{k}, m\right)= \begin{cases} (\max i)_{i \leq m} R\left(n_{1}, \ldots , n_{k}, i\right) \\ & \text{ если }(\exists i)_{i \leq m} R\left(n_{1}, \ldots , n_{k}, i\right) \\ 0 & \text{ иначе. }\end{cases}

?

Задача 4.6.4

(a)(b)

Предположим, что $f: \mathbf{N}^{k+1} \rightarrow \mathbf{N}$ примитивно рекурсивна. Покажите, что следующие функции также примитивно рекурсивны:

?

(a)

$g\left(n_{1}, \ldots , n_{k}, m\right)=\sum_{i=0}^{m} f\left(n_{1}, \ldots , n_{k}, i\right)$ .

(b)

$h\left(n_{1}, \ldots , n_{k}, m\right)=\prod_{i=0}^{m} f\left(n_{1}, \ldots , n_{k}, i\right)$ .

Задача 4.6.5

Предположим, что $f: \mathbf{N} \rightarrow \mathbf{N}$ примитивно рекурсивна и удовлетворяет $f(0)=0$ и $f(n)<f(n+1)$ при всех $n \geq 0$ . Покажите, что функция $h(m)=[$ целое число $n$ такое, что $f(n) \leq m<f(n+1)]$ также примитивно рекурсивна.

?

Задача 4.6.6

Предположим, что $f: \mathbf{N} \rightarrow \mathbf{N}$ и $g: \mathbf{N} \rightarrow \mathbf{N}$ обе примитивно рекурсивны. Покажите, что следующая функция $h: \mathbf{N}^{2} \rightarrow \mathbf{N}$ также примитивно рекурсивна:

\begin{aligned} h(n, 0) & =f(n) \\ h(n, m+1) & =g\left(h\left(n,\left\lfloor \frac{m+1}{2}\right\rfloor \right)\right). \end{aligned}

?

Задача 4.6.7

Предположим, что $f: \mathbf{N} \rightarrow \mathbf{N}$ примитивно рекурсивна. Покажите, что следующая функция $g: \mathbf{N}^{2} \rightarrow \mathbf{N}$ также примитивно рекурсивна:

\begin{aligned} g(n, 0) & =f(n) \\ g(n, m+1) & =g(g(n, m), m) \end{aligned}

?

Примитивно рекурсивные функции