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

Пример 4.32

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

\pi (i, j)=\frac{(i+j)(i+j+1)}{2}+j,

является функцией спаривания.

?

Пример 4.33

Покажите, что функция Фибоначчи примитивно рекурсивна.

?

Пример 4.34

Покажите, что функция

\tau \left(n_{1}, \ldots , n_{k-1}, n_{k}\right)=\left\langle k-1,\left\langle n_{1},\left\langle \cdots \left\langle n_{k-1}, n_{k}\right\rangle \cdots \right\rangle \right\rangle \right\rangle

является гёделевой нумерацией.

?

Пример 4.35

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

?

(a)

$\operatorname {list}(m, 0)=0$ и $\operatorname {list}(m, k)=[\underbrace{m, m, \ldots , m}_{k}]$ , если $k \geq 1$ .

(b)

$\operatorname {find}\left(\left[n_{1}, \ldots , n_{k}\right], m\right)= \begin{cases} \min \left\{ i \mid 1 \leq i \leq k, n_{i}=m\right\} & \text{ если такое } i \text{ существует }, \\ 0 & \text{ иначе } \end{cases}$

(c)

$\operatorname {replace}\left(\left[n_{1}, \ldots , n_{k}\right], m, i\right) = \begin{cases} \left[n_{1}, \ldots , n_{i-1}, m, n_{i+1}, \ldots , n_{k}\right] & \text{ если } 1 \leq i \leq k, \\ \left[n_{1}, \ldots , n_{k}\right] & \text{ иначе. } \end{cases}$

(d)

$\operatorname {conseq}\left(\left[n_{1}, \ldots , n_{k}\right],\left[m_{1}, \ldots , m_{\ell }\right]\right)=\left[n_{1}, \ldots , n_{k}, m_{1}, \ldots , m_{\ell }\right]$ .

(e)

$\operatorname {subseq}\left(\left[n_{1}, \ldots , n_{k}\right], i, \ell \right)$

= \begin{cases} {\left[n_{i}, n_{i+1}, \ldots , n_{i+\ell -1}\right]} & \text{ если } 1 \leq i \leq k, 1 \leq \ell \leq k-i+1 \\ 0 & \text{ иначе. }\end{cases}

Пример 4.36

Покажите, что функция $f: \mathbf{N} \rightarrow \mathbf{N}$ , определённая как $f(0)=1$ , $f(n+1)=f(0)^{n+1}+f(1)^{n}+\ldots +f(n)^{1}$ , примитивно рекурсивна.

?

Пример 4.38

Функция sort : $\mathbf{N} \rightarrow \mathbf{N}$ отображает число $\left[n_{1}, n_{2}, \ldots , n_{k}\right]$ в число $\left[n_{p_{1}}, n_{p_{2}}, \ldots , n_{p_{k}}\right]$ , где $\left(p_{1}, p_{2}, \ldots , p_{k}\right)$ — перестановка $(1,2, \ldots , k)$ такая, что $n_{p_{1}} \leq n_{p_{2}} \leq \cdots \leq n_{p_{k}}$ . Покажите, что sort примитивно рекурсивна.

?

Задача 4.7.1

(a)(b)

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

?

(a)

$f_{1}(n, m)=2^{n}(2 m+1)-1$ .

(b)

$f_{2}(n, m)=\max (n, m)^{2}+m+g(m, n)$ , где $g(m, n)=n$ , если $m \geq n$ , и $g(m, n)=0$ , если $n>m$ .

Задача 4.7.2

(a)(b)

Пусть $\tau_{1}: \bigcup_{k=1}^{\infty } \mathbf{N}^{k} \rightarrow \mathbf{N}$ определена как $f\left(n_{1}, \ldots , n_{k}\right)=2^{n_{1}} 3^{n_{2}} \cdots p_{k}^{n_{k}}$ , где $p_{k}$ — $k$ -е простое число.

?

(a)

Покажите, что $\tau_{1}$ сюръективна, примитивно рекурсивна и монотонна. Также покажите, что $\tau_{1}$ почти инъективна в том смысле, что если $\tau_{1}\left(n_{1}, \ldots , n_{k}\right)=\tau_{1}\left(m_{1}, \ldots , m_{\ell }\right)$ и если $k \leq \ell$ , то $n_{i}=m_{i}$ при всех $i$ , $1 \leq i \leq k$ , и $m_{j}=0$ при всех $j$ , $k<j \leq \ell$ .

(b)

Проверьте, что если использовать $\tau_{1}$ в качестве гёделевой нумерации, то функции size, item и функции из примера 4.35 остаются примитивно рекурсивными. (Здесь $\operatorname {size}(n)$ — число элементов в последовательности $n$ , не считая завершающих нулей.)

Задача 4.7.3

Пусть $n_{1}, n_{2}, \ldots , n_{k}$ — $k$ неотрицательных целых чисел. Докажите, что если $1 \leq i_{1}< i_{2}<\cdots <i_{\ell } \leq k$ , то $\left[n_{i_{1}}, n_{i_{2}}, \ldots , n_{i_{\ell }}\right] \leq \left[n_{1}, n_{2}, \ldots , n_{k}\right]$ .

