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

Задача III.1.1

Доказать, что любая примитивно рекурсивная функция всюду определена.

?

Задача III.1.2

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

Доказать, что если функция $f^{n}(x_{1}, \ldots , x_{n})$ примитивно рекурсивна, то следующие функции примитивно рекурсивны:

?

(а)

$f_{1}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, x_{1}, \ldots , x_{n})$ (перестановка аргументов);

(б)

$f_{2}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, \ldots , x_{n}, x_{1})$ (циклическая перестановка аргументов);

(в)

$f_{3}(x_{1}, \ldots , x_{n}, x_{n+1}) = f(x_{1}, \ldots , x_{n})$ (введение фиктивного аргумента);

(г)

$f_{4}(x_{1}, \ldots , x_{n-1}) = f(x_{1}, x_{1}, \ldots , x_{n-1})$ (отождествление аргументов).

Задача III.1.3

Какие функции получаются из простейших с помощью лишь суперпозиций?

?

Задача III.1.4

Доказать, что из $o^{1}$ и $I_{m}^{n}$ с помощью суперпозиций и схем примитивной рекурсии нельзя получить функции $x+1$ и $2x$ .

?

Задача III.1.5

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

?

(а)

$f(x) = x + n$ ;

(б)

$f(x) = n$ ;

(в)

$f(x, y) = x + y$ ;

(г)

$f(x, y) = x \cdot y$ ;

(д)

$f(x, y) = x^{y}$ (здесь $0^{0} = 1$ );

(е)

$f(x, y) = x!$ (здесь $0! = 1$ ).

Задача III.1.6

(а)(б)

Какая функция получается из $g$ и $h$ с помощью схемы примитивной рекурсии:

?

(а)

$g(x) = x$ , $h(x, y, z) = z^{x}$ ;

(б)

$g(x) = x$ , $h(x, y, z) = x^{z}$ ?

Задача III.1.7

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

?

(а)

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

(б)

$\overline{\operatorname {sg}}(x) = \begin{cases} 0, & \text{если } x > 0, \\ 1, & \text{если } x = 0; \end{cases}$

(в)

$x \symdiff 1 = \begin{cases} 0, & \text{если } x = 0, \\ x - 1, & \text{если } x > 0; \end{cases}$

(г)

$x \symdiff y = \begin{cases} 0, & \text{если } x \leq y, \\ x - y, & \text{если } x > y; \end{cases}$

(д)

$\left|x - y\right|$ ;

(е)

$\max (x, y)$ ;

(ж)

$\min (x, y)$ .

Задача III.1.8

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

Доказать следующие равенства:

?

(а)

$x \symdiff y = s(x) \symdiff s(y)$ ;

(б)

$x + (y \symdiff x) = y + (x \symdiff y)$ ;

(в)

$x \symdiff (y+z) = (x \symdiff y) \symdiff z$ ;

(г)

$(x \symdiff y) \symdiff z = (x \symdiff z) \symdiff y$ .

Задача III.1.9

Пусть $g^{n+1}, \alpha^{m}, \beta^{m}$ примитивно рекурсивные функции. Доказать, что следующие функции примитивно рекурсивны:

?

(а)

$f^{n+1}(x_{1}, \ldots , x_{n}, x_{n+1}) = \displaystyle \sum_{i=0}^{x_{n+1}} g(x_{1}, \ldots , x_{n}, i)$ ;

(б)

$f^{n+2}(x_{1}, \ldots , x_{n}, y, z) = \begin{cases} \displaystyle \sum_{i=y}^{z} g(x_{1}, \ldots , x_{n}, i), & \text{если } y \leq z, \\ 0, & \text{если } y > z; \end{cases}$

(в)

$f^{n+m}(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m}) = \begin{cases} \displaystyle \sum_{i=\alpha (y_{1}, \ldots , y_{m})}^{\beta (y_{1}, \ldots , y_{m})} g(x_{1}, \ldots , x_{n}, i), & \text{если } \alpha (y_{1}, \ldots , y_{m}) \leq \beta (y_{1}, \ldots , y_{m}), \\ 0, & \text{в остальных случаях;} \end{cases}$

(г)

$f^{n+1}(x_{1}, \ldots , x_{n}, x_{n+1}) = \displaystyle \prod_{i=0}^{x_{n+1}} g(x_{1}, \ldots , x_{n}, i)$ ;

