Упражнения

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

Покажите, что ни одно бесконечное подмножество $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]$?