?

Задача 4.7.4

Предположим, что $f(n, 0)=g(n)$ и $f(n, m+1)=h(n, f(n, k(m)))$ для некоторых примитивно рекурсивных $g, h$ и $k$ . Также предположим, что $k(m) \leq m$ при всех $m>0$ . Докажите, что $f$ также примитивно рекурсивна. (Заметим, что решение 1 примера 4.38 фактически использовало этот результат.)

?

Задача 4.7.5

(a)(b)

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

?

(a)

$f(n, m)=$ число вхождений целого числа $m$ в последовательность $n=\left[n_{1}, \ldots , n_{k}\right]$ .

(b)

$g(n)=\left[d_{k}, d_{k-1}, \ldots , d_{0}\right]$ , где $d_{k} d_{k-1} \cdots d_{0}$ — десятичная запись $n$ (например, $g(2801)=[2,8,0,1]$ ).

Задача 4.7.6

(a)(b)

Мы можем расширить понятие примитивно рекурсивных функций на функции из $\mathbf{Z}^{k}$ в $\mathbf{Z}$ , где $\mathbf{Z}$ — множество целых чисел. Всё, что для этого нужно, — это рассматривать пару $\left\langle n_{1}, n_{2}\right\rangle$ как представление целого числа из $\mathbf{Z}$ : если $n_{1}>0$ , то она представляет $n_{2}$ , иначе она представляет $-n_{2}$ . Покажите, что следующие функции над целыми числами примитивно рекурсивны:

?

(a)

$\operatorname {inner}(n, m)=$ скалярное произведение двух $k$ -мерных векторов $n$ и $m$ , если $\operatorname {size}(n)=\operatorname {size}(m)=2 k$ (и равно 0 в противном случае). (Мы рассматриваем список $\left[n_{1}, n_{2}, \ldots , n_{2 k}\right]$ как $k$ -мерный целочисленный вектор, $i$ -й элемент которого — это целое число, представленное парой $\left\langle n_{2 i-1}, n_{2 i}\right\rangle$ ; то есть оно равно $n_{2 i}$ , если $n_{2 i-1}>0$ , и равно $-n_{2 i}$ , если $n_{2 i-1}=0$ .)

(b)

$\operatorname {det}(n)=$ определитель матрицы $n$ , если $\operatorname {size}(n)=2 k^{2}$ для некоторого $k \geq 1$ (и равен 0 в противном случае). (Мы рассматриваем $\left[n_{1}, n_{2}, \ldots , n_{2 k^{2}}\right]$ как целочисленную матрицу $M$ размера $k \times k$ , где $M_{i j}$ равно целому числу, представленному парой $\left\langle n_{2(i-1) k+2 j-1}, n_{2(i-1) k+2 j}\right\rangle$ .)

Задача 4.7.7

Мы говорим, что последовательность $n=\left[n_{1}, \ldots , n_{k}\right]$ сбалансирована, если существует разбиение $\left\{ 1,2, \ldots , k\right\}$ на два подмножества $B$ и $C$ (то есть $B \cup C=\left\{ 1,2, \ldots , k\right\}$ и $B \cap C=\emptyset$ ) такое, что $\sum_{i \in B} n_{i}=\sum_{j \in C} n_{j}$ . Докажите, что предикат $[n$ сбалансирована $]$ примитивно рекурсивен.

?

Задача 4.7.8

(a)(b)

?

(a)

Покажите, что функция $\operatorname {merge}(n, m)$ , которая объединяет две отсортированные последовательности в одну отсортированную последовательность (и выдаёт 0, если хотя бы одна из двух входных последовательностей не отсортирована), примитивно рекурсивна.

(b)

Докажите, что sort примитивно рекурсивна, используя алгоритм сортировки слиянием.

Задача 4.7.9

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

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

?

Задача 4.7.10

Предположим, что $g_{1}, g_{2}$ и $h$ все примитивно рекурсивны. Покажите, что следующая функция $f$ примитивно рекурсивна:

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

?

Задача 4.7.11

Предположим, что $g_{1}, g_{2}$ и $h$ все примитивно рекурсивны. Покажите, что следующая функция $f$ примитивно рекурсивна:

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

?

Задача 4.7.12

Предположим, что $g_{1}, g_{2}, h_{1}$ и $h_{2}$ все примитивно рекурсивны. Пусть $f_{1}$ и $f_{2}$ — функции, определённые следующими формулами:

\begin{aligned} f_{1}(m, 0) & =g_{1}(m) \\ f_{2}(m, 0) & =g_{2}(m) \\ f_{1}(m, n+1) & =h_{1}\left(m, n, f_{1}(m, n), f_{2}(m, n)\right) \\ f_{2}(m, n+1) & =h_{2}\left(m, n, f_{1}(m, n), f_{2}(m, n)\right) \end{aligned}

Покажите, что $f_{1}$ и $f_{2}$ обе примитивно рекурсивны:

?

Функции сопряжения и гёделевская нумерация