Задачи по теории множеств, математической логике и теории алгоритмов

Часть III

Теория алгоритмов

[160/87%]

Показать

LaTeX

Показать LaTeX

Содержание

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

III.2 · Машины Тьюринга

III.3 · Рекурсивные и рекурсивно перечислимые множества

III.4 · Нумерации Клини и Поста

Глава

III.1 · Частично рекурсивные функции[44/84%]

Задача 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$ -местных общерекурсивных функций.

Происхождение: Изложено по оригинальному источнику

Глава

III.2 · Машины Тьюринга[25/96%]

Задача III.2.1

Какую функцию $f(x)$ вычисляет машина $T$ со следующей программой команд:

q_{1}0 \to q_{2}0R, \qquad q_{1}1 \to q_{0}1, \qquad q_{2}0 \to q_{0}1, \qquad q_{2}1 \to q_{2}1R \, ?

Происхождение: Изложено по оригинальному источнику

Задача III.2.2

Пусть машина $T$ имеет следующую программу:

q_{1}0 \to q_{0}0.

Какие функции $f_{1}(x), f_{2}(x_{1}, x_{2}), \ldots , f_{n}(x_{1}, \ldots , x_{n}), \ldots$ вычисляет эта машина?

Происхождение: Изложено по оригинальному источнику

Задача III.2.3

Построить машину Тьюринга, которая правильно вычисляет функцию $f(x) = x+1$ .

Происхождение: Изложено по оригинальному источнику

Задача III.2.4

Построить машину Тьюринга, которая правильно вычисляет функцию $o(x) = 0$ .

Происхождение: Изложено по оригинальному источнику

Задача III.2.5

Построить следующие машины Тьюринга:

Перенос нуля: $q_{1}001^{x}0 \mid \Rightarrow_{А} q_{0}01^{x}00$ .
Правый сдвиг: $q_{1}001^{x}0 \mid \Rightarrow_{Б^{+}} 01^{x}q_{0}0$ .
Левый сдвиг: $01^{x}q_{1}0 \mid \Rightarrow_{Б^{-}} q_{0}01^{x}0$ .
Транспозиция: $01^{x}q_{1}01^{y}0 \mid \Rightarrow_{В} 01^{y}q_{0}01^{x}0$ .
Удвоение: $q_{1}01^{x}0 \Rightarrow_{Г} q_{0}01^{x}01^{x}0$ .
Циклический сдвиг: $q_{1}01^{x_{1}}01^{x_{2}}\ldots 01^{x_{n}}0 \mid \Rightarrow_{\text{Ц}_{n}} q_{0}01^{x_{2}}\ldots 01^{x_{n}}01^{x_{1}}0$ .
Копирование: $q_{1}01^{x_{1}}\ldots 01^{x_{n}}0 \Rightarrow_{\text{К}_{n}} q_{0}01^{x_{1}}\ldots 01^{x_{n}}01^{x_{1}}\ldots 01^{x_{n}}0$ .

Происхождение: Изложено по оригинальному источнику

Задача III.2.6

Построить машину Тьюринга, которая правильно вычисляет функцию $I_{m}^{n}(x_{1}, \ldots , x_{n})$ (где $1 \leq m \leq n$ ).

Происхождение: Изложено по оригинальному источнику

Задача III.2.7

(а)(б)

Происхождение: Изложено по оригинальному источнику

(а)

Пусть функции $f(x)$ и $g(x)$ правильно вычислимы по Тьюрингу. Показать, что функция $h(x) = f(g(x))$ правильно вычислима по Тьюрингу.

(б)

Пусть функции $f(x_{1}, \ldots , x_{n})$ и $g_{1}(x_{1}, \ldots , x_{m}), \ldots , g_{n}(x_{1}, \ldots , x_{m})$ правильно вычислимы по Тьюрингу. Показать, что функция $h(x_{1}, \ldots , x_{n}) = f(g_{1}(x_{1}, \ldots , x_{m}), \ldots , g_{n}(x_{1}, \ldots , x_{m}))$ правильно вычислима по Тьюрингу.

Задача III.2.8

(а)(б)(в)(г)(д)(е)(ж)(з)

Построить машину Тьюринга для правильного вычисления функций:

Происхождение: Изложено по оригинальному источнику

(а)

$x+y$ ;

(б)

$x \symdiff 1$ ;

(в)

$\operatorname {sg}(x)$ ;

(г)

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

(д)

$x \symdiff y$ ;

(е)

$x - y$ ;

(ж)

$\dfrac {x}{2}$ ;

(з)

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

Задача III.2.9

(а)(б)

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

Происхождение: Изложено по оригинальному источнику

(а)

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

(б)

если функция $f^{n}$ получается из правильно вычислимой по Тьюрингу функции $g^{n+1}$ с помощью $\mu$ -оператора, то $f^{n}$ правильно вычислима по Тьюрингу.

Задача III.2.10

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

Происхождение: Изложено по оригинальному источнику

Задача III.2.11

(а)(б)(в)

Доказать, что существуют примитивно рекурсивные функции $\alpha , \beta , \gamma$ такие, что:

