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

Задача 558

Пусть заданы три функции: $f(x, y, z)=x y+z, g(x, y)=2 x+y$ , $h(x)=2 x^{2}$ . Определить, какой будет функция $F^{(2)}$ , задаваемая так: $f\left(h\left(\operatorname {id}_{1}^{2}\right), g\left(h\left(\operatorname {id}_{2}^{2}\right), \operatorname {id}_{2}^{2}\right), \operatorname {id}_{2}^{2}\right)$ ?

?

Задача 559

(а)(б)(в)

Определить, чему равно значение следующих о.р.ф.:

?

(а)

$f=\operatorname {Pr}\left[0, s\left(\operatorname {id}_{1}^{2}+\operatorname {id}_{1}^{2}\right)+\operatorname {id}_{2}^{2}\right]$ ;

(б)

$f=\operatorname {Pr}\left[0, s\left(\operatorname {id}_{1}^{2}\right)+s\left(\operatorname {id}_{1}^{2}\right)+\operatorname {id}_{2}^{2}\right]$ ;

(в)

$f=\operatorname {Pr}\left[0, s\left(3 \cdot \operatorname {id}_{1}^{2} \cdot s\left(\operatorname {id}_{1}^{2}\right)\right)+\operatorname {id}_{2}^{2}\right]$ .

Задача 560

О. р. ф. $f(x)$ задана следующим образом:

\operatorname {Pr}\left[0, s\left(\operatorname {id}_{1}^{2}\right)+s\left(\operatorname {id}_{1}^{2}\right)+\operatorname {id}_{1}^{2}+\operatorname {id}_{1}^{2}+\operatorname {id}_{2}^{2}+\operatorname {id}_{2}^{2}\right].

Доказать, что $f(x)=3 \cdot 2^{x+1}-4 x-6$ .

?

Задача 561

(а)(б)(в)

Найти значение $F(5)$ для следующих функций:

?

(а)

$F=\operatorname {Pr}[1, h]$ , где $h(y, z)=\left\lfloor 2^{z} / z^{2}\right\rfloor$ ;

(б)

$F=\operatorname {Pr}[1, h]$ , где $h(y, z)=\left\lfloor 2^{z} / z\right\rfloor$ ;

(в)

$F=\operatorname {Pr}[2, h]$ , где $h(y, z)=3 z-(2 y+1)$ .

Задача 562

Показать, что следующие функции являются о. р. ф.:

?

(а)

$\operatorname {pow}(x, y)=x^{y}$ — возведение в степень;

(б)

$\operatorname {fact}(x)=x!$ — факториал;

(в)

$\operatorname {if}(x, y, z)$ — условная операция,

\operatorname {if}(x, y, z)= \begin{cases} y, & \text{ если } x \neq 0 \\ z, & \text{ иначе }\end{cases}

(г)

$\min^{(n)}\left(x_{1}, \ldots , x_{n}\right)$ — наименьший из аргументов, $n>0$ ;

(д)

$\max^{(n)}\left(x_{1}, \ldots , x_{n}\right)$ — наибольший из аргументов, $n>0$ ;

(е)

$\operatorname {diff}=\left|x-y\right|$ — модуль разности;

(ж)

$\bmod (x, y)$ — остаток от деления $x$ на $y$ ;

(з)

$\operatorname {div}(x, y)=\lfloor x / y\rfloor$ — целочисленное частное.

Задача 563

Доказать, что если функция $f\left(x_{1}, \ldots , x_{n}\right)$ является ч.р. ф., то и функция $g\left(x_{1}, \ldots , x_{n}\right)=f\left(x_{i_{1}}, \ldots , x_{i_{n}}\right)$ является ч.р. ф. для каждой перестановки $(i_{1}, \ldots , i_{n})$ чисел $1,2, \ldots , n$ .

?

Задача 564

