s-m-n theorem

[18/72%]
Show
LaTeX
Problem 5.4.2 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.4 "Reducibility"

If g:{0,1}∗→{0,1}∗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]g^{-1}(x)=(\min y) [g(y)=x]. Show that there exists a recursive function ff such that for all one-to-one functions ϕm,ϕf(m)=ϕm−1\phi_{m}, \phi_{f(m)}=\phi_{m}^{-1}.

?
Problem 5.4.3 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.4 "Reducibility"

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

?
Problem 5.4.4 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.4 "Reducibility"
?
(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\}
Problem 5.5.8 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.5 "Recursion Theorem"

Prove that there exist two integers m≠nm \neq n such that Wm={n}W_{m}=\left\{ n\right\} and Wn={m}W_{n}=\left\{ m\right\}.

?
Problem 5.5.9 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.5 "Recursion Theorem"
?
(a)

Prove that the s−m−ns-m-n theorem can be improved so that each smns_{m}^{n} is a one-to-one function in the sense that if e1≠e2e_{1} \neq e_{2} then smn(e1,y1,…s_{m}^{n}\left(e_{1}, y_{1}, \ldots \right., yn)≠smn(e2,y1,…,yn)\left.y_{n}\right) \neq s_{m}^{n}\left(e_{2}, y_{1}, \ldots , y_{n}\right) for all y1,…,yn∈Ny_{1}, \ldots , y_{n} \in \mathbf{N}.

(b)

Show that for any partial recursive function gg and any constant nn, there exists a constant e>ne>n such that ϕe(x)=g(x,e)\phi_{e}(x)=g(x, e).

Example 5.29 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.4 "Reducibility"

The halting problem KK is complete.

?
Example 5.48 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.4 "Reducibility"

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

?
Problem III.4.3 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"

Prove that:

?
(a)

Kn+1(x0,x1,…,xn)K^{n+1}(x_{0}, x_{1}, \ldots , x_{n}) is universal for all nn-ary partial recursive functions;

(b)

for any partial recursive function fn+mf^{n+m} there is a primitive recursive function gng^{n} such that

f(x1,…,xn,y1,…,ym)=Km+1(g(x1,…,xn),y1,…,ym). f(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m}) = K^{m+1}(g(x_{1}, \ldots , x_{n}), y_{1}, \ldots , y_{m}).
Problem III.4.5 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"

Construct primitive recursive functions that give, from the Kleene numbers of the original one-place functions, the Kleene numbers of the functions obtained from the originals:

?
(a)

by means of superposition;

(b)

by means of inversion;

(c)

by means of iteration;

(d)

by means of taking the sum of two functions.

Problem III.4.8 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"

Construct primitive recursive functions that give, from the Kleene numbers of the original functions, the Kleene numbers of the functions obtained from the originals:

?
(a)

by means of superposition;

(b)

by means of primitive recursion;

(c)

by means of the μ\mu-operator.

Problem III.4.9 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"

Prove that for any partial recursive function f(x1,…,xn)f(x_{1}, \ldots , x_{n}) there is a primitive recursive function g(x1,…,xn)g(x_{1}, \ldots , x_{n}) such that for any xx

κg(x1,…,xn)={κf(x1,…,xn),if f(x1,…,xn) is defined,ωotherwise. \kappa _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \kappa _{f(x_{1}, \ldots , x_{n})}, & \text{if } f(x_{1}, \ldots , x_{n}) \text{ is defined,} \\ \omega & \text{otherwise.} \end{cases}
?
Problem III.4.10 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"
?
(a)

Prove that for every partial recursive function f(x1,…,xn,y)f(x_{1}, \ldots , x_{n}, y) there is a primitive recursive function g(x1,…,xn)g(x_{1}, \ldots , x_{n}) such that

κg(x1,…,xn)={κf(x1,…,xn,g(x1,…,xn)),if f(x1,…,xn,g(x1,…,xn)) is defined,ωotherwise. \kappa _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \kappa _{f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n}))}, & \text{if } f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n})) \text{ is defined,} \\ \omega & \text{otherwise.} \end{cases}
(b)

Prove that for every partial recursive function f(x)f(x) there is a natural number aa such that

κa={κf(a),if f(a) is defined,ωotherwise \kappa _{a} = \begin{cases} \kappa _{f(a)}, & \text{if } f(a) \text{ is defined,} \\ \omega & \text{otherwise} \end{cases}

(the fixed-point theorem).

Problem III.4.24 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"

Prove that for any partial recursive function fnf^{n} there is a primitive recursive function gng^{n} such that

πg(x1,…,xn)={πf(x1,…,xn),if f(x1,…,xn) is defined,∅otherwise. \pi _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \pi _{f(x_{1}, \ldots , x_{n})}, & \text{if } f(x_{1}, \ldots , x_{n}) \text{ is defined,} \\ \emptyset & \text{otherwise.} \end{cases}
?
Problem III.4.25 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"

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})}.
?
Problem III.4.26 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"

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)}.

Problem III.4.27 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"

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)}}.

Problem III.4.28 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"
?
(a)

Prove that for any partial recursive function fn+1f^{n+1} there is a primitive recursive function gng^{n} such that

πg(x1,…,xn)={πf(x1,…,xn,g(x1,…,xn)),if f(x1,…,xn,g(x1,…,xn)) is defined,∅otherwise. \pi _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \pi _{f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n}))}, & \text{if } f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n})) \text{ is defined,} \\ \emptyset & \text{otherwise.} \end{cases}
(b)

Prove that for any partial recursive function ff there is a number aa such that

πa={πf(a),if f(a) is defined,∅otherwise \pi _{a} = \begin{cases} \pi _{f(a)}, & \text{if } f(a) \text{ is defined,} \\ \emptyset & \text{otherwise} \end{cases}

(the fixed-point theorem).

Problem III.4.29 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"

Prove that for any recursively enumerable set M⊆Nn+2M \subseteq \mathbb {N}^{n+2} there is a primitive recursive function gng^{n} such that

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

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.