Происхождение: Изложено по оригинальному источнику

(а)

$\alpha (x, y) = \lambda (T_{1} \cdot T_{2})$ , если $\lambda (T_{1}) = x$ и $\lambda (T_{2}) = y$ ;

(б)

$\beta (x) = \lambda (T)$ для некоторой машины $T$ , перерабатывающей слово $q_{1}0$ в слово $q_{1}01^{x}0$ ;

(в)

$\gamma (x, y, z) = \lambda \left(T_{1}\begin{cases} q_{i} = T_{2} \\ q_{j} = T_{3} \end{cases}\right)$ , если $\lambda (T_{1}) = x$ , $\lambda (T_{2}) = y$ , $\lambda (T_{3}) = z$ .

Задача III.2.12

Построить примитивно рекурсивные функции $\gamma^{n}(x_{1}, \ldots , x_{n})$ такие, что

\nu (q_{1}01^{x_{1}}\ldots 01^{x_{n}}0) = \gamma ^{n}(x_{1}, \ldots , x_{n}).

Происхождение: Изложено по оригинальному источнику

Задача III.2.13

Построить примитивно рекурсивную функцию $\rho (s, k, l, u, \nu )$ удовлетворяющую условию: если $u = k_{l}(A)$ , $\nu = k_{r}(B)$ , $0 \leq s \leq 2$ , то $\rho (s, k, l, u, \nu ) = \nu ((Aq_{i}a_{j}B)_{T}')$ , где $T(i,j)$ есть $q_{i}a_{j} \to q_{k}a_{l}$ при $s=0$ , $q_{i}a_{j} \to q_{k}a_{l}L$ при $s=1$ , $q_{i}a_{j} \to q_{k}a_{l}R$ при $s=2$ .

Происхождение: Изложено по оригинальному источнику

Задача III.2.14

Построить примитивно рекурсивную функцию $\sigma (t, i, j, u, \nu )$ , удовлетворяющую условию: если $u = k_{l}(A)$ , $\nu = k_{r}(B)$ , $t = \lambda (T)$ , $q_{i}$ входит в алфавит внутренних состояний, а $a_{j}$ --- во внешний алфавит машины $T$ , то $\sigma (t, i, j, u, \nu ) = \nu ((Aq_{i}a_{j}B)_{T}')$ .

Происхождение: Изложено по оригинальному источнику

Задача III.2.15

Построить примитивно рекурсивную функцию $\tau (t, x)$ , удовлетворяющую условию: если $t = \lambda (T)$ , $x = \nu (M)$ , где $M = Aq_{i}a_{j}B$ --- машинное слово в алфавите машины $T$ , то $\tau (t,x) = \nu (M_{T}')$ .

Происхождение: Изложено по оригинальному источнику

Задача III.2.16

Построить примитивно рекурсивную функцию $w(t, x, y)$ , удовлетворяющую условию: если $t = \lambda (T)$ , $x = \nu (M)$ , где $M$ --- машинное слово в алфавите машины $T$ , то $w(t, x, y) = \nu (M_{T}^{(y)})$ .

Происхождение: Изложено по оригинальному источнику

Задача III.2.17

Построить примитивно рекурсивную функцию $\varepsilon (x)$ , удовлетворяющую условию: если $x = \nu (M)$ , то $\varepsilon (x)$ есть число вхождений символа $a_{1}$ в слово $M$ .

Происхождение: Изложено по оригинальному источнику

Задача III.2.18

(а)(б)

Доказать, что если машина $T$ вычисляет $f(x_{1}, \ldots , x_{n})$ и $t_{0} = \lambda (T)$ , то:

Происхождение: Изложено по оригинальному источнику

(а)

$\langle x_{1}, \ldots , x_{n} \rangle \in \delta_{f} \Leftrightarrow \operatorname {ex}(1, w(t_{0}, \gamma^{n}(x_{1}, \ldots , x_{n}), y)) = 0$ для некоторого $y$ ;

(б)

$f(x_{1}, \ldots , x_{n}) = \varepsilon (w(t_{0}, \gamma^{n}(x_{1}, \ldots , x_{n}), h^{n+1}(t_{0}, x_{1}, \ldots , x_{n})))$ , где $h^{n+1}(t_{0}, x_{1}, \ldots , x_{n}) = \mu y \left[\operatorname {ex}(1, w(t_{0}, \gamma^{n}(x_{1}, \ldots , x_{n}), y)) = 0\right]$ , а функции $\gamma , w$ и $\varepsilon$ взяты из задач III.2.12, III.2.16 и III.2.17.

Задача III.2.19

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

Происхождение: Изложено по оригинальному источнику

Задача III.2.20

Доказать, что функция вычислима по Тьюрингу тогда и только тогда, когда существует машина Тьюринга с внешним алфавитом $\left\{ 0,1\right\}$ , вычисляющая эту функцию.

Происхождение: Изложено по оригинальному источнику

Задача III.2.21

Доказать, что существует двуместная частично рекурсивная функция $U(t, x)$ , универсальная для семейства всех одноместных частично рекурсивных функций.

Происхождение: Изложено по оригинальному источнику

Задача III.2.22

Доказать, что существует $(n+1)$ -местная частично рекурсивная функция $U^{n+1}(t, x_{1}, \ldots , x_{n})$ , универсальная для семейства всех $n$ -местных частично рекурсивных функций.

Происхождение: Изложено по оригинальному источнику

Задача III.2.23

(а)(б)(в)

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

Происхождение: Изложено по оригинальному источнику

(а)

$h(x, y) = \begin{cases} 1, & \text{если } x \text{ есть номер машины } T \text{ и машина } T \text{ останавливается, начиная работу с машинного слова } q_{1}01^{y}0, \\ 0 & \text{в противном случае;} \end{cases}$

(б)

$g(x) = h(x,x)$ ;

(в)

$h_{0}(x) = \begin{cases} 1, & \text{если } x \text{ есть номер машины } T \text{ и машина } T \text{ останавливается, начиная работу с машинного слова } q_{1}0, \\ 0 & \text{в противном случае.} \end{cases}$

Задача III.2.24

Доказать, что существует примитивно рекурсивная функция $S(z, x, y, w)$ такая, что

S(z, x, y, w) = \begin{cases} 1, & \text{если } z = \lambda (T) \text{ и машина } T \text{ перерабатывает слово } q_{1}01^{x}0 \text{ в слово } q_{0}01^{y}0\ldots 0 \text{ не более чем за } w \text{ шагов,} \\ 0 & \text{в противном случае.} \end{cases}

Происхождение: Изложено по оригинальному источнику

Задача III.2.25

(а)(б)

Доказать, что существуют примитивно рекурсивные функции $p, T_{1}, T_{2}, \ldots$ такие, что:

Происхождение: Изложено по оригинальному источнику

(а)

$U(m, x) = p(\mu y \left[T_{1}(m, x, y) = 0\right])$ ;

(б)

$U^{n+1}(m, x_{1}, \ldots , x_{n}) = p(\mu y \left[T_{n}(m, x_{1}, \ldots , x_{n}, y) = 0\right])$ .

Глава

III.3 · Рекурсивные и рекурсивно перечислимые множества[48/81%]

Задача III.3.1

(а)(б)(в)(г)(д)(е)(ж)(з)

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

Происхождение: Изложено по оригинальному источнику

(а)

$x = y$ ;

(б)

$x + y = z$ ;

(в)

$x \cdot y = z$ ;

(г)

$x$ делит $y$ ;

(д)

$x$ четно;

(е)

$x$ и $y$ взаимно просты;

(ж)

$\exists n(x = 1^{2} + 2^{2} + \ldots + n^{2})$ ;

(з)

$\exists n(x = 1 + 2 + \ldots + n)$ .

Задача III.3.2

(а)(б)(в)(г)(д)(е)

Доказать, что если $P(x_{1}, \ldots , x_{n})$ и $Q(x_{1}, \ldots , x_{n})$ --- рекурсивные (примитивно рекурсивные) предикаты, то следующие предикаты также рекурсивны (примитивно рекурсивны):

Происхождение: Изложено по оригинальному источнику

(а)

$(P(x_{1}, \ldots , x_{n})\ \& \ Q(x_{1}, \ldots , x_{n}))$ ;

(б)

$(P(x_{1}, \ldots , x_{n}) \lor Q(x_{1}, \ldots , x_{n}))$ ;

(в)

$\neg P(x_{1}, \ldots , x_{n})$ ;

(г)

$(P(x_{1}, \ldots , x_{n}) \supset Q(x_{1}, \ldots , x_{n}))$ ;

(д)

$P(x_{1}, x_{1}, x_{3}, \ldots , x_{n})$ ;

(е)

$P(f(x_{1}, \ldots , x_{m}), x_{m+1}, \ldots , x_{m+n-1})$ , если $f(x_{1}, \ldots , x_{m})$ --- орф (прф).

Задача III.3.3

Доказать, что если предикат $R(x_{1}, \ldots , x_{n}, y)$ рекурсивен (примитивно рекурсивен), то предикаты $\exists y (y \leq z\ \& \ R(x_{1}, \ldots , x_{n}, y))$ и $\forall y (y \leq z \supset R(x_{1}, \ldots , x_{n}, y))$ также рекурсивны (примитивно рекурсивны).

Происхождение: Изложено по оригинальному источнику

Задача III.3.4

Доказать, что если предикат $R(x_{1}, \ldots , x_{n}, y, z)$ примитивно рекурсивен, то $M = \left\{ \langle x_{1}, \ldots , x_{n} \rangle \mid \exists y \exists z\, R(x_{1}, \ldots , x_{n}, y, z)\right\}$ --- рекурсивно перечислимое множество.

Происхождение: Изложено по оригинальному источнику

Задача III.3.5

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.6

Доказать, что любое конечное множество натуральных чисел примитивно рекурсивно.

Происхождение: Изложено по оригинальному источнику

Задача III.3.7

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.8

Доказать, что если $f$ --- общерекурсивная (примитивно рекурсивная) функция и $a$ --- фиксированное число, то множество решений уравнения $f(x_{1}, \ldots , x_{n}) = a$ рекурсивно (примитивно рекурсивно).

Происхождение: Изложено по оригинальному источнику

Задача III.3.9

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.10

Доказать, что если множества $A$ и $B$ рекурсивны (примитивно рекурсивны), то множества $A \cap B$ , $A \cup B$ , $\mathbb {N} \setminus A$ также рекурсивны (примитивно рекурсивны).

Происхождение: Изложено по оригинальному источнику

Задача III.3.11

Доказать, что если множества $A$ и $B$ рекурсивно перечислимы, то множества $A \cap B$ и $A \cup B$ рекурсивно перечислимы.

Происхождение: Изложено по оригинальному источнику

Задача III.3.12

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.13

(а)(б)

Пусть множества $A$ и $B$ отличаются конечным числом элементов. Доказать, что:

Происхождение: Изложено по оригинальному источнику

(а)

если $A$ рекурсивно, то $B$ рекурсивно;

(б)

если $A$ рекурсивно перечислимо, то $B$ рекурсивно перечислимо.

Задача III.3.14

Доказать, что если множество $A$ и его дополнение $\mathbb {N} \setminus A$ рекурсивно перечислимы, то $A$ рекурсивно (теорема Поста).

Происхождение: Изложено по оригинальному источнику

Задача III.3.15

(а)(б)(в)

Пусть $M \subseteq \mathbb {N}^{n}$ . Положим

c^{n}(M) = \left\{ c^{n}(x_{1}, \ldots , x_{n}) \mid \langle x_{1}, \ldots , x_{n} \rangle \in M\right\} ,

где $c^{n}$ определена в задаче III.1.14. Доказать, что:

Происхождение: Изложено по оригинальному источнику

(а)

$M$ примитивно рекурсивно тогда и только тогда, когда $c^{n}(M)$ примитивно рекурсивно;

(б)

$M$ рекурсивно тогда и только тогда, когда $c^{n}(M)$ рекурсивно;

(в)

$M$ рекурсивно перечислимо тогда и только тогда, когда $c^{n}(M)$ рекурсивно перечислимо.

Задача III.3.16

Пусть $M \subseteq \mathbb {N}$ --- непустое множество. Доказать, что $M$ рекурсивно перечислимо тогда и только тогда, когда существует примитивно рекурсивная функция $\alpha (x)$ такая, что $M = \left\{ \alpha (x) \mid x \in \mathbb {N}\right\}$ .

Происхождение: Изложено по оригинальному источнику

Задача III.3.17

Пусть $M$ --- непустое множество $n$ -ок. Доказать, что множество $M$ рекурсивно перечислимо тогда и только тогда, когда существуют одноместные примитивно рекурсивные функции $\alpha_{1}, \ldots , \alpha_{n}$ такие, что

M = \left\{ \langle \alpha _{1}(x), \ldots , \alpha _{n}(x) \rangle \mid x \in \mathbb {N}\right\} .

Происхождение: Изложено по оригинальному источнику

Задача III.3.18

Пусть общерекурсивная функция $f(x)$ удовлетворяет условию: $f(x) \geq x$ для всех $x \in \mathbb {N}$ . Доказать, что область значений $\rho_{f}$ функции $f$ рекурсивна.

Происхождение: Изложено по оригинальному источнику

Задача III.3.19

Доказать, что бесконечное множество $A$ рекурсивно тогда и только тогда, когда $A$ есть множество значений строго возрастающей общерекурсивной функции.

Происхождение: Изложено по оригинальному источнику

Задача III.3.20

Доказать, что непустое множество $A$ рекурсивно тогда и только тогда, когда $A$ есть множество значений монотонно (не обязательно строго) возрастающей общерекурсивной функции.

Происхождение: Изложено по оригинальному источнику

Задача III.3.21

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.22

Доказать, что каждое бесконечное рекурсивно перечислимое множество представимо в виде $A = \rho_{f}$ для некоторой общерекурсивной 1--1-функции $f$ .

Происхождение: Изложено по оригинальному источнику

Задача III.3.23

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.24

Доказать, что если график $\Gamma_{f}$ функции $f$ рекурсивно перечислим, то функция $f$ частично рекурсивна.

Происхождение: Изложено по оригинальному источнику

Задача III.3.25

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.26

Пусть $A$ --- рекурсивное множество, $f$ --- общерекурсивная функция с $\rho_{f} = \mathbb {N}$ , $f(A) \cap f(\mathbb {N} \setminus A) = \emptyset$ . Доказать, что $f(A)$ рекурсивно.

Происхождение: Изложено по оригинальному источнику

Задача III.3.27

Пусть $A, B$ --- рекурсивно перечислимые множества, а $C$ --- рекурсивное множество такие, что $A \cap B = \emptyset$ , $A \subseteq C \subseteq A \cup B$ . Доказать, что $A$ рекурсивно.

Происхождение: Изложено по оригинальному источнику

Задача III.3.28

Пусть $f, g$ --- общерекурсивные функции, причем $g$ --- 1--1-функция. Пусть также имеем $f(x) \geq g(x)$ для всех $x$ . Доказать, что если $\rho_{g}$ рекурсивно, то $\rho_{f}$ рекурсивно.

Происхождение: Изложено по оригинальному источнику

Задача III.3.29

Пусть $A, B$ --- рекурсивно перечислимые множества. Доказать, что существуют рекурсивно перечислимые множества $A_{1} \subseteq A$ , $B_{1} \subseteq B$ такие, что $A_{1} \cap B_{1} = \emptyset$ , $A_{1} \cup B_{1} = A \cup B$ .

Происхождение: Изложено по оригинальному источнику

Задача III.3.30

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

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

Происхождение: Изложено по оригинальному источнику

(а)

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

(б)

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

(в)

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

(г)

график любой частично рекурсивной функции рекурсивно перечислим.

Задача III.3.31

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.32

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.33

Доказать, что множество значений частично рекурсивной функции рекурсивно перечислимо.

Происхождение: Изложено по оригинальному источнику

Задача III.3.34

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.35

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.36

(а)(б)

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

Происхождение: Изложено по оригинальному источнику

(а)

образ рекурсивно перечислимого множества относительно частично рекурсивной функции рекурсивно перечислим;

(б)

полный прообраз рекурсивно перечислимого множества относительно частично рекурсивной функции рекурсивно перечислим.

Задача III.3.37

Доказать, что множество $A$ решений уравнения

f(x_{1}, \ldots , x_{n}) = a

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.38

Доказать, что если $f^{n+1}$ --- частично рекурсивная функция, то множество $M = \left\{ \langle x_{1}, \ldots , x_{n} \rangle \mid \exists y\, f(x_{1}, \ldots , x_{n}, y) = 0\right\}$ рекурсивно перечислимо.

Происхождение: Изложено по оригинальному источнику

Задача III.3.39

Пусть $M_{1}, \ldots , M_{k}$ --- попарно непересекающиеся рекурсивно перечислимые множества $n$ -ок, $f_{1}, \ldots , f_{n}$ --- частично рекурсивные функции. Доказать, что $g(x_{1}, \ldots , x_{n})$ , определенная следующим образом:

g(x_{1}, \ldots , x_{n}) = \begin{cases} f_{1}(x_{1}, \ldots , x_{n}), & \text{если } \langle x_{1}, \ldots , x_{n} \rangle \in M_{1}, \\ \makebox[0pt][l]{\dotfill } \\ f_{k}(x_{1}, \ldots , x_{n}), & \text{если } \langle x_{1}, \ldots , x_{n} \rangle \in M_{k}, \\ \text{не определена в остальных случаях,} \end{cases}

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.40

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

f(x_{1}, \ldots , x_{n}) = l(\mu t \left[g(x_{1}, \ldots , x_{n}, t) = 0\right]),

где $g(x_{1}, \ldots , x_{n}, t)$ --- подходящая примитивно рекурсивная функция, а $l$ --- функция из задачи III.1.13 (ср. с задачей III.2.25).

Происхождение: Изложено по оригинальному источнику

Задача III.3.41

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

f(x_{1}, \ldots , x_{n}) = \mu t \left[g(x_{1}, \ldots , x_{n}, t) = 0\right]

для подходящей примитивно рекурсивной функции $g(x_{1}, \ldots , x_{n}, t)$ тогда и только тогда, когда график функции $f(x_{1}, \ldots , x_{n})$ примитивно рекурсивен.

Происхождение: Изложено по оригинальному источнику

Задача III.3.42

Пусть $F(x,y)$ определена с помощью рекурсии по двум переменным:

\begin{cases} F(0,y) = \varphi (y), \\ F(x+1,0) = \psi (x, F(x, \alpha (x)), F(x, F(x, \gamma (x)))), \\ F(x+1,y+1) = \tau (x,y,F(x,F(x+1,y))). \end{cases}

Доказать, что если функции $\varphi , \psi , \alpha , \gamma , \tau$ общерекурсивны, то функция $F$ общерекурсивна.

Происхождение: Изложено по оригинальному источнику

Задача III.3.43

Доказать, что множество

H = \left\{ x \mid \exists y\, T_{1}(x,x,y) = 0\right\} ,

где $T_{1}$ --- функция из задачи III.2.25, является рекурсивно перечислимым, но не рекурсивным.

Происхождение: Изложено по оригинальному источнику

Задача III.3.44

Доказать, что если область определения частично рекурсивной функции $f^{n}$ есть рекурсивное множество, то $f^{n}$ имеет рекурсивное доопределение.

Происхождение: Изложено по оригинальному источнику

Задача III.3.45

Доказать, что если $V(n,x)$ есть частично рекурсивная функция, универсальная для класса всех одноместных частично рекурсивных функций, то множество $M = \left\{ x \mid V(x,x) = 0\right\}$ рекурсивно перечислимо, но не рекурсивно.

Происхождение: Изложено по оригинальному источнику

Задача III.3.46

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

Происхождение: Изложено по оригинальному источнику

Задача III.3.47

Найти частично рекурсивную функцию $f(x)$ , не представимую в виде

f(x) = \mu y \left[g(x,y) = 0\right]

ни для какой общерекурсивной функции $g$ .

Происхождение: Изложено по оригинальному источнику

Задача III.3.48

Доказать, что если $V(n,x)$ есть частично рекурсивная функция, универсальная для класса всех одноместных частично рекурсивных функций, то множество

G = \left\{ n \mid V(n,x) \text{ --- общерекурсивная функция}\right\}

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

Происхождение: Изложено по оригинальному источнику

Глава

III.4 · Нумерации Клини и Поста[43/91%]

Задача III.4.1

(а)(б)(в)(г)(д)(е)

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

Происхождение: Изложено по оригинальному источнику

(а)

$[x,y]$ осуществляет взаимно однозначное соответствие между $\mathbb {N}^{2}$ и $\mathbb {N}$ ;

(б)

$[x_{1}, \ldots , x_{n}]$ осуществляет взаимно однозначное соответствие между $\mathbb {N}^{n}$ и $\mathbb {N}$ ;

(в)

$[[x]_{1}^{2}, [x]_{2}^{2}] = x$ , $[[x,y]]_{1}^{2} = x$ , $[[x,y]]_{2}^{2} = y$ ;

(г)

$[[x]_{1}^{n}, \ldots , [x]_{n}^{n}] = x$ , $[[x_{1}, \ldots , x_{n}]]_{i}^{n} = x_{i}$ ;

(д)

$[x_{1}, \ldots , x_{m}, x_{m+1}, \ldots , x_{n}] = [[x_{1}, \ldots , x_{m}], x_{m+1}, \ldots , x_{n}]$ ;

(е)

$c(x_{0}, c(x_{1}, x_{2})) = [c(x_{0}, x_{1}), x_{2}]$ .

Задача III.4.2

(а)(б)

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

Происхождение: Изложено по оригинальному источнику

(а)

$K^{n+m+1}(x_{0}, x_{1}, \ldots , x_{n}, x_{n+1}, \ldots , x_{n+m}) = K^{m+1}([x_{0}, x_{1}, \ldots , x_{n}], x_{n+1}, \ldots , x_{n+m})$ ;

(б)

$K^{n}(c(x_{0}, x_{1}), x_{2}, \ldots , x_{n}) = U^{n+1}(x_{0}, x_{1}, x_{2}, \ldots , x_{n})$ .

Задача III.4.3

(а)(б)

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

Происхождение: Изложено по оригинальному источнику

(а)

$K^{n+1}(x_{0}, x_{1}, \ldots , x_{n})$ является универсальной для всех $n$ -местных частично рекурсивных функций;

(б)

для любой частично рекурсивной функции $f^{n+m}$ существует примитивно рекурсивная функция $g^{n}$ такая, что

f(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m}) = K^{m+1}(g(x_{1}, \ldots , x_{n}), y_{1}, \ldots , y_{m}).

Задача III.4.4

Доказать, что всякая частично рекурсивная функция $f$ имеет бесконечно много клиниевских номеров.

Происхождение: Изложено по оригинальному источнику

Задача III.4.5

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

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

Происхождение: Изложено по оригинальному источнику

(а)

с помощью суперпозиции;

(б)

с помощью обращения;

(в)

с помощью итерации;

(г)

с помощью взятия суммы двух функций.

Задача III.4.6

(а)(б)

Доказать, что существует рекурсивно перечислимое множество $P$ , удовлетворяющее условиям:

Происхождение: Изложено по оригинальному источнику

(а)

если $x \in P$ , то $\kappa_{x}$ есть примитивно рекурсивная функция;

(б)

для любой примитивно рекурсивной функции $f$ существует $x \in P$ такое, что $f = \kappa_{x}$ .

Задача III.4.7

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

Происхождение: Изложено по оригинальному источнику

Задача III.4.8

(а)(б)(в)

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

Происхождение: Изложено по оригинальному источнику

(а)

с помощью суперпозиции;

(б)

с помощью примитивной рекурсии;

(в)

с помощью $\mu$ -оператора.

Задача III.4.9

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

\kappa _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \kappa _{f(x_{1}, \ldots , x_{n})}, & \text{если } f(x_{1}, \ldots , x_{n}) \text{ определено,} \\ \omega & \text{в противном случае.} \end{cases}

Происхождение: Изложено по оригинальному источнику

Задача III.4.10

(а)(б)

Происхождение: Изложено по оригинальному источнику

(а)

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

\kappa _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \kappa _{f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n}))}, & \text{если } f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n})) \text{ определено,} \\ \omega & \text{в противном случае.} \end{cases}