Говорят, что функция $h^{(n+1)}$ получена ограниченной минимизацией функции $f^{(n+1)}$ (это обозначается $h=\mu_{\lim } f$ ), если $h(\bar{x}, y)=y$ , когда $f(\bar{x}, y) \neq 0$ для всех $z<y$ , иначе $h(\bar{x}, y)$ равняется наименьшему $z<y$ , для которого $f(\bar{x}, z)=0$ . Доказать, что функцию $\mu_{\lim } f$ можно построить из $f$ и базисных функций при помощи суперпозиции и примитивной рекурсии.

?

Задача 565

Пусть $g\left(x_{1}, \ldots , x_{n-1}, x_{n}\right)$ — ч.р.ф., $a$ и $b>0$ — натуральные числа. Доказать, что функция

f\left(x_{1}, \ldots , x_{n-1}, x_{n}\right)= \begin{cases} a, & \text{ если } x_{n}<b \\ g\left(x_{1}, \ldots , x_{n-1}, x_{n}-b\right), & \text{ если } x_{n} \geqslant b\end{cases}

тоже является ч.р.ф.

?

Задача 566

Найти значение $F(9)$ и $F(17)$ для $F=\mu f$ и следующих функций $f^{(2)}$ . Определить, для какой из них будет выполнено $F(x)=\lfloor \sqrt{x}\rfloor$ :

?

(а)

$f(x, y)=y^{2} \div x$ ;

(б)

$f(x, y)=x-y^{2}$ ;

(в)

$f(x, y)=(x+1)-y^{2}$ ; $\circledast$

(г)

$f(x, y)=(x+1)-(y+1)^{2}$ ;

(д)

$f(x, y)=x \doteq (y+1)^{2}$ .

Задача 567

Определить, для какой из следующих функций $f^{(3)}$ будет выполнено $F(x)=\lfloor y / x\rfloor$ , где $F=\mu f$ и $x \neq 0$ :

?

(а)

$f(x, y, i)=y-i x$ ;

(б)

$f(x, y, i)=y-(i+1) x$ ;

(в)

$f(x, y, i)=(y+1)-i x$ ;

(г)

$f(x, y, i)=(y+1)-i(x+1)$ ;

(д)

$f(x, y, i)=(y+1) \div (i+1) x$ .

Задача 568

(а)(б)(в)(г)

Какие из следующих выражений определяют количество $\tau (x)$ различных делителей числа $x$ ?

?

(а)

$x-\sum_{i<x} \operatorname {test}(\bmod (x, s(i)))$ ;

(б)

$x-\sum_{i<x} \operatorname {not}(\bmod (x, s(i)))$ ;

(в)

$\sum_{i<x} \operatorname {test}(\bmod (x, s(i)))$ ;

(г)

$\sum_{i<x} \operatorname {not}(\bmod (x, s(i)))$ .

Задача 569

Показать, что следующие функции являются ч.р. ф.:

?

(а)

$\operatorname {rt}(n, x)=\lfloor \sqrt[n]{x}\rfloor$ — целая часть корня $n$ -й степени из $x$ ;

(б)

$\log (i, x)=\left\lfloor \log_{i} x\right\rfloor$ ;

(в)

$p(x)=1$ , если $x$ — простое число, и $p(x)=0$ в противном случае;

(г)

$\operatorname {pn}(k)-k$ -е простое число в порядке возрастания, $\operatorname {pn}(0)=2$ ;

(д)

$\sigma (x)$ — сумма делителей числа $x$ , считать, что $\sigma (0)=0$ ;

(е)

$\operatorname {digit}(n, m, i)$ - $i$ -я цифра в $m$ -ичном представлении числа $n$ : то есть если $n=\sum_{i=0}^{\infty } a_{i} m^{i}$ , где $0 \leqslant a_{i}<m$ , то $\operatorname {digit}(n, m, i)=a_{i}$ ;

(ж)

НОД $(x, y)$ — наибольший общий делитель чисел $x$ и $y$ .

