Effective operations on indices of r.e. sets

[9/67%]
Show
LaTeX

Assume that A∪B={0,1}∗A \cup B= \left\{ 0,1\right\}^{*} and A∩B≠∅A \cap B \neq \emptyset. Show that if AA and BB are r.e., then A≤mA∩BA \leq_{m} A \cap B.

?
?
(a)

Show that for every partial recursive function ff, there exists a recursive function gg such that Wg(x)=f−1(Wx)W_{g(x)}=f^{-1}\left(W_{x}\right).

(b)

Show that there is a recursive function gg such that for all x,yx, y,

Wg(x,y)=ϕx−1(Wy)={z∣ϕx(z)∈Wy} W_{g(x, y)}=\phi _{x}^{-1}\left(W_{y}\right)=\left\{ z \mid \phi _{x}(z) \in W_{y}\right\}

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

?
(a)

Show that there exists a partial recursive function p:{0,1}∗→{0,1}∗p: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*} such that Dp=Df∪Dg∪DhD_{p}=D_{f} \cup D_{g} \cup D_{h}, and for each x∈Dpx \in D_{p}, p(x)=f(x)p(x)=f(x) or p(x)=g(x)p(x)=g(x) or p(x)=h(x)p(x)=h(x).

(b)

Show that there does not always exist a partial recursive function q:{0,1}∗→{0,1}∗q: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*} such that Dq=Df∪Dg∪DhD_{q}=D_{f} \cup D_{g} \cup D_{h}, and for each x∈Dq,q(x)=f(x)x \in D_{q}, q(x)=f(x) or q(x)=g(x)q(x)=g(x) or q(x)=h(x)q(x)=h(x), and for each x∈Df∩Dg∩Dh,q(x)=min⁡{f(x),g(x),h(x)}x \in D_{f} \cap D_{g} \cap D_{h}, q(x)=\min \left\{ f(x), g(x), h(x)\right\}.

Let M1,…,MkM_{1}, \ldots , M_{k} be pairwise disjoint recursively enumerable sets of nn-tuples, f1,…,fnf_{1}, \ldots , f_{n} partial recursive functions. Prove that g(x1,…,xn)g(x_{1}, \ldots , x_{n}), defined as follows:

g(x1,…,xn)={f1(x1,…,xn),if ⟨x1,…,xn⟩∈M1,\makebox[0pt][l]\dotfillfk(x1,…,xn),if ⟨x1,…,xn⟩∈Mk,undefined otherwise, g(x_{1}, \ldots , x_{n}) = \begin{cases} f_{1}(x_{1}, \ldots , x_{n}), & \text{if } \langle x_{1}, \ldots , x_{n} \rangle \in M_{1}, \\ \makebox[0pt][l]{\dotfill } \\ f_{k}(x_{1}, \ldots , x_{n}), & \text{if } \langle x_{1}, \ldots , x_{n} \rangle \in M_{k}, \\ \text{undefined otherwise,} \end{cases}

is partial recursive.

?

Prove the recursive enumerability of the sets of all Kleene numbers of the following families of one-place partial recursive functions:

?
(a)

functions defined at the point 00;

(b)

functions ff such that f(a)=bf(a) = b for given numbers aa and bb;

(c)

functions with nonempty domain of definition.

Prove that the sets of all Post numbers of the following families of recursively enumerable sets are recursively enumerable:

?
(a)

those containing a given number aa;

(b)

the nonempty ones.

Prove that for every recursively enumerable set P⊆Nn+1P \subseteq \mathbb {N}^{n+1} (n>0n > 0) there is a primitive recursive function α(x1,…,xn)\alpha (x_{1}, \ldots , x_{n}) such that

⟨x0,x1,…,xn⟩∈P⇔x0∈πα(x1,…,xn). \langle x_{0}, x_{1}, \ldots , x_{n} \rangle \in P \Leftrightarrow x_{0} \in \pi _{\alpha (x_{1}, \ldots , x_{n})}.
?

Prove that there exist primitive recursive functions f,g,h,u,v,wf, g, h, u, v, w such that:

?
(a)

πx∩πy=πf(x,y)\pi_{x} \cap \pi_{y} = \pi_{f(x,y)};

(b)

πx∪πy=πg(x,y)\pi_{x} \cup \pi_{y} = \pi_{g(x,y)};

(c)

{x}=πh(x)\left\{ x\right\} = \pi_{h(x)};

(d)

{c(s,t)∣s∈πx,t∈πy}=πu(x,y)\left\{ c(s,t) \mid s \in \pi_{x}, t \in \pi_{y}\right\} = \pi_{u(x,y)};

(e)

κy(πx)=πv(x,y)\kappa_{y}(\pi_{x}) = \pi_{v(x,y)};

(f)

κy−1(πx)=πw(x,y)\kappa_{y}^{-1}(\pi_{x}) = \pi_{w(x,y)}.

Prove that there exist primitive recursive functions ff and gg such that:

?
(a)

δκx=ρκf(x)\delta_{\kappa_{x}} = \rho_{\kappa_{f(x)}};

(b)

ρκx=δκg(x)\rho_{\kappa_{x}} = \delta_{\kappa_{g(x)}}.

References

[DuKo01] Du D., Ko K. Problem Solving in Automata, Languages, and Complexity. John Wiley & Sons, 2001.
[LaMa02] Lavrov I.A., Maksimova L.L. Задачи по теории множеств, математической логике и теории алгоритмов. 5-е изд., Физматлит, 2002.