(б)

Доказать, что для каждой частично рекурсивной функции $f(x)$ существует такое натуральное число $a$ , что

\kappa _{a} = \begin{cases} \kappa _{f(a)}, & \text{если } f(a) \text{ определено,} \\ \omega & \text{в противном случае} \end{cases}

(теорема о неподвижной точке).

Задача III.4.11

Доказать, что для любой частично рекурсивной функции $f(x,y)$ существует число $n$ такое, что $f(n,y) = \kappa_{n}(y)$ для всех $y$ .

Происхождение: Изложено по оригинальному источнику

Задача III.4.12

(а)(б)

Доказать, что существует число $n$ такое, что:

Происхождение: Изложено по оригинальному источнику

(а)

$\kappa_{n}(0) = n$ ;

(б)

$\kappa_{n}(n) = n$ .

Задача III.4.13

Доказать, что существует примитивно рекурсивная функция $f$ такая, что для любого $x$ , если $\kappa_{x}$ есть общерекурсивная функция, то

\kappa _{\kappa _{x}(f(x))} = \kappa _{f(x)}.

Происхождение: Изложено по оригинальному источнику

Задача III.4.14

(а)(б)(в)

Построить частично рекурсивные функции $\kappa_{a}$ такие, что:

Происхождение: Изложено по оригинальному источнику

