Дополнительные темы теории вычислимости

Приведите пример в духе теоремы о рекурсии — программу на реальном языке программирования (или на разумном его приближении), которая выводит саму себя.

Покажите, что ни одно бесконечное подмножество $M I N_{\mathrm{TM}}$ не распознаётся машиной Тьюринга.

Покажите, что если $A \leq_{\mathrm{T}} B$ и $B \leq_{\mathrm{T}} C$, то $A \leq_{\mathrm{T}} C$.

Пусть $A_{\text{TM }}{ }^{\prime }=\left\{ \langle M, w\rangle \mid M \text{ — машина Тьюринга с оракулом и } M^{A T \mathrm{M}} \text{ допускает } w\right\}$. Покажите, что $A_{\text{TM }}{ }^{\prime }$ неразрешима относительно $A_{\text{TM }}$.

Является ли утверждение $\exists x \forall y[x+y=y]$ элементом $\operatorname {Th}(\mathcal{N},+)$? Почему да или почему нет? А что насчёт утверждения $\exists x \forall y[x+y=x]$?

Опишите две различные машины Тьюринга, $M$ и $N$, такие что $M$, будучи запущенной на любом входе, выводит $\langle N\rangle$, а $N$ выводит $\langle M\rangle$.

В формулировке теоремы о рекурсии с неподвижной точкой (теорема 6.8) пусть преобразование $t$ — это функция, меняющая местами состояния $q_{\text{accept }}$ и $q_{\text{reject }}$ в описаниях машин Тьюринга. Приведите пример неподвижной точки для $t$.

• Покажите, что $E Q_{\mathrm{TM}} \leq_{\mathrm{m}} \overline{E Q_{\mathrm{TM}}}$.

Используя теорему о рекурсии, приведите альтернативное доказательство теоремы Райса из задачи 5.28.

Приведите модель для формулы

• Пусть $\phi_{\mathrm{eq}}$ определена как в задаче 6.10. Приведите модель для формулы

Пусть $(\mathcal{N},<)$ — модель с множеством $\mathcal{N}$ и отношением «меньше». Покажите, что $\operatorname {Th}(\mathcal{N},<)$ разрешима.

Для каждого $m>1$ пусть $\mathcal{Z}_{m}=\left\{ 0,1,2, \ldots , m-1\right\}$, и пусть $\mathcal{F}_{m}=\left(\mathcal{Z}_{m},+, \times \right)$ — модель с множеством $\mathcal{Z}_{m}$ и отношениями, соответствующими операциям $+$ и $\times$ по модулю $m$. Покажите, что для каждого $m$ теория $\operatorname {Th}\left(\mathcal{F}_{m}\right)$ разрешима.

Покажите, что для любых двух языков $A$ и $B$ существует язык $J$, для которого $A \leq_{\mathrm{T}} J$ и $B \leq_{\mathrm{T}} J$.

Покажите, что для любого языка $A$ существует язык $B$, для которого $A \leq_{\mathrm{T}} B$ и $B \not\leq_{\mathrm{T}} A$.

• Докажите, что существуют два тьюринг-несравнимых языка $A$ и $B$ — то есть такие, что $A \not\leq_{\mathrm{T}} B$ и $B \not\leq_{\mathrm{T}} A$.

• Пусть $A$ и $B$ — два непересекающихся языка. Будем говорить, что язык $C$ разделяет $A$ и $B$, если $A \subseteq C$ и $B \subseteq \bar{C}$. Опишите два непересекающихся языка, распознаваемых машиной Тьюринга, которые нельзя разделить никаким разрешимым языком.

Покажите, что $\overline{E Q_{\mathrm{TM}}}$ распознаётся машиной Тьюринга с оракулом для $A_{\mathrm{TM}}$.

В следствии 4.18 мы показали, что множество всех языков несчётно. Используйте этот результат, чтобы доказать существование языков, не распознаваемых машиной Тьюринга с оракулом для $A_{\text{TM }}$.

Вспомните проблему соответствий Поста, определённую в разделе 5.2, и соответствующий ей язык $P C P$. Покажите, что $P C P$ разрешима относительно $A_{\text{тм }}$.

Покажите, как вычислить описательную сложность строк $\mathrm{K}(x)$ с помощью оракула для $A_{\text{тм }}$.

Используя результат задачи 6.21, приведите функцию $f$, вычислимую с помощью оракула для $A_{\text{ТМ }}$, такую что при каждом $n$ значение $f(n)$ — несжимаемая строка длины $n$.

Покажите, что функция $\mathrm{K}(x)$ не является вычислимой функцией.

Покажите, что множество несжимаемых строк неразрешимо.

Покажите, что множество несжимаемых строк не содержит бесконечного подмножества, распознаваемого машиной Тьюринга.

• Покажите, что для любого $c$ существуют строки $x$ и $y$, для которых $\mathrm{K}(x y)>\mathrm{K}(x)+\mathrm{K}(y)+c$.

Пусть $S=\left\{ \langle M\rangle \mid M\text{ — МТ и }L(M)=\left\{ \langle M\rangle \right\} \right\}$. Покажите, что ни $S$, ни $\bar{S}$ не распознаются машиной Тьюринга.

Пусть $R \subseteq \mathcal{N}^{k}$ — $k$-местное отношение. Будем говорить, что $R$ определимо в $\operatorname {Th}(\mathcal{N},+)$, если можно указать формулу $\phi$ с $k$ свободными переменными $x_{1}, \ldots , x_{k}$, такую что для всех $a_{1}, \ldots , a_{k} \in \mathcal{N}$, $\phi \left(a_{1}, \ldots , a_{k}\right)$ истинна в точности тогда, когда $a_{1}, \ldots , a_{k} \in R$. Покажите, что каждое из следующих отношений определимо в $\operatorname {Th}(\mathcal{N},+)$.