Задача 570

Определить ч. р. ф. $l^{(1)}$ , значение которой равно $\log_{2} x$ , когда $x$ является степенью двойки, и неопределено в противном случае.

?

Задача 571

На евклидовой координатной плоскости дан круг $C$ с центром в точке $(100,100)$ радиусом 50. Доказать, что следующая функция $r^{(2)}$ является частично рекурсивной: $r(x, y)$ определено тогда и только тогда, когда точка $(x, y)$ находится вне круга $C$ , при этом её значение равно целой части расстояния от $(x, y)$ до круга (то есть до ближайшей к $(x, y)$ точки круга $C$ ).

?

Задача 572

О. р. ф., которая может быть построена без использования минимизации, называется примитивно рекурсивной. Пусть функции $g$ и $f$ примитивно рекурсивны, $h=\mu g, h-$ о. р. ф., и $h$ мажорируется функцией $f: h(\bar{x})<f(\bar{x})$ для всех $\bar{x}$ . Доказать, что $h$ тоже является примитивно рекурсивной.

?

Задача 573

Доказать, что если значения о. р. ф. $f(x)$ изменить на конечном множестве, то получившаяся функция $f^{\prime }(x)$ также будет о. р. ф.

?

Задача 574

Доказать, что из константы 0 и функций $\operatorname {id}_{m}^{n}$ с помощью суперпозиции и примитивной рекурсии нельзя получить функцию $s(x)=x+1$ и функцию $d(x)=2 x$ . Указание. Индукцией по построению функции доказать, что для всех таким образом построенных функций выполнено неравенство $f\left(x_{1}, \ldots , x_{n}\right)<2$ для произвольных $x_{1}, \ldots , x_{n}<2$ .

?

Задача 575

Пусть $f$ — взаимно однозначная на $\omega$ о.р. ф. Доказать, что обратная функция $f^{-1}$ тоже является о.р. ф., явно её построив.

?

Задача 576

Пусть $g\left(x_{1}, \ldots , x_{n}, y\right)$ — о. р. ф. Доказать, что функция

f\left(x_{1}, \ldots , x_{n}, y, z\right)= \begin{cases} \sum _{i=0}^{z} g\left(x_{1}, \ldots , x_{n}, y+i\right), & \text{ при } y \leqslant z, \\ 0, & \text{ при } y>z\end{cases}

общерекурсивна.

?

Задача 577

Доказать, что если функции $f\left(x_{1}, \ldots , x_{n}, y\right), g\left(x_{1}, \ldots , x_{n}, y\right)$ и $h\left(x_{1}, \ldots , x_{n}, y\right)$ общерекурсивны, то функция

\begin{aligned} & F\left(x_{1}, \ldots , x_{n}\right)=\min \left\{ y: f\left(x_{1}, \ldots , x_{n}, y\right)=0\right. \text{ или } \\ & \left.\quad g\left(x_{1}, \ldots , x_{n}, y\right)>h\left(x_{1}, \ldots , x_{n}, y\right)\right\} \end{aligned}

является ч.р.ф.

?

Задача 578

(а)(б)(в)

Допустим, что все пары $(x, y)$ натуральных чисел упорядочены по возрастанию суммы $x+y$ , а пары с одинаковой суммой — по возрастанию координаты $x$ . Этот порядок выглядит так:

\begin{aligned} & (0,0),(0,1),(1,0),(0,2),(1,1),(2,0), \ldots \\ & \quad \ldots ,(0, x+y),(1, x+y-1), \ldots ,(x, y), \ldots ,(x+y, 0), \ldots \end{aligned}

Пусть $\langle x, y\rangle$ — это номер пары $(x, y)$ в этом порядке (будем считать, что пара (0,0) имеет номер 0). Тогда функция $\langle$ , $\rangle взаимно однозначно$ нумерует все пары натуральных чисел.

?

(а)

