Advanced Topics in Computability Theory

Give an example in the spirit of the recursion theorem of a program in a real programming language (or a reasonable approximation thereof) that prints itself out.

Show that any infinite subset of $\operatorname {MIN}_{\mathrm{TM}}$ is not Turing-recognizable.

ᴬ Show that if $A \leq_{\mathrm{T}} B$ and $B \leq_{\mathrm{T}} C$, then $A \leq_{\mathrm{T}} C$.

Let $A_{\text{TM }}{ }^{\prime }=\left\{ \langle M, w\rangle \mid M \text{ is an oracle TM and } M^{A T \mathrm{M}} \text{ accepts } w\right\}$. Show that $A_{\text{TM }}{ }^{\prime }$ is undecidable relative to $A_{\text{TM }}$.

ᴬ Is the statement $\exists x \forall y[x+y=y]$ a member of $\operatorname {Th}(\mathcal{N},+)$? Why or why not? What about the statement $\exists x \forall y[x+y=x]$?

Describe two different Turing machines, $M$ and $N$, where $M$ outputs $\langle N\rangle$ and $N$ outputs $\langle M\rangle$, when started on any input.

In the fixed-point version of the recursion theorem (Theorem 6.8), let the transformation $t$ be a function that interchanges the states $q_{\text{accept }}$ and $q_{\text{reject }}$ in Turing machine descriptions. Give an example of a fixed point for $t$.

• Show that $\operatorname {EQ}_{\mathrm{TM}} \leq_{\mathrm{m}} \overline{\operatorname {EQ}_{\mathrm{TM}}}$.

ᴬ Use the recursion theorem to give an alternative proof of Rice's theorem in Problem 5.28.

ᴬ Give a model of the sentence

• Let $\phi_{\mathrm{eq}}$ be defined as in Problem 6.10. Give a model of the sentence

Problem 6.10:

ᴬ Let $(\mathcal{N},<)$ be the model with universe $\mathcal{N}$ and the "less than" relation. Show that $\operatorname {Th}(\mathcal{N},<)$ is decidable.

For each $m>1$ let $\mathcal{Z}_{m}=\left\{ 0,1,2, \ldots , m-1\right\}$, and let $\mathcal{F}_{m}=\left(\mathcal{Z}_{m},+, \times \right)$ be the model whose universe is $\mathcal{Z}_{m}$ and that has relations corresponding to the + and × relations computed modulo $m$. Show that for each $m$, the theory $\operatorname {Th}\left(\mathcal{F}_{m}\right)$ is decidable.

Show that for any two languages $A$ and $B$, a language $J$ exists, where $A \leq_{\mathrm{T}} J$ and $B \leq_{\mathrm{T}} J$.

Show that for any language $A$, a language $B$ exists, where $A \leq_{\mathrm{T}} B$ and $B \nleq_{\mathrm{T}} A$.

• Prove that there exist two languages $A$ and $B$ that are Turing-incomparable-that is, where $A \nleq_{\mathrm{T}} B$ and $B \nleq_{\mathrm{T}} A$.

• Let $A$ and $B$ be two disjoint languages. Say that language $C$ separates $A$ and $B$ if $A \subseteq C$ and $B \subseteq \bar{C}$. Describe two disjoint Turing-recognizable languages that aren't separable by any decidable language.

Show that $\overline{\operatorname {EQ}_{\mathrm{TM}}}$ is recognizable by a Turing machine with an oracle for $A_{\mathrm{TM}}$.

In Corollary 4.18, we showed that the set of all languages is uncountable. Use this result to prove that languages exist that are not recognizable by an oracle Turing machine with an oracle for $A_{\text{TM }}$.

Recall the Post Correspondence Problem that we defined in Section 5.2 and its associated language $\operatorname {PCP}$. Show that $\operatorname {PCP}$ is decidable relative to $A_{\text{TM }}$.

Show how to compute the descriptive complexity of strings $\mathrm{K}(x)$ with an oracle for $A_{\text{TM }}$.

Use the result of Problem 6.21 to give a function $f$ that is computable with an oracle for $A_{\text{TM }}$, where for each $n, f(n)$ is an incompressible string of length $n$.

Show that the function $\mathrm{K}(x)$ is not a computable function.

Show that the set of incompressible strings is undecidable.

Show that the set of incompressible strings contains no infinite subset that is Turing-recognizable.

• Show that for any $c$, some strings $x$ and $y$ exist, where $\mathrm{K}(x y)>\mathrm{K}(x)+\mathrm{K}(y)+c$.

Let $S=\left\{ \langle M\rangle \mid M\text{ is a TM and }L(M)=\left\{ \langle M\rangle \right\} \right\}$. Show that neither $S$ nor $\bar{S}$ is Turing-recognizable.

Let $R \subseteq \mathcal{N}^{k}$ be a $k$-ary relation. Say that $R$ is definable in $\operatorname {Th}(\mathcal{N},+)$ if we can give a formula $\phi$ with $k$ free variables $x_{1}, \ldots , x_{k}$ such that for all $a_{1}, \ldots , a_{k} \in \mathcal{N}$, $\phi \left(a_{1}, \ldots , a_{k}\right)$ is true exactly when $a_{1}, \ldots , a_{k} \in R$. Show that each of the following relations is definable in $\operatorname {Th}(\mathcal{N},+)$.