(а)

$\kappa_{a} = \chi_{\left\{ a\right\} }$ ;

(б)

$\kappa_{a} = \chi_{\left\{ a\right\} }^{*}$ ;

(в)

$\kappa_{a} = \chi_{\mathbb {N} - \left\{ a\right\} }^{*}$ .

Задача III.4.15

Пусть $\mathcal{F}$ --- семейство всех одноместных частичных функций. Отображение $F: \mathcal{F} \to \mathcal{F}$ назовем эффективным оператором, если функция $g(n,x) = (F(\kappa_{n}))(x)$ частично рекурсивна. Доказать, что для любого эффективного оператора $F$ существует частично рекурсивная функция $f$ такая, что $f = F(f)$ .

Происхождение: Изложено по оригинальному источнику

Задача III.4.16

(а)(б)

Доказать, что для любых частично рекурсивных функций $\alpha , \gamma , \delta$ существует частично рекурсивная функция $f$ , удовлетворяющая условиям:

Происхождение: Изложено по оригинальному источнику

(а)

если $\alpha (x) = 0$ , то $f(x) = 0$ ;

(б)

если $\alpha (x) > 0$ , то $f(x) = \gamma (f(\delta (x)))$ .

Задача III.4.17

Пусть $\mathcal{A}$ --- некоторое непустое семейство одноместных частично рекурсивных функций, отличное от семейства всех таких функций. Доказать, что множество