(д)

$f^{n+2}(x_{1}, \ldots , x_{n}, y, z) = \begin{cases} \displaystyle \prod_{i=y}^{z} g(x_{1}, \ldots , x_{n}, i), & \text{если } y \leq z, \\ 0, & \text{если } y > z; \end{cases}$

(е)

$f^{n+m}(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m}) = \begin{cases} \displaystyle \prod_{i=\alpha (y_{1}, \ldots , y_{m})}^{\beta (y_{1}, \ldots , y_{m})} g(x_{1}, \ldots , x_{n}, i), & \text{если } \alpha (y_{1}, \ldots , y_{m}) \leq \beta (y_{1}, \ldots , y_{m}), \\ 0, & \text{в остальных случаях.} \end{cases}$

Задача III.1.10

Доказать, что если $f$ получается из примитивно рекурсивных функций $g$ и $h$ с помощью ограниченного $\mu$ -оператора, то $f$ примитивно рекурсивна.

?

Задача III.1.11

Пусть функции $f_{0}^{n}, f_{1}^{n}, \ldots , f_{s}^{n}$ обладают следующим свойством: для любых натуральных значений $x_{1}, \ldots , x_{n}$ одна и только одна из этих функций равна $0$ . Скажем, что функция $g^{n}$ кусочно задана, если

g^{n}(x_{1}, \ldots , x_{n}) = \begin{cases} h_{0}^{n}(x_{1}, \ldots , x_{n}), & \text{если } f_{0}^{n}(x_{1}, \ldots , x_{n}) = 0, \\ \makebox[0pt][l]{\dotfill } \\ h_{s}^{n}(x_{1}, \ldots , x_{n}), & \text{если } f_{s}^{n}(x_{1}, \ldots , x_{n}) = 0. \end{cases}

Доказать, что если функции $h_{0}^{n}, \ldots , h_{s}^{n}, f_{0}^{n}, \ldots , f_{s}^{n}$ примитивно рекурсивны, то $g^{n}$ примитивно рекурсивна.

?

Задача III.1.12

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

?

(а)

$\left[\frac{x}{y}\right]$ --- частное от деления $x$ на $y$ (здесь $\left[\frac{x}{0}\right] = x$ );

(б)

$\operatorname {rest}(x, y)$ --- остаток от деления $x$ на $y$ (здесь $\operatorname {rest}(x, 0) = x$ );

(в)

$\tau (x)$ --- число делителей числа $x$ , где $\tau (0) = 0$ ;

(г)

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

(д)

$\operatorname {lh}(x)$ --- число простых делителей числа $x$ , где $\operatorname {lh}(0) = 0$ ;

(е)

$\pi (x)$ --- число простых чисел, не превосходящих $x$ ;

(ж)

$k(x, y)$ --- наименьшее общее кратное чисел $x$ и $y$ , где $k(x, 0) = k(0, y) = 0$ ;

(з)

$d(x, y)$ --- наибольший общий делитель чисел $x$ и $y$ , где $d(0, 0) = 0$ ;

(и)

$p(x)$ --- $x$ -е простое число ( $p(0) = 2$ , $p(1) = 3$ , $p(2) = 5, \ldots$ );

(к)

$\operatorname {long}(x)$ --- номер наибольшего простого делителя числа $x$ ;

(л)

$\operatorname {ex}(x, y)$ --- показатель степени $x$ -го простого числа $p(x)$ в каноническом разложении на простые множители числа $y$ , где $\operatorname {ex}(x, 0) = 0$ ;

(м)

$\left[\sqrt{x}\right]$ ;

(н)

$\left[\sqrt[y]{x}\right]$ , где $\left[\sqrt[0]{x}\right] = x$ ;

(о)

$\left[x\sqrt{2}\right]$ ;

(п)

$\left[e \cdot x\right]$ ;

(р)

$\left[e^{x}\right]$ ;

(с)

$C_{x}^{y}$ (здесь $C_{x}^{y} = 1$ при $y \leq x$ ).

Задача III.1.13

(а)(б)

?

(а)

Доказать, что функция

c(x, y) = \frac{(x+y)^{2} + 3x + y}{2}