Доказать, что $\langle x, y\rangle =\frac{(x+y)(x+y+1)}{2}+x$ .

(б)

Найти обратные функции $\left\rangle_{1}\right.$ и $\left\rangle_{2}\right.$ такие, что будут выполнены равенства $\langle \langle x, y\rangle \rangle_{1}=x,\langle \langle x, y\rangle \rangle_{2}=y$ и, следовательно, $\left\langle \langle z\rangle_{1},\langle z\rangle_{2}\right\rangle =z$ .

(в)

Показать, что все эти функции общерекурсивны.

Задача 579

Показать, что функция $F(x)$ из задачи 547 на стр. 168 является o. p. ф.

Указание. Показать сначала, что функция $g(x)=\langle F(x), F(x+1)\rangle$ является о. р. ф.

?

Задача 580

Другая функция, позволяющая нумеровать пары натуральных чисел, выглядит так: $c(x, y)=2^{x}(2 y+1)-1$ . Доказать, что сама $c$ и обратные к ней функции $c_{1}$ и $c_{2}$ (то есть $c_{1}(c(x, y))=x$ и $c_{2}(c(x, y))=y$ ) являются общерекурсивными.

?

Задача 581

(а)(б)(в)

Если задана взаимно однозначная нумерация пар $k$ (например, из задач 578 или 580), то можно индуктивно пронумеровать упорядоченные $n$ -ки произвольной длины:

\begin{aligned} K() & =0 \\ K\left(x_{1}, \ldots , x_{n}, x_{n+1}\right) & =k\left(k\left(k_{1}\left(K\left(x_{1}, \ldots , x_{n}\right)\right), x_{n+1}\right), n+1\right) \end{aligned}

?

(а)

Доказать, что функция $K$ взаимно однозначна.

(б)

Доказать, что функции $K^{(n)}\left(x_{1}, \ldots , x_{n}\right)$ общерекурсивны.

(в)

Доказать, что обратная к $K$ функция $K^{\prime }$ тоже является общерекурсивной:

K^{\prime }\left(K\left(x_{0}, \ldots , x_{n}\right), m\right)= \begin{cases} x_{m}, & \text{ при } m \leqslant n, \\ 0, & \text{ иначе. }\end{cases}

Задача 582

(а)(б)(в)

Ещё один способ кодирования конечных последовательностей натуральных чисел использует двоичную запись: последовательность $\left(n_{0}, n_{1}, \ldots , n_{k}\right)$ кодируется двоичным числом $1^{n_{k}} 01^{n_{k-1}} 0 \ldots 01^{n_{1}} 01^{n_{0}}$ (последовательности, которые получаются добавлением или удалением конечных нулей, не различаются).

?

(а)

Найти коды последовательностей $(2,3,0,1)$ и $(0,0,2,1,2)$ .

(б)

Определить, кодами каких последовательностей являются числа 169 и 19783.

(в)

Доказать, что функция $k(x, y)$ является общерекурсивной. Здесь $x$ — код последовательности, $y$ — номер элемента, значение функции равно этому элементу.

Задача 583

(а)(б)(в)

Функция Аккермана задана следующим образом:

\begin{aligned} A(0, y) & =y+1 \\ A(x+1,0) & =A(x, 1) \\ A(x+1, y+1) & =A(x, A(x+1, y)) \end{aligned}

?

(а)

Найти $A(1, y)$ и $A(2, y)$ для всех натуральных $y$ .

(б)

Доказать, что $A(3, y)=2^{y+3}-3$ .

(в)

Доказать, что функция Аккермана является общерекурсивной. Указание. С помощью функций $K$ и $K^{\prime }$ (задача 581 на противоположной странице) строить последовательности $(x_{1}, x_{2}, \ldots , x_{n}, z)$ такие, что

A(x, y)=A\left(x_{1}, A\left(x_{2}, \ldots , A\left(x_{n}, z\right) \ldots \right)\right).

Частично рекурсивные функции