\kappa ^{-1}(\mathcal{A}) = \left\{ x \mid \kappa _{x} \in \mathcal{A}\right\}

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

Происхождение: Изложено по оригинальному источнику

Задача III.4.18

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

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

Происхождение: Изложено по оригинальному источнику

(а)

$A_{1} = \left\{ x \mid \kappa_{x} \text{ --- константа}\right\}$ ;

(б)

$A_{2} = \left\{ x \mid \kappa_{x}(a) = b\right\}$ , где $a, b$ --- фиксированные числа;

(в)

$A_{3} = \left\{ c(x,y) \mid y \in \delta_{\kappa_{x}}\right\}$ ;

(г)

$A_{4} = \left\{ c(x,y) \mid y \in \rho_{\kappa_{x}}\right\}$ ;

(д)

$A_{5} = \left\{ c(x,y) \mid \kappa_{x} = \kappa_{y}\right\}$ .

Задача III.4.19

(а)(б)(в)

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

Происхождение: Изложено по оригинальному источнику

(а)

функций, определенных в точке $0$ ;

(б)

функций $f$ таких, что $f(a) = b$ для данных чисел $a$ и $b$ ;

(в)

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

Задача III.4.20

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

Происхождение: Изложено по оригинальному источнику

Задача III.4.21

