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

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

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

Доказать, что если предикат $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))$ также рекурсивны (примитивно рекурсивны).

Доказать, что если предикат $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\}$ --- рекурсивно перечислимое множество.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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