Reducibility

Assume that both $A$ and $B$ are nonempty proper subsets of $\Sigma^{*}$.

Show that the set $\mathrm{EMP}=\left\{ x \mid W_{x}=\emptyset \right\}$ is not recursive.

The halting problem $K$ is complete.

Let $A$ be a nontrivial function-index set. Show that if EMP $\subseteq A$, then $A$ is not r.e. Thus, the following index sets are not r.e: $\overline{A_{1}}$, EMP, $\overline{\text{ Tot }}$, Fin, Rec, Reg and Rev.

Let $A$ be an r.e. index set. Show that if $x \in A$ and $W_{x} \subseteq W_{y}$ then $y \in A$. Thus, the following sets are not r.e.: $\overline{\operatorname {REC}}, \overline{\operatorname {REG}}, \overline{\operatorname {REV}}$.

Let $A$ be an r.e. function-index set. Show that if $x \in A$ then there exists $y \in A$ such that $W_{y}$ is a finite subset of $W_{x}$. Thus, the following sets are not r.e.: Tot, $\overline{\text{ FIN }}$.

Show that TOT $\leq_{m} \overline{\text{ FIN }}$ and $\overline{\text{ FIN }} \leq_{m}$ TOT.

(Revisited) Show, by the $s-m-n$ theorem, that $K \leq_{m} \overline{\text{ EMP }}$.

Assume that $A \cup B= \left\{ 0,1\right\}^{*}$ and $A \cap B \neq \emptyset$. Show that if $A$ and $B$ are r.e., then $A \leq_{m} A \cap B$.

If $g: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ is one-to-one, then we define $g^{-1}(x)=(\min y) [g(y)=x]$. Show that there exists a recursive function $f$ such that for all one-to-one functions $\phi_{m}, \phi_{f(m)}=\phi_{m}^{-1}$.

Show that there exists a recursive function $c(x, y)$ such that $\phi_{c(x, y)}(z)= \phi_{x}\left(\phi_{y}(z)\right)$.

(Rice's theorem for r.e. index sets) For any finite set $D=\left\{ x_{1}, \ldots , x_{n}\right\}$, we say $\left[x_{1}, \ldots , x_{n}\right]$ (in any order) is a code of $D$. Show that an index set $A$ is r.e. if and only if

1. $x \in A$ and $W_{x} \subseteq W_{y}$ imply $y \in A$;

2. $x \in A$ implies that there exists $y \in A$ such that $W_{y}$ is a finite subset of $W_{x}$; and

3. There exists an r.e. set $B$ that contains codes of all and only finite sets $W_{x}$ such that $x \in A$ (i.e., for each $x \in A$ such that $W_{x}$ is finite, $B$ contains at least one of its code, and for every $\left[x_{1}, \ldots , x_{n}\right] \in B$ and every $x$ such that $\left.W_{x}=\left\{ x_{1}, \ldots , x_{n}\right\} , x \in A\right)$.

For any partial recursive function $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$, we write $D_{f}$ to denote its domain $\left\{ x \mid f(x) \downarrow \right\}$. Let $f, g, h: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ be three partial recursive functions.

Define

Is $f$ a partial recursive function? Prove your answer.

Let $\mathcal{C}_{1}$ be the class of all recursive sets, $\mathcal{C}_{2}$ the class of all r.e. sets which are not recursive, $\mathcal{C}_{3}$ the class of all co-r.e. sets which are not r.e., and $\mathcal{C}_{4}$ the class of all sets that are neither r.e. nor co-r.e. For each of the following sets, determine in which class $\mathcal{C}_{i}, i \in \left\{ 1,2,3,4\right\}$, it belongs to.

A set $A$ is called single-valued if for each $y$, there exists at most one $z$ such that $\langle y, z\rangle \in A$. Let $B_{12}=\left\{ x \mid W_{x}\text{ is single-valued }\right\}$. Show that EMP $\leq_{m} B_{12}$ and $B_{12} \leq_{m}$ EMP,

Prove the following reductions:

Let $B_{13}=\left\{ x \mid W_{x}=K\right\}$.

Let $B_{14}=\left\{ x \mid \left(\exists y \in W_{x}\right)\left[W_{y}\right.\text{ is infinite }]\right\}$.

A set $B \subseteq \left\{ 0,1\right\}^{*}$ is called productive if there exists a partial recursive function $f$ such that for every $x$, if $W_{x} \subseteq B$ then $f(x) \downarrow$ and $f(x) \in B-W_{x}$.

Show that there exist two r.e. sets $A$ and $B$ such that $A \leq_{m} B$ and $B \leq_{m} A$.