Math Problems Vault

Problem III.1.43 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.1 "Partial Recursive Functions"

Prove that there is no primitive recursive function universal for the family of all $n$ -ary primitive recursive functions.

?

Problem III.1.44 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.1 "Partial Recursive Functions"

Prove that there is no partial recursive function universal for the family of all $n$ -ary general recursive functions.

?

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

Prove that there exists a two-place partial recursive function $U(t, x)$ universal for the family of all one-place partial recursive functions.

?

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

Prove that there exists an $(n+1)$ -place partial recursive function $U^{n+1}(t, x_{1}, \ldots , x_{n})$ universal for the family of all $n$ -ary partial recursive functions.

?

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

(a)(b)

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

?

(a)

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

(b)

$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.45 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that if $V(n,x)$ is a partial recursive function universal for the class of all one-place partial recursive functions, then the set $M = \left\{ x \mid V(x,x) = 0\right\}$ is recursively enumerable but not recursive.

?

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

Prove that if $V(n,x)$ is a partial recursive function universal for the class of all one-place partial recursive functions, then the set

G = \left\{ n \mid V(n,x) \text{ is a general recursive function}\right\}

is not recursively enumerable.

?

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

(a)(b)

Prove that:

?

(a)

$K^{n+m+1}(x_{0}, x_{1}, \ldots , x_{n}, x_{n+1}, \ldots , x_{n+m}) = K^{m+1}([x_{0}, x_{1}, \ldots , x_{n}], x_{n+1}, \ldots , x_{n+m})$ ;

(b)

$K^{n}(c(x_{0}, x_{1}), x_{2}, \ldots , x_{n}) = U^{n+1}(x_{0}, x_{1}, x_{2}, \ldots , x_{n})$ .

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

(a)(b)

Prove that:

?

(a)

$K^{n+1}(x_{0}, x_{1}, \ldots , x_{n})$ is universal for all $n$ -ary partial recursive functions;

(b)

for any partial recursive function $f^{n+m}$ there is a primitive recursive function $g^{n}$ such that

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

Prove that every partial recursive function $f$ has infinitely many Kleene numbers.

?

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

(a)(b)

Prove that there is a recursively enumerable set $P$ satisfying the conditions:

?

(a)

if $x \in P$ , then $\kappa_{x}$ is a primitive recursive function;

(b)

for any primitive recursive function $f$ there is $x \in P$ such that $f = \kappa_{x}$ .

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

Prove that there is a general recursive function universal for the family of all one-place primitive recursive functions.

?

Universal functions (computability)

References