(канторовская нумерующая функция) осуществляет взаимно однозначное соответствие между $\mathbb {N}^{2}$ и $\mathbb {N}$ (нумерует пары натуральных чисел).

(б)

Пусть $l(x)$ и $r(x)$ таковы, что

c(l(x), r(x)) = x.

Доказать, что $l(x)$ и $r(x)$ примитивно рекурсивны и $l(c(x, y)) = x$ , $r(c(x, y)) = y$ .

Задача III.1.14

(а)(б)(в)

Для каждого $n \geq 1$ определим функции

c^{1}(x_{1}) = x_{1}, \qquad c^{n+1}(x_{1}, x_{2}, x_{3}, \ldots , x_{n+1}) = c^{n}(c(x_{1}, x_{2}), x_{3}, \ldots , x_{n+1})

(см. задачу III.1.13).

Пусть $c_{i}^{n}$ ( $1 \leq i \leq n$ ) таковы, что $c^{n}(c_{1}^{n}(x), \ldots , c_{n}^{n}(x)) = x$ .

?

(а)

Доказать тождества

c_{i}^{n}(c^{n}(x_{1}, \ldots , x_{n})) = x_{i} \ \text{для } 1 \leq i \leq n.

(б)

Доказать, что функции $c^{n}$ и $c_{i}^{n}$ примитивно рекурсивны.

(в)

Доказать, что функции $c^{n}(x_{1}, \ldots , x_{n})$ осуществляют взаимно однозначные соответствия между $\mathbb {N}^{n}$ и $\mathbb {N}$ (нумеруют кортежи натуральных чисел длины $n$ ).

Задача III.1.15

Как из одноместных частично рекурсивных функций и функций $c^{n}(x_{1}, \ldots , x_{n})$ получить все частично рекурсивные функции?

?

Задача III.1.16

(а)(б)

Назовем одноместную функцию $f(x)$ функцией большого размаха, если она каждое натуральное число принимает в качестве своего значения бесконечное число раз.

?

(а)

Пусть пара функций $\langle f_{1}(x), f_{2}(x) \rangle$ отображает $\mathbb {N}$ на $\mathbb {N}^{2}$ . Доказать, что $f_{1}(x)$ и $f_{2}(x)$ --- функции большого размаха.

(б)

Пусть $f_{1}(x)$ --- произвольная примитивно рекурсивная функция большого размаха. Построить примитивно рекурсивную функцию $f_{2}(x)$ так, чтобы функции $f_{1}(x)$ и $f_{2}(x)$ осуществляли взаимно однозначное соответствие между $\mathbb {N}$ и $\mathbb {N}^{2}$ .

Задача III.1.17

Рассмотрим функцию Гёделя

\beta (x, y, z) = \operatorname {rest}(x, 1 + y(z+1)).

Доказать, что, какова бы ни была конечная последовательность натуральных чисел $a_{1}, \ldots , a_{n}$ , система уравнений

\begin{cases} \beta (x, y, 0) = \alpha _{0}, \\ \makebox[0pt][l]{\dotfill } \\ \beta (x, y, n) = \alpha _{n}, \end{cases}

имеет по меньшей мере одно решение $x, y$ .

?

Задача III.1.18

Доказать, что если функции $g, h, t_{1}, \ldots , t_{s}$ примитивно рекурсивны и $f$ получается из них возвратной рекурсией, то функция $f$ примитивно рекурсивна.

?

Задача III.1.19

Доказать, что функция, перечисляющая по порядку числа Фибоначчи:

\begin{cases} f(0) = 0, \quad f(1) = 1, \\ f(n+2) = f(n) + f(n+1), \end{cases}

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

?

Задача III.1.20

Пусть функции $f$ и $g$ определены следующим образом:

\begin{cases} f(0) = a, \quad g(0) = b, \\ f(x+1) = h_{1}(x, f(x), g(x)), \\ g(x+1) = h_{2}(x, f(x), g(x)). \end{cases}

Доказать, что если функции $h_{1}$ и $h_{2}$ примитивно рекурсивны, то функции $f$ и $g$ примитивно рекурсивны.

?

Задача III.1.21

Пусть $f_{1}^{n+1}, \ldots , f_{k}^{n+1}$ определены с помощью совместной рекурсии:

\begin{cases} f_{i}^{n+1}(x_{1}, \ldots , x_{n}, 0) = g_{i}^{n}(x_{1}, \ldots , x_{n}), \\ f_{i}^{n+1}(x_{1}, \ldots , x_{n}, y+1) = \\ \hphantom {f_{i}^{n+1}(x_{1}, \ldots , x_{n}, y+1) =} \, h_{i}^{n+k+1}(x_{1}, \ldots , x_{n}, y, f_{1}(x_{1}, \ldots , x_{n}, y), \ldots , f_{k}(x_{1}, \ldots , x_{n}, y)) \end{cases}

для всех $1 \leq i \leq k$ .

Доказать, что если функции $g_{1}, \ldots , g_{k}, h_{1}, \ldots , h_{k}$ примитивно рекурсивны, то функции $f_{1}, \ldots , f_{k}$ примитивно рекурсивны.

?

Задача III.1.22

Доказать, что всякая примитивно рекурсивная функция общерекурсивна.

?

Задача III.1.23

(а)(б)(в)

?

(а)

Доказать, что суперпозиция общерекурсивных функций есть общерекурсивная функция.

(б)

Доказать, что, применяя оператор примитивной рекурсии к общерекурсивным функциям, мы получим общерекурсивную функцию.

(в)

Привести пример общерекурсивной функции, из которой с помощью $\mu$ -оператора получается функция, не являющаяся общерекурсивной.

Задача III.1.24

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

Доказать, что если функция $f(x_{1}, \ldots , x_{n})$ частично рекурсивна, то следующие функции частично рекурсивны:

?

(а)

$f_{1}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, x_{1}, \ldots , x_{n})$ (перестановка аргументов);

(б)

$f_{2}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, \ldots , x_{n}, x_{1})$ (циклическая перестановка аргументов);

(в)

$f_{3}(x_{1}, \ldots , x_{n}, x_{n+1}) = f(x_{1}, \ldots , x_{n})$ (введение фиктивного аргумента);

(г)

$f_{4}(x_{1}, \ldots , x_{n-1}) = f(x_{1}, x_{1}, \ldots , x_{n-1})$ (отождествление аргументов).

Задача III.1.25

(а)(б)(в)

Доказать, что:

?

(а)

существует в точности $\aleph_{0}$ частично рекурсивных функций;

(б)

существует частичная числовая функция, не являющаяся частично рекурсивной;

(в)

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

Задача III.1.26

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

?

(а)

нигде не определенная функция $\omega$ , т.е. функция $\omega$ с пустой областью определения;

(б)

$f(x, y) = \begin{cases} x - y, & \text{если } x \geq y, \\ \text{не определена в остальных случаях}; \end{cases}$

(в)

$f(x, y) = \begin{cases} \dfrac {x}{y}, & \text{если } y \text{ делит } x, \\ \text{не определена в остальных случаях}; \end{cases}$

(г)

$f(x, y) = \begin{cases} z, & \text{если } z^{y} = x, \\ \text{не определена в остальных случаях}; \end{cases}$

(д)

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

Задача III.1.27

Доказать, что если функции $g^{n+1}, h^{n+1}$ и $t^{n+1}$ частично рекурсивны, то следующие функции частично рекурсивны:

?

(а)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) = h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(б)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) \neq h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(в)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) \leq h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(г)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) < h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(д)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) = 0 \text{ и } h(x_{1}, \ldots , x_{n}, y) = 0\right]$ ;

(е)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) = 0 \text{ или } h(x_{1}, \ldots , x_{n}, y) \leq t(x_{1}, \ldots , x_{n}, y)\right]$ .

Задача III.1.28

(а)(б)

?

(а)

Доказать, что функция $f^{n+1}$ , возникающая из частичных функций $g^{n}$ и $h^{n+2}$ с помощью оператора примитивной рекурсии, может быть получена с помощью специальной рекурсии вида:

\begin{cases} F(x, 0) = x, \\ F(x, y+1) = G(F(x, y)) \end{cases}

и суперпозиций из функций $g^{n}, h^{n+2}, o, s, I_{m}^{n}$ и $c, l, r$ из задачи III.1.13.

(б)

Доказать, что функция $f(x)$ , получающаяся из $a$ и $h(x, y)$ с помощью оператора примитивной рекурсии, может быть получена с помощью итерации и суперпозиций из функций $a, h, o, s, I_{m}^{n}$ и $c, l, r$ из задачи III.1.13.