Пусть $\mathcal{A}$ --- некоторое непустое семейство рекурсивно перечислимых множеств, отличное от семейства всех рекурсивно перечислимых множеств. Доказать, что множество

\pi ^{-1}(\mathcal{A}) = \left\{ x \mid \pi _{x} \in \mathcal{A}\right\}

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

Происхождение: Изложено по оригинальному источнику

Задача III.4.22

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

Доказать, что не рекурсивны множества:

Происхождение: Изложено по оригинальному источнику

(а)

$\left\{ x \mid \pi_{x} \neq \emptyset \right\}$ ;

(б)

$\left\{ x \mid \pi_{x} = \mathbb {N}\right\}$ ;

(в)

$\left\{ x \mid a \in \pi_{x}\right\}$ , где $a$ --- фиксированное число;

(г)

$\left\{ x \mid \pi_{x} \text{ конечно}\right\}$ ;

(д)

$\left\{ c(x,y) \mid \pi_{x} = \pi_{y}\right\}$ .

Задача III.4.23

(а)(б)

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

Происхождение: Изложено по оригинальному источнику

(а)

содержащих данное число $a$ ;

(б)

непустых.

Задача III.4.24

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

\pi _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \pi _{f(x_{1}, \ldots , x_{n})}, & \text{если } f(x_{1}, \ldots , x_{n}) \text{ определено,} \\ \emptyset & \text{в противном случае.} \end{cases}

