Kleene normal form theorem

[4/100%]
Show
LaTeX
Problem III.2.24 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.2 "Turing Machines"

Prove that there exists a primitive recursive function S(z,x,y,w)S(z, x, y, w) such that

S(z,x,y,w)={1,if z=λ(T) and the machine T transforms the word q101x0 into the word q001y0…0 in at most w steps,0otherwise. S(z, x, y, w) = \begin{cases} 1, & \text{if } z = \lambda (T) \text{ and the machine } T \text{ transforms the word } q_{1}01^{x}0 \text{ into the word } q_{0}01^{y}0\ldots 0 \text{ in at most } w \text{ steps,} \\ 0 & \text{otherwise.} \end{cases}
?
Problem III.2.25 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.2 "Turing Machines"

Prove that there exist primitive recursive functions p,T1,T2,…p, T_{1}, T_{2}, \ldots such that:

?
(a)

U(m,x)=p(μy[T1(m,x,y)=0])U(m, x) = p(\mu y \left[T_{1}(m, x, y) = 0\right]);

(b)

Un+1(m,x1,…,xn)=p(μy[Tn(m,x1,…,xn,y)=0])U^{n+1}(m, x_{1}, \ldots , x_{n}) = p(\mu y \left[T_{n}(m, x_{1}, \ldots , x_{n}, y) = 0\right]).

Problem III.3.40 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that any partial recursive function f(x1,…,xn)f(x_{1}, \ldots , x_{n}) is representable in Kleene normal form, i.e., in the form

f(x1,…,xn)=l(μt[g(x1,…,xn,t)=0]), f(x_{1}, \ldots , x_{n}) = l(\mu t \left[g(x_{1}, \ldots , x_{n}, t) = 0\right]),

where g(x1,…,xn,t)g(x_{1}, \ldots , x_{n}, t) is a suitable primitive recursive function, and ll is the function from problem III.1.13 (cf. problem III.2.25).

?
Problem III.3.41 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that a partial function f(x1,…,xn)f(x_{1}, \ldots , x_{n}) is representable in the form

f(x1,…,xn)=μt[g(x1,…,xn,t)=0] f(x_{1}, \ldots , x_{n}) = \mu t \left[g(x_{1}, \ldots , x_{n}, t) = 0\right]

for a suitable primitive recursive function g(x1,…,xn,t)g(x_{1}, \ldots , x_{n}, t) if and only if the graph of the function f(x1,…,xn)f(x_{1}, \ldots , x_{n}) is primitive recursive.

?

References

[LaMa02] Lavrov I.A., Maksimova L.L. Задачи по теории множеств, математической логике и теории алгоритмов. 5-е изд., Физматлит, 2002.