Задача III.1.29

Доказать, что функция $f^{n}$ , получающаяся из частичной функции $g^{n+1}$ с помощью $\mu$ -оператора, может быть получена из функций $g, I_{m}^{n}$ и $c, l, r$ из задачи III.1.13 с помощью суперпозиций и $\mu$ -оператора специального вида.

F(x) = \mu y \left[G(x, y) = 0\right].

?

Задача III.1.30

Доказать, что функция $f^{n+1}$ , получающаяся с помощью оператора примитивной рекурсии из всюду определенных функций $g^{n}$ и $h^{n+2}$ , может быть получена из этих функций и функций $+, \symdiff , s, o, I_{m}^{n}$ и $c, l, r, \beta$ из задач III.1.13, III.1.17 с помощью суперпозиций и $\mu$ -оператора специального вида из задачи III.1.29.

?

Задача III.1.31

(а)(б)(в)

?

(а)

Пусть $\sqrt{2} = a_{0}, a_{1}a_{2}, \ldots$ --- разложение числа $\sqrt{2}$ в бесконечную десятичную дробь. Доказать общерекурсивность функции $a_{n}$ .

(б)

Пусть $e = a_{0}, a_{1}a_{2}, \ldots$ --- разложение числа $e$ в бесконечную десятичную дробь. Доказать общерекурсивность функции $a_{n}$ .

(в)

Пусть $\pi = a_{0}, a_{1}a_{2}, \ldots$ --- разложение числа $\pi$ в бесконечную десятичную дробь. Доказать общерекурсивность функции $a_{n}$ .

Задача III.1.32

Пусть $\alpha = a_{0}, a_{1}a_{2}, \ldots$ --- разложение действительного числа $\alpha$ в бесконечную десятичную дробь. Число $\alpha$ назовем общерекурсивным (конструктивным), если $a_{n}$ --- общерекурсивная функция от $n$ . Доказать, что алгебраические числа общерекурсивны.

?

Задача III.1.33

Доказать, что:

?

(а)

$\mathbf{i}(ax+b) = b \cdot \dfrac {a^{x} - 1}{a - 1}$ при $a > 1$ ;

(б)

$\mathbf{i}\left(1 + \left[\dfrac {x}{2}\right]\right) = \operatorname {sg} x$ ;

(в)

$\mathbf{i}\left(x + 1 + \left[\dfrac {x+1}{2}\right] - \left[\dfrac {x}{2}\right]\right) = 2x \symdiff 1$ ;

(г)

$\mathbf{i}(\overline{\operatorname {sg}}\, x + 2x) = 2^{x-1} \symdiff \overline{\operatorname {sg}}\, x$ ;

(д)

$\mathbf{i}(x + 1 + \sqrt{4x+1}) = x^{2} + x$ ;

(е)

$\mathbf{i}\left(x + 1 + 2\left[\sqrt{x}\right]\right) = x^{2}$ .

Задача III.1.34

Доказать, что следующие функции могут быть получены из функций $s(x) = x+1$ и $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ с помощью операций подстановки, итерации и сложения двух функций:

?

(а)

$I_{m}^{n}(x_{1}, \ldots , x_{n})$ ;

(б)

$o(x)$ ;

(в)

$\operatorname {sg}(x)$ ;

(г)

$\overline{\operatorname {sg}}(x)$ ;

(д)

$ax + by + c$ ;

(е)

$x^{2}$ ;

(ж)

$\left[\dfrac {x}{2}\right]$ ;

(з)

$\left[\sqrt{x}\right]$ ;

(и)

$x \cdot y$ ;

(к)

$x \symdiff y$ ;

(л)

$c(x, y)$ ;

(м)

$l(x)$ ;

(н)

$r(x)$ .

Задача III.1.35

Доказать, что всякая примитивно рекурсивная функция может быть получена из функций $s(x) = x+1$ и $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ с помощью операций подстановки, итерации и сложения двух функций (теорема Р. Робинсона).

?

Задача III.1.36

(а)(б)

Доказать, что:

?

(а)

$I_{1}^{1}(f(x)) = f(I_{1}^{1}(x)) = f(f^{-1}(f(x))) = f(x)$ ;

(б)

$f^{-1}(f(f^{-1}(x))) = f^{-1}(x)$ .