Происхождение: Изложено по оригинальному источнику

Задача III.4.25

Доказать, что для каждого рекурсивно перечислимого множества $P \subseteq \mathbb {N}^{n+1}$ ( $n > 0$ ) существует такая примитивно рекурсивная функция $\alpha (x_{1}, \ldots , x_{n})$ , что

\langle x_{0}, x_{1}, \ldots , x_{n} \rangle \in P \Leftrightarrow x_{0} \in \pi _{\alpha (x_{1}, \ldots , x_{n})}.

Происхождение: Изложено по оригинальному источнику

Задача III.4.26

(а)(б)(в)(г)(д)(е)

Доказать, что существуют примитивно рекурсивные функции $f, g, h, u, v, w$ такие, что:

Происхождение: Изложено по оригинальному источнику

(а)

$\pi_{x} \cap \pi_{y} = \pi_{f(x,y)}$ ;

(б)

$\pi_{x} \cup \pi_{y} = \pi_{g(x,y)}$ ;

(в)

$\left\{ x\right\} = \pi_{h(x)}$ ;

(г)

$\left\{ c(s,t) \mid s \in \pi_{x}, t \in \pi_{y}\right\} = \pi_{u(x,y)}$ ;

(д)

$\kappa_{y}(\pi_{x}) = \pi_{v(x,y)}$ ;

(е)

$\kappa_{y}^{-1}(\pi_{x}) = \pi_{w(x,y)}$ .

Задача III.4.27

(а)(б)

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

Происхождение: Изложено по оригинальному источнику

(а)

$\delta_{\kappa_{x}} = \rho_{\kappa_{f(x)}}$ ;

(б)

$\rho_{\kappa_{x}} = \delta_{\kappa_{g(x)}}$ .

Задача III.4.28

(а)(б)

Происхождение: Изложено по оригинальному источнику

(а)

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

\pi _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \pi _{f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n}))}, & \text{если } f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n})) \text{ определено,} \\ \emptyset & \text{в противном случае.} \end{cases}

(б)

Доказать, что для любой частично рекурсивной функции $f$ существует такое число $a$ , что

\pi _{a} = \begin{cases} \pi _{f(a)}, & \text{если } f(a) \text{ определено,} \\ \emptyset & \text{в противном случае} \end{cases}

(теорема о неподвижной точке).

Задача III.4.29

Доказать, что для любого рекурсивно перечислимого множества $M \subseteq \mathbb {N}^{n+2}$ существует примитивно рекурсивная функция $g^{n}$ такая, что

\langle x_{0}, x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n}) \rangle \in M \Leftrightarrow x_{0} \in \pi _{g(x_{1}, \ldots , x_{n})}.

Происхождение: Изложено по оригинальному источнику

Задача III.4.30

(а)(б)(в)

Доказать, что существует число $n$ такое, что:

Происхождение: Изложено по оригинальному источнику

(а)

$\pi_{n} = \left\{ n\right\}$ ;

(б)

$\pi_{n} = \left\{ n^{2}\right\}$ ;

(в)

$\pi_{n} = \mathbb {N} \setminus \left\{ n\right\}$ .

Задача III.4.31

Доказать, что отношение $\leq_{m}$ рефлексивно и транзитивно.

Происхождение: Изложено по оригинальному источнику

Задача III.4.32

Доказать, что всякое рекурсивное множество $m$ -сводимо к любому непустому множеству с непустым дополнением.

Происхождение: Изложено по оригинальному источнику

Задача III.4.33

Доказать, что если $A$ $m$ -сводимо к рекурсивному (рекурсивно перечислимому) множеству, то $A$ рекурсивно (рекурсивно перечислимо).

Происхождение: Изложено по оригинальному источнику

Задача III.4.34

Доказать, что множество

K_{1} = \left\{ c(x,y) \mid x \in \pi _{y}\right\}

является $m$ -универсальным.

Происхождение: Изложено по оригинальному источнику

Задача III.4.35

Доказать, что каждое $m$ -универсальное множество не рекурсивно.

Происхождение: Изложено по оригинальному источнику

Задача III.4.36

Доказать, что множество

K = \left\{ x \mid x \in \pi _{x}\right\}

является креативным.

Происхождение: Изложено по оригинальному источнику

Задача III.4.37

Доказать, что каждое креативное множество не рекурсивно.

Происхождение: Изложено по оригинальному источнику

Задача III.4.38

Доказать, что если $A$ --- креативное множество, $A \leq_{m} B$ и $B$ рекурсивно перечислимо, то $B$ креативно.

Происхождение: Изложено по оригинальному источнику

Задача III.4.39

Доказать, что каждое креативное множество является $m$ -универсальным.

Происхождение: Изложено по оригинальному источнику

Задача III.4.40

Доказать, что множество $m$ -универсально тогда и только тогда, когда оно креативно.

Происхождение: Изложено по оригинальному источнику

Задача III.4.41

Доказать, что множество

K_{2} = \left\{ x \mid \pi _{x} \neq \emptyset \right\}

является креативным.

Происхождение: Изложено по оригинальному источнику

Задача III.4.42

Доказать, что существует примитивно рекурсивная функция $\sigma (x)$ такая, что машина Тьюринга с номером $\sigma (x)$ вычисляет функцию $\kappa_{x}$ .

Происхождение: Изложено по оригинальному источнику

Задача III.4.43

Доказать, что множество $H$ из задачи III.3.43 из 3 является креативным.

Происхождение: Изложено по оригинальному источнику