Сводимость

Пусть $A$ и $B$ — непустые собственные подмножества $\Sigma^{*}$.

Покажите, что множество $\mathrm{EMP}=\left\{ x \mid W_{x}=\emptyset \right\}$ не рекурсивно.

Покажите, с помощью $s$-$m$-$n$-теоремы, что $K \leq_{m} \overline{\text{ EMP }}$.

Проблема останова $K$ полна.

Пусть $A$ — нетривиальное индексное множество функций. Покажите, что если EMP $\subseteq A$, то $A$ не является р.п. Таким образом, следующие индексные множества не являются р.п.: $\overline{A_{1}}$, EMP, $\overline{\text{ Tot }}$, Fin, Rec, Reg и Rev.

Пусть $A$ — р.п. индексное множество. Покажите, что если $x \in A$ и $W_{x} \subseteq W_{y}$, то $y \in A$. Таким образом, следующие множества не являются р.п.: $\overline{\operatorname {REC}}, \overline{\operatorname {REG}}, \overline{\operatorname {REV}}$.

Пусть $A$ — р.п. индексное множество функций. Покажите, что если $x \in A$, то существует $y \in A$ такое, что $W_{y}$ — конечное подмножество $W_{x}$. Таким образом, следующие множества не являются р.п.: Tot, $\overline{\text{ FIN }}$.

Покажите, что TOT $\leq_{m} \overline{\text{ FIN }}$ и $\overline{\text{ FIN }} \leq_{m}$ TOT.

Пусть $A \cup B= \left\{ 0,1\right\}^{*}$ и $A \cap B \neq \emptyset$. Покажите, что если $A$ и $B$ являются р.п., то $A \leq_{m} A \cap B$.

Если $g: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ инъективна, определим $g^{-1}(x)=(\min y) [g(y)=x]$. Покажите, что существует рекурсивная функция $f$ такая, что для каждой инъективной функции $\phi_{m}$ выполнено $\phi_{f(m)}=\phi_{m}^{-1}$.

Покажите, что существует рекурсивная функция $c(x, y)$ такая, что $\phi_{c(x, y)}(z)= \phi_{x}\left(\phi_{y}(z)\right)$.

(Теорема Райса для р.п. индексных множеств) Для конечного множества $D=\left\{ x_{1}, \ldots , x_{n}\right\}$ будем говорить, что $\left[x_{1}, \ldots , x_{n}\right]$ (в любом порядке) — код $D$. Покажите, что индексное множество $A$ является р.п. тогда и только тогда, когда

1. из $x \in A$ и $W_{x} \subseteq W_{y}$ следует $y \in A$;

2. из $x \in A$ следует, что существует $y \in A$ такое, что $W_{y}$ — конечное подмножество $W_{x}$; и

3. существует р.п. множество $B$, содержащее коды всех и только конечных множеств $W_{x}$ таких, что $x \in A$ (т.е. для каждого $x \in A$, для которого $W_{x}$ конечно, $B$ содержит хотя бы один его код, и для каждого $\left[x_{1}, \ldots , x_{n}\right] \in B$ и каждого $x$ такого, что $\left.W_{x}=\left\{ x_{1}, \ldots , x_{n}\right\} , x \in A\right)$.

Для каждой частично рекурсивной функции $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ обозначим через $D_{f}$ её область определения $\left\{ x \mid f(x) \downarrow \right\}$. Пусть $f, g, h: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ — три частично рекурсивные функции.

Определим

Является ли $f$ частично рекурсивной функцией? Докажите свой ответ.

Пусть $\mathcal{C}_{1}$ — класс всех рекурсивных множеств, $\mathcal{C}_{2}$ — класс всех р.п. множеств, не являющихся рекурсивными, $\mathcal{C}_{3}$ — класс всех ко-р.п. множеств, не являющихся р.п., а $\mathcal{C}_{4}$ — класс всех множеств, которые не являются ни р.п., ни ко-р.п. Для каждого из следующих множеств определите, какому классу $\mathcal{C}_{i}, i \in \left\{ 1,2,3,4\right\}$, оно принадлежит.

Множество $A$ называется однозначным, если для каждого $y$ существует не более одного $z$ такого, что $\langle y, z\rangle \in A$. Пусть $B_{12}=\left\{ x \mid W_{x}\text{ однозначно }\right\}$. Покажите, что EMP $\leq_{m} B_{12}$ и $B_{12} \leq_{m}$ EMP,

Докажите следующие сведения:

Пусть $B_{13}=\left\{ x \mid W_{x}=K\right\}$.

Пусть $B_{14}=\left\{ x \mid \left(\exists y \in W_{x}\right)[W_{y}\text{ бесконечно}]\right\}$.

Множество $B \subseteq \left\{ 0,1\right\}^{*}$ называется продуктивным, если существует частично рекурсивная функция $f$ такая, что для каждого $x$, если $W_{x} \subseteq B$, то $f(x) \downarrow$ и $f(x) \in B-W_{x}$.

Покажите, что существуют два р.п. множества $A$ и $B$ такие, что $A \leq_{m} B$ и $B \leq_{m} A$.