Задача III.1.37

(а)(б)(в)

Доказать, что:

?

(а)

если $f^{-1}(x)$ определена в какой-нибудь точке $a$ , то

f(f^{-1}(a)) = a;

(б)

если $f^{-1}(x)$ всюду определена, то

f(f^{-1}(x)) = I_{1}^{1}(x);

(в)

существует $f(x)$ такая, что $f^{-1}(x)$ всюду определена, но

f^{-1}(f(x)) \neq I_{1}^{1}(x).

Задача III.1.38

Доказать, что:

?

(а)

$(x+1)^{-1} = x - 1$ ;

(б)

$(o(x))^{-1} = 0 - x$ ;

(в)

$(2x)^{-1} = \dfrac {x}{2}$ ;

(г)

$(x^{2})^{-1} = \sqrt{x}$ ;

(д)

$\left(\left[\dfrac {x}{n}\right]\right)^{-1} = nx$ ;

(е)

$\left(\left[\sqrt[n]{x}\right]\right)^{-1} = x^{n}$ ;

(ж)

$q^{-1}(x) = x + \left[\dfrac {x+1}{2}\right]^{2}$ , где $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ ;

(з)

$q^{-1}(2x) = x^{2} + 2x$ ;

(и)

$q^{-1}(2x+1) = x^{2} + 4x + 2$ ;

(к)

$q^{-1}(2x+2y) = (x+y)^{2} + 2x + 2y$ .

Задача III.1.39

Доказать, что следующие функции могут быть получены из функций $s(x) = x+1$ и $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ с помощью операций подстановки, обращения и сложения двух функций:

?

(а)

$I_{m}^{n}(x_{1}, \ldots , x_{n})$ ;

(б)

$o(x)$ ;

(в)

$\operatorname {sg}(x)$ ;

(г)

$\overline{\operatorname {sg}}(x)$ ;

(д)

$ax + by + c$ ;

(е)

$x^{2}$ ;

(ж)

$\left[\dfrac {x}{2}\right]$ ;

(з)

$\left[\sqrt{x}\right]$ ;

(и)

$x \cdot y$ ;

(к)

$x \symdiff y$ ;

(л)

$c(x, y)$ ;

(м)

$l(x)$ ;

(н)

$r(x)$ .

Задача III.1.40

Пусть $f(x) = \mu y \left[h(x, y) = 0\right]$ . Доказать, что $f(x)$ может быть получена из $h, s(x) = x+1$ и $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ с помощью операций подстановки, обращения и сложения двух функций.

?

Задача III.1.41

Доказать, что всякая частично рекурсивная функция может быть получена из $s(x) = x+1$ , $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ с помощью операций подстановки, обращения и сложения двух функций (теорема Ю. Робинсон).

?

Задача III.1.42

Рассмотрим следующие функции Аккермана:

B(0, y) = 2+y; \qquad B(x+1, 0) = \operatorname {sg} x; \qquad B(x+1, y+1) = B(x, B(x+1, y)); \qquad A(x) = B(x, x).

Назовем всюду определенную функцию $f(x_{1}, \ldots , x_{n})$ $B$ -мажорируемой, если существует натуральное число $m$ такое, что

f(x_{1}, \ldots , x_{n}) < B(m, \max (x_{1}, \ldots , x_{n}) + 3).

Доказать, что:

?

(а)

$B(x, y)$ и $A(x)$ общерекурсивны;

(б)

$B(n+2, x+1) \geq 2^{x+1}$ ;

(в)

$B(n+1, x+2) \geq B(n+1, x+1)$ ;

(г)

$B(n+2, x+3) \geq B(n+1, x+4)$ ;

(д)

простейшие функции $B$ -мажорируемы;

(е)

функция, полученная с помощью суперпозиции из $B$ -мажорируемых функций, $B$ -мажорируема;

(ж)

функция, полученная с помощью примитивной рекурсии из $B$ -мажорируемых функций, $B$ -мажорируема;

(з)

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

Задача III.1.43

Доказать, что не существует примитивно рекурсивной функции, универсальной для семейства всех $n$ -местных примитивно рекурсивных функций.

?

Задача III.1.44

Доказать, что не существует частично рекурсивной функции, универсальной для семейства всех $n$ -местных общерекурсивных функций.

?

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