Math Problems Vault

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

(a)(b)

?

(a)

Prove that the function $f^{n+1}$ , arising from the partial functions $g^{n}$ and $h^{n+2}$ by means of the primitive recursion operator, can be obtained by means of a special recursion of the form:

\begin{cases} F(x, 0) = x, \\ F(x, y+1) = G(F(x, y)) \end{cases}

and superpositions from the functions $g^{n}, h^{n+2}, o, s, I_{m}^{n}$ and $c, l, r$ from problem III.1.13.

(b)

Prove that the function $f(x)$ , obtained from $a$ and $h(x, y)$ by means of the primitive recursion operator, can be obtained by means of iteration and superpositions from the functions $a, h, o, s, I_{m}^{n}$ and $c, l, r$ from problem III.1.13.

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

Prove that the function $f^{n}$ , obtained from the partial function $g^{n+1}$ by means of the $\mu$ -operator, can be obtained from the functions $g, I_{m}^{n}$ and $c, l, r$ from problem III.1.13 by means of superpositions and a $\mu$ -operator of the special form.

F(x) = \mu y \left[G(x, y) = 0\right].

?

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

Prove that the function $f^{n+1}$ , obtained by means of the primitive recursion operator from everywhere defined functions $g^{n}$ and $h^{n+2}$ , can be obtained from these functions and the functions $+, \symdiff , s, o, I_{m}^{n}$ and $c, l, r, \beta$ from problems III.1.13, III.1.17, by means of superpositions and a $\mu$ -operator of the special form from problem III.1.29.

?

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

Prove that:

?

(a)

$\mathbf{i}(ax+b) = b \cdot \dfrac {a^{x} - 1}{a - 1}$ for $a > 1$ ;

(b)

$\mathbf{i}\left(1 + \left[\dfrac {x}{2}\right]\right) = \operatorname {sg} x$ ;

(c)

$\mathbf{i}\left(x + 1 + \left[\dfrac {x+1}{2}\right] - \left[\dfrac {x}{2}\right]\right) = 2x \symdiff 1$ ;

(d)

$\mathbf{i}(\overline{\operatorname {sg}}\, x + 2x) = 2^{x-1} \symdiff \overline{\operatorname {sg}}\, x$ ;

(e)

$\mathbf{i}(x + 1 + \sqrt{4x+1}) = x^{2} + x$ ;

(f)

$\mathbf{i}\left(x + 1 + 2\left[\sqrt{x}\right]\right) = x^{2}$ .

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

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

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

Prove that every primitive recursive function can be obtained from the functions $s(x) = x+1$ and $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ by means of the operations of substitution, iteration, and addition of two functions (R. Robinson's theorem).

?

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

(a)(b)

Prove that:

?

(a)

$I_{1}^{1}(f(x)) = f(I_{1}^{1}(x)) = f(f^{-1}(f(x))) = f(x)$ ;

(b)

$f^{-1}(f(f^{-1}(x))) = f^{-1}(x)$ .

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

(a)(b)(c)

Prove that:

?

(a)

if $f^{-1}(x)$ is defined at some point $a$ , then

f(f^{-1}(a)) = a;

(b)

if $f^{-1}(x)$ is everywhere defined, then

f(f^{-1}(x)) = I_{1}^{1}(x);

(c)

there exists $f(x)$ such that $f^{-1}(x)$ is everywhere defined, but

f^{-1}(f(x)) \neq I_{1}^{1}(x).

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

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

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

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

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

Let $f(x) = \mu y \left[h(x, y) = 0\right]$ . Prove that $f(x)$ can be obtained from $h, s(x) = x+1$ , and $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ by means of the operations of substitution, inversion, and addition of two functions.

?

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

Prove that every partial recursive function can be obtained from $s(x) = x+1$ , $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ by means of the operations of substitution, inversion, and addition of two functions (Yu. Robinson's theorem).

?

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

Let the function $f$ be partial recursive but not general recursive. Prove that the domain of definition of the function $f^{-1}$ is primitive recursive.

?

Alternative bases for recursive function classes

References