All textbooks/Problems in Set Theory, Mathematical Logic and the Theory of Algorithms

Part III

Part III. Theory of Algorithms

[160/85%]

Show

LaTeX

Show LaTeX

On this page

III.1 · Partial Recursive Functions

III.2 · Turing Machines

III.3 · Recursive and Recursively Enumerable Sets

III.4 · Kleene and Post Numberings

Chapter III.1Partial Recursive Functions[44/77%]

Problem III.1.1

Prove that every primitive recursive function is everywhere defined.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.2

(a)(b)(c)(d)

Prove that if the function $f^{n}(x_{1}, \ldots , x_{n})$ is primitive recursive, then the following functions are primitive recursive:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$f_{1}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, x_{1}, \ldots , x_{n})$ (permutation of arguments);

(b)

$f_{2}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, \ldots , x_{n}, x_{1})$ (cyclic permutation of arguments);

(c)

$f_{3}(x_{1}, \ldots , x_{n}, x_{n+1}) = f(x_{1}, \ldots , x_{n})$ (introduction of a dummy argument);

(d)

$f_{4}(x_{1}, \ldots , x_{n-1}) = f(x_{1}, x_{1}, \ldots , x_{n-1})$ (identification of arguments).

Problem III.1.3

Which functions are obtained from the simplest functions using superpositions alone?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.4

Prove that the functions $x+1$ and $2x$ cannot be obtained from $o^{1}$ and $I_{m}^{n}$ using superpositions and primitive recursion schemes.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.5

(a)(b)(c)(d)(e)(f)

Prove that the following functions are primitive recursive:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$f(x) = x + n$ ;

(b)

$f(x) = n$ ;

(c)

$f(x, y) = x + y$ ;

(d)

$f(x, y) = x \cdot y$ ;

(e)

$f(x, y) = x^{y}$ (here $0^{0} = 1$ );

(f)

$f(x, y) = x!$ (here $0! = 1$ ).

Problem III.1.6

(a)(b)

Which function is obtained from $g$ and $h$ by means of the primitive recursion scheme:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$g(x) = x$ , $h(x, y, z) = z^{x}$ ;

(b)

$g(x) = x$ , $h(x, y, z) = x^{z}$ ?

Problem III.1.7

(a)(b)(c)(d)(e)(f)(g)

Prove that the following functions are primitive recursive:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\operatorname {sg}(x) = \begin{cases} 0, & \text{if } x = 0, \\ 1, & \text{if } x > 0; \end{cases}$

(b)

$\overline{\operatorname {sg}}(x) = \begin{cases} 0, & \text{if } x > 0, \\ 1, & \text{if } x = 0; \end{cases}$

(c)

$x \symdiff 1 = \begin{cases} 0, & \text{if } x = 0, \\ x - 1, & \text{if } x > 0; \end{cases}$

(d)

$x \symdiff y = \begin{cases} 0, & \text{if } x \leq y, \\ x - y, & \text{if } x > y; \end{cases}$

(e)

$\left|x - y\right|$ ;

(f)

$\max (x, y)$ ;

(g)

$\min (x, y)$ .

Problem III.1.8

(a)(b)(c)(d)

Prove the following identities:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$x \symdiff y = s(x) \symdiff s(y)$ ;

(b)

$x + (y \symdiff x) = y + (x \symdiff y)$ ;

(c)

$x \symdiff (y+z) = (x \symdiff y) \symdiff z$ ;

(d)

$(x \symdiff y) \symdiff z = (x \symdiff z) \symdiff y$ .

Problem III.1.9

(a)(b)(c)(d)(e)(f)

Let $g^{n+1}, \alpha^{m}, \beta^{m}$ be primitive recursive functions. Prove that the following functions are primitive recursive:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$f^{n+1}(x_{1}, \ldots , x_{n}, x_{n+1}) = \displaystyle \sum_{i=0}^{x_{n+1}} g(x_{1}, \ldots , x_{n}, i)$ ;

(b)

$f^{n+2}(x_{1}, \ldots , x_{n}, y, z) = \begin{cases} \displaystyle \sum_{i=y}^{z} g(x_{1}, \ldots , x_{n}, i), & \text{if } y \leq z, \\ 0, & \text{if } y > z; \end{cases}$

(c)

$f^{n+m}(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m}) = \begin{cases} \displaystyle \sum_{i=\alpha (y_{1}, \ldots , y_{m})}^{\beta (y_{1}, \ldots , y_{m})} g(x_{1}, \ldots , x_{n}, i), & \text{if } \alpha (y_{1}, \ldots , y_{m}) \leq \beta (y_{1}, \ldots , y_{m}), \\ 0, & \text{otherwise;} \end{cases}$

(d)

$f^{n+1}(x_{1}, \ldots , x_{n}, x_{n+1}) = \displaystyle \prod_{i=0}^{x_{n+1}} g(x_{1}, \ldots , x_{n}, i)$ ;

(e)

$f^{n+2}(x_{1}, \ldots , x_{n}, y, z) = \begin{cases} \displaystyle \prod_{i=y}^{z} g(x_{1}, \ldots , x_{n}, i), & \text{if } y \leq z, \\ 0, & \text{if } y > z; \end{cases}$

(f)

$f^{n+m}(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m}) = \begin{cases} \displaystyle \prod_{i=\alpha (y_{1}, \ldots , y_{m})}^{\beta (y_{1}, \ldots , y_{m})} g(x_{1}, \ldots , x_{n}, i), & \text{if } \alpha (y_{1}, \ldots , y_{m}) \leq \beta (y_{1}, \ldots , y_{m}), \\ 0, & \text{otherwise.} \end{cases}$

Problem III.1.10

Prove that if $f$ is obtained from primitive recursive functions $g$ and $h$ by means of the bounded $\mu$ -operator, then $f$ is primitive recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.11

Let the functions $f_{0}^{n}, f_{1}^{n}, \ldots , f_{s}^{n}$ have the following property: for any natural values $x_{1}, \ldots , x_{n}$ , one and only one of these functions equals $0$ . We say that the function $g^{n}$ is defined by cases, if

g^{n}(x_{1}, \ldots , x_{n}) = \begin{cases} h_{0}^{n}(x_{1}, \ldots , x_{n}), & \text{if } f_{0}^{n}(x_{1}, \ldots , x_{n}) = 0, \\ \makebox[0pt][l]{\dotfill } \\ h_{s}^{n}(x_{1}, \ldots , x_{n}), & \text{if } f_{s}^{n}(x_{1}, \ldots , x_{n}) = 0. \end{cases}

Prove that if the functions $h_{0}^{n}, \ldots , h_{s}^{n}, f_{0}^{n}, \ldots , f_{s}^{n}$ are primitive recursive, then $g^{n}$ is primitive recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.12

(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

(q)

Problem III.1.13

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Prove that the function

c(x, y) = \frac{(x+y)^{2} + 3x + y}{2}

(the Cantor pairing function) is a bijection between $\mathbb {N}^{2}$ and $\mathbb {N}$ (i.e., it numbers pairs of natural numbers).

(b)

Let $l(x)$ and $r(x)$ be such that

c(l(x), r(x)) = x.

Prove that $l(x)$ and $r(x)$ are primitive recursive and $l(c(x, y)) = x$ , $r(c(x, y)) = y$ .

Problem III.1.14

(a)(b)(c)

For each $n \geq 1$ define the functions

c^{1}(x_{1}) = x_{1}, \qquad c^{n+1}(x_{1}, x_{2}, x_{3}, \ldots , x_{n+1}) = c^{n}(c(x_{1}, x_{2}), x_{3}, \ldots , x_{n+1})

(see problem III.1.13).

Let $c_{i}^{n}$ ( $1 \leq i \leq n$ ) be such that $c^{n}(c_{1}^{n}(x), \ldots , c_{n}^{n}(x)) = x$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Prove the identities

c_{i}^{n}(c^{n}(x_{1}, \ldots , x_{n})) = x_{i} \ \text{for } 1 \leq i \leq n.

(b)

Prove that the functions $c^{n}$ and $c_{i}^{n}$ are primitive recursive.

(c)

Prove that the functions $c^{n}(x_{1}, \ldots , x_{n})$ are bijections between $\mathbb {N}^{n}$ and $\mathbb {N}$ (i.e., they number $n$ -tuples of natural numbers).

Problem III.1.15

How can all partial recursive functions be obtained from one-place partial recursive functions and the functions $c^{n}(x_{1}, \ldots , x_{n})$ ?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.16

(a)(b)

Call a one-place function $f(x)$ a function of large spread, if it takes on every natural number as its value infinitely many times.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Let the pair of functions $\langle f_{1}(x), f_{2}(x) \rangle$ map $\mathbb {N}$ onto $\mathbb {N}^{2}$ . Prove that $f_{1}(x)$ and $f_{2}(x)$ are functions of large spread.

(b)

Let $f_{1}(x)$ be an arbitrary primitive recursive function of large spread. Construct a primitive recursive function $f_{2}(x)$ so that the functions $f_{1}(x)$ and $f_{2}(x)$ form a bijection between $\mathbb {N}$ and $\mathbb {N}^{2}$ .

Problem III.1.17

Consider the Godel function

\beta (x, y, z) = \operatorname {rest}(x, 1 + y(z+1)).

Prove that, whatever the finite sequence of natural numbers $a_{1}, \ldots , a_{n}$ may be, the system of equations

\begin{cases} \beta (x, y, 0) = \alpha _{0}, \\ \makebox[0pt][l]{\dotfill } \\ \beta (x, y, n) = \alpha _{n}, \end{cases}

has at least one solution $x, y$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.18

Prove that if the functions $g, h, t_{1}, \ldots , t_{s}$ are primitive recursive and $f$ is obtained from them by course-of-values recursion with delays, then the function $f$ is primitive recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.19

Prove that the function enumerating the Fibonacci numbers in order:

\begin{cases} f(0) = 0, \quad f(1) = 1, \\ f(n+2) = f(n) + f(n+1), \end{cases}

is primitive recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.20

Let the functions $f$ and $g$ be defined as follows:

\begin{cases} f(0) = a, \quad g(0) = b, \\ f(x+1) = h_{1}(x, f(x), g(x)), \\ g(x+1) = h_{2}(x, f(x), g(x)). \end{cases}

Prove that if the functions $h_{1}$ and $h_{2}$ are primitive recursive, then the functions $f$ and $g$ are primitive recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.21

Let $f_{1}^{n+1}, \ldots , f_{k}^{n+1}$ be defined by means of simultaneous recursion:

\begin{cases} f_{i}^{n+1}(x_{1}, \ldots , x_{n}, 0) = g_{i}^{n}(x_{1}, \ldots , x_{n}), \\ f_{i}^{n+1}(x_{1}, \ldots , x_{n}, y+1) = \\ \hphantom {f_{i}^{n+1}(x_{1}, \ldots , x_{n}, y+1) =} \, h_{i}^{n+k+1}(x_{1}, \ldots , x_{n}, y, f_{1}(x_{1}, \ldots , x_{n}, y), \ldots , f_{k}(x_{1}, \ldots , x_{n}, y)) \end{cases}

for all $1 \leq i \leq k$ .

Prove that if the functions $g_{1}, \ldots , g_{k}, h_{1}, \ldots , h_{k}$ are primitive recursive, then the functions $f_{1}, \ldots , f_{k}$ are primitive recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.22

Prove that every primitive recursive function is general recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.23

(a)(b)(c)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Prove that the superposition of general recursive functions is a general recursive function.

(b)

Prove that applying the primitive recursion operator to general recursive functions yields a general recursive function.

(c)

Give an example of a general recursive function from which the $\mu$ -operator yields a function that is not general recursive.

Problem III.1.24

(a)(b)(c)(d)

Prove that if the function $f(x_{1}, \ldots , x_{n})$ is partial recursive, then the following functions are partial recursive:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$f_{1}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, x_{1}, \ldots , x_{n})$ (permutation of arguments);

(b)

$f_{2}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, \ldots , x_{n}, x_{1})$ (cyclic permutation of arguments);

(c)

$f_{3}(x_{1}, \ldots , x_{n}, x_{n+1}) = f(x_{1}, \ldots , x_{n})$ (introduction of a dummy argument);

(d)

$f_{4}(x_{1}, \ldots , x_{n-1}) = f(x_{1}, x_{1}, \ldots , x_{n-1})$ (identification of arguments).

Problem III.1.25

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

there are exactly $\aleph_{0}$ partial recursive functions;

(b)

there is a partial numerical function that is not partial recursive;

(c)

there is an everywhere defined numerical function that is not general recursive.

Problem III.1.26

(a)(b)(c)(d)(e)

Prove that the following functions are partial recursive:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

the nowhere defined function $\omega$ , i.e., the function $\omega$ with empty domain of definition;

(b)

$f(x, y) = \begin{cases} x - y, & \text{if } x \geq y, \\ \text{undefined otherwise}; \end{cases}$

(c)

$f(x, y) = \begin{cases} \dfrac {x}{y}, & \text{if } y \text{ divides } x, \\ \text{undefined otherwise}; \end{cases}$

(d)

$f(x, y) = \begin{cases} z, & \text{if } z^{y} = x, \\ \text{undefined otherwise}; \end{cases}$

(e)

a function defined at finitely many points.

Problem III.1.27

(a)(b)(c)(d)(e)(f)

Prove that if the functions $g^{n+1}, h^{n+1}$ , and $t^{n+1}$ are partial recursive, then the following functions are partial recursive:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) = h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(b)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) \neq h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(c)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) \leq h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(d)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) < h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(e)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) = 0 \text{ and } h(x_{1}, \ldots , x_{n}, y) = 0\right]$ ;

(f)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) = 0 \text{ or } h(x_{1}, \ldots , x_{n}, y) \leq t(x_{1}, \ldots , x_{n}, y)\right]$ .

Problem III.1.28

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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

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].

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.30

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.31

(a)(b)(c)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Let $\sqrt{2} = a_{0}, a_{1}a_{2}, \ldots$ be the expansion of the number $\sqrt{2}$ as an infinite decimal fraction. Prove that the function $a_{n}$ is general recursive.

(b)

Let $e = a_{0}, a_{1}a_{2}, \ldots$ be the expansion of the number $e$ as an infinite decimal fraction. Prove that the function $a_{n}$ is general recursive.

(c)

Let $\pi = a_{0}, a_{1}a_{2}, \ldots$ be the expansion of the number $\pi$ as an infinite decimal fraction. Prove that the function $a_{n}$ is general recursive.

Problem III.1.32

Let $\alpha = a_{0}, a_{1}a_{2}, \ldots$ be the expansion of the real number $\alpha$ as an infinite decimal fraction. Call the number $\alpha$ general recursive (constructive), if $a_{n}$ is a general recursive function of $n$ . Prove that algebraic numbers are general recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.33

(a)(b)(c)(d)(e)(f)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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

(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

Problem III.1.35

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.36

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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

(a)(b)(c)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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

(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

Problem III.1.39

(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

Problem III.1.40

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.41

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.42

(a)(b)(c)(d)(e)(f)(g)(h)

Consider the following Ackermann functions:

B(0, y) = 2+y; \qquad B(x+1, 0) = \operatorname {sg} x; \qquad B(x+1, y+1) = B(x, B(x+1, y)); \qquad A(x) = B(x, x).

Call an everywhere defined function $f(x_{1}, \ldots , x_{n})$ $B$ -majorized, if there is a natural number $m$ such that

f(x_{1}, \ldots , x_{n}) < B(m, \max (x_{1}, \ldots , x_{n}) + 3).

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$B(x, y)$ and $A(x)$ are general recursive;

(b)

$B(n+2, x+1) \geq 2^{x+1}$ ;

(c)

$B(n+1, x+2) \geq B(n+1, x+1)$ ;

(d)

$B(n+2, x+3) \geq B(n+1, x+4)$ ;

(e)

the simplest functions are $B$ -majorized;

(f)

a function obtained by means of superposition from $B$ -majorized functions is $B$ -majorized;

(g)

a function obtained by means of primitive recursion from $B$ -majorized functions is $B$ -majorized;

(h)

the function $A$ is not primitive recursive.

Problem III.1.43

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.1.44

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Chapter III.2Turing Machines[25/96%]

Problem III.2.1

Which function $f(x)$ is computed by the machine $T$ with the following program of commands:

q_{1}0 \to q_{2}0R, \qquad q_{1}1 \to q_{0}1, \qquad q_{2}0 \to q_{0}1, \qquad q_{2}1 \to q_{2}1R \, ?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.2

Let the machine $T$ have the following program:

q_{1}0 \to q_{0}0.

Which functions $f_{1}(x), f_{2}(x_{1}, x_{2}), \ldots , f_{n}(x_{1}, \ldots , x_{n}), \ldots$ does this machine compute?

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.3

Construct a Turing machine that correctly computes the function $f(x) = x+1$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.4

Construct a Turing machine that correctly computes the function $o(x) = 0$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.5

Construct the following Turing machines:

Zero transfer: $q_{1}001^{x}0 \mid \Rightarrow_{A} q_{0}01^{x}00$ .
Right shift: $q_{1}001^{x}0 \mid \Rightarrow_{B^{+}} 01^{x}q_{0}0$ .
Left shift: $01^{x}q_{1}0 \mid \Rightarrow_{B^{-}} q_{0}01^{x}0$ .
Transposition: $01^{x}q_{1}01^{y}0 \mid \Rightarrow_{C} 01^{y}q_{0}01^{x}0$ .
Doubling: $q_{1}01^{x}0 \Rightarrow_{D} q_{0}01^{x}01^{x}0$ .
Cyclic shift: $q_{1}01^{x_{1}}01^{x_{2}}\ldots 01^{x_{n}}0 \mid \Rightarrow_{\text{Cy}_{n}} q_{0}01^{x_{2}}\ldots 01^{x_{n}}01^{x_{1}}0$ .
Copying: $q_{1}01^{x_{1}}\ldots 01^{x_{n}}0 \Rightarrow_{\text{Cp}_{n}} q_{0}01^{x_{1}}\ldots 01^{x_{n}}01^{x_{1}}\ldots 01^{x_{n}}0$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.6

Construct a Turing machine that correctly computes the function $I_{m}^{n}(x_{1}, \ldots , x_{n})$ (where $1 \leq m \leq n$ ).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.7

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

Let the functions $f(x)$ and $g(x)$ be correctly Turing computable. Show that the function $h(x) = f(g(x))$ is correctly Turing computable.

(b)

Let the functions $f(x_{1}, \ldots , x_{n})$ and $g_{1}(x_{1}, \ldots , x_{m}), \ldots , g_{n}(x_{1}, \ldots , x_{m})$ be correctly Turing computable. Show that the function $h(x_{1}, \ldots , x_{n}) = f(g_{1}(x_{1}, \ldots , x_{m}), \ldots , g_{n}(x_{1}, \ldots , x_{m}))$ is correctly Turing computable.

Problem III.2.8

(a)(b)(c)(d)(e)(f)(g)(h)

Construct a Turing machine for the correct computation of the functions:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$x+y$ ;

(b)

$x \symdiff 1$ ;

(c)

$\operatorname {sg}(x)$ ;

(d)

$\overline{\operatorname {sg}}(x)$ ;

(e)

$x \symdiff y$ ;

(f)

$x - y$ ;

(g)

$\dfrac {x}{2}$ ;

(h)

$\left[\dfrac {x}{2}\right]$ .

Problem III.2.9

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if the function $f^{n+1}$ is obtained from correctly Turing computable functions $g^{n}$ and $h^{n+2}$ by means of primitive recursion, then $f^{n+1}$ is correctly Turing computable;

(b)

if the function $f^{n}$ is obtained from a correctly Turing computable function $g^{n+1}$ by means of the $\mu$ -operator, then $f^{n}$ is correctly Turing computable.

Problem III.2.10

Prove that every partial recursive function is correctly Turing computable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.11

(a)(b)(c)

Prove that there exist primitive recursive functions $\alpha , \beta , \gamma$ such that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\alpha (x, y) = \lambda (T_{1} \cdot T_{2})$ , if $\lambda (T_{1}) = x$ and $\lambda (T_{2}) = y$ ;

(b)

$\beta (x) = \lambda (T)$ for some machine $T$ that transforms the word $q_{1}0$ into the word $q_{1}01^{x}0$ ;

(c)

$\gamma (x, y, z) = \lambda \left(T_{1}\begin{cases} q_{i} = T_{2} \\ q_{j} = T_{3} \end{cases}\right)$ , if $\lambda (T_{1}) = x$ , $\lambda (T_{2}) = y$ , $\lambda (T_{3}) = z$ .

Problem III.2.12

Construct primitive recursive functions $\gamma^{n}(x_{1}, \ldots , x_{n})$ such that

\nu (q_{1}01^{x_{1}}\ldots 01^{x_{n}}0) = \gamma ^{n}(x_{1}, \ldots , x_{n}).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.13

Construct a primitive recursive function $\rho (s, k, l, u, \nu )$ satisfying the condition: if $u = k_{l}(A)$ , $\nu = k_{r}(B)$ , $0 \leq s \leq 2$ , then $\rho (s, k, l, u, \nu ) = \nu ((Aq_{i}a_{j}B)_{T}')$ , where $T(i,j)$ is $q_{i}a_{j} \to q_{k}a_{l}$ for $s=0$ , $q_{i}a_{j} \to q_{k}a_{l}L$ for $s=1$ , $q_{i}a_{j} \to q_{k}a_{l}R$ for $s=2$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.14

Construct a primitive recursive function $\sigma (t, i, j, u, \nu )$ satisfying the condition: if $u = k_{l}(A)$ , $\nu = k_{r}(B)$ , $t = \lambda (T)$ , $q_{i}$ occurs in the alphabet of internal states, and $a_{j}$ in the external alphabet of the machine $T$ , then $\sigma (t, i, j, u, \nu ) = \nu ((Aq_{i}a_{j}B)_{T}')$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.15

Construct a primitive recursive function $\tau (t, x)$ satisfying the condition: if $t = \lambda (T)$ , $x = \nu (M)$ , where $M = Aq_{i}a_{j}B$ is a machine word in the alphabet of the machine $T$ , then $\tau (t,x) = \nu (M_{T}')$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.16

Construct a primitive recursive function $w(t, x, y)$ satisfying the condition: if $t = \lambda (T)$ , $x = \nu (M)$ , where $M$ is a machine word in the alphabet of the machine $T$ , then $w(t, x, y) = \nu (M_{T}^{(y)})$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.17

Construct a primitive recursive function $\varepsilon (x)$ satisfying the condition: if $x = \nu (M)$ , then $\varepsilon (x)$ is the number of occurrences of the symbol $a_{1}$ in the word $M$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.18

(a)(b)

Prove that if the machine $T$ computes $f(x_{1}, \ldots , x_{n})$ and $t_{0} = \lambda (T)$ , then:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\langle x_{1}, \ldots , x_{n} \rangle \in \delta_{f} \Leftrightarrow \operatorname {ex}(1, w(t_{0}, \gamma^{n}(x_{1}, \ldots , x_{n}), y)) = 0$ for some $y$ ;

(b)

$f(x_{1}, \ldots , x_{n}) = \varepsilon (w(t_{0}, \gamma^{n}(x_{1}, \ldots , x_{n}), h^{n+1}(t_{0}, x_{1}, \ldots , x_{n})))$ , where $h^{n+1}(t_{0}, x_{1}, \ldots , x_{n}) = \mu y \left[\operatorname {ex}(1, w(t_{0}, \gamma^{n}(x_{1}, \ldots , x_{n}), y)) = 0\right]$ , and the functions $\gamma , w$ , and $\varepsilon$ are taken from problems III.2.12, III.2.16, and III.2.17.

Problem III.2.19

Prove that every Turing computable function is partial recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.20

Prove that a function is Turing computable if and only if there is a Turing machine with external alphabet $\left\{ 0,1\right\}$ computing this function.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.21

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.22

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.23

(a)(b)(c)

Prove that the following functions are not partial recursive:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$h(x, y) = \begin{cases} 1, & \text{if } x \text{ is the number of a machine } T \text{ and the machine } T \text{ halts, starting to work from the machine word } q_{1}01^{y}0, \\ 0 & \text{otherwise;} \end{cases}$

(b)

$g(x) = h(x,x)$ ;

(c)

$h_{0}(x) = \begin{cases} 1, & \text{if } x \text{ is the number of a machine } T \text{ and the machine } T \text{ halts, starting to work from the machine word } q_{1}0, \\ 0 & \text{otherwise.} \end{cases}$

Problem III.2.24

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

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}

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.2.25

(a)(b)

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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])$ .

Chapter III.3Recursive and Recursively Enumerable Sets[48/81%]

Problem III.3.1

(a)(b)(c)(d)(e)(f)(g)(h)

Prove that the following predicates are primitive recursive:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$x = y$ ;

(b)

$x + y = z$ ;

(c)

$x \cdot y = z$ ;

(d)

$x$ divides $y$ ;

(e)

$x$ is even;

(f)

$x$ and $y$ are relatively prime;

(g)

$\exists n(x = 1^{2} + 2^{2} + \ldots + n^{2})$ ;

(h)

$\exists n(x = 1 + 2 + \ldots + n)$ .

Problem III.3.2

(a)(b)(c)(d)(e)(f)

Prove that if $P(x_{1}, \ldots , x_{n})$ and $Q(x_{1}, \ldots , x_{n})$ are recursive (primitive recursive) predicates, then the following predicates are also recursive (primitive recursive):

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$(P(x_{1}, \ldots , x_{n})\ \& \ Q(x_{1}, \ldots , x_{n}))$ ;

(b)

$(P(x_{1}, \ldots , x_{n}) \lor Q(x_{1}, \ldots , x_{n}))$ ;

(c)

$\neg P(x_{1}, \ldots , x_{n})$ ;

(d)

$(P(x_{1}, \ldots , x_{n}) \supset Q(x_{1}, \ldots , x_{n}))$ ;

(e)

$P(x_{1}, x_{1}, x_{3}, \ldots , x_{n})$ ;

(f)

$P(f(x_{1}, \ldots , x_{m}), x_{m+1}, \ldots , x_{m+n-1})$ , if $f(x_{1}, \ldots , x_{m})$ is g.r. (p.r.).

Problem III.3.3

Prove that if the predicate $R(x_{1}, \ldots , x_{n}, y)$ is recursive (primitive recursive), then the predicates $\exists y (y \leq z\ \& \ R(x_{1}, \ldots , x_{n}, y))$ and $\forall y (y \leq z \supset R(x_{1}, \ldots , x_{n}, y))$ are also recursive (primitive recursive).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.4

Prove that if the predicate $R(x_{1}, \ldots , x_{n}, y, z)$ is primitive recursive, then $M = \left\{ \langle x_{1}, \ldots , x_{n} \rangle \mid \exists y \exists z\, R(x_{1}, \ldots , x_{n}, y, z)\right\}$ is a recursively enumerable set.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.5

Prove that there exists a set that is not recursively enumerable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.6

Prove that any finite set of natural numbers is primitive recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.7

Prove that a set of $n$ -tuples is recursive (primitive recursive) if and only if its characteristic function is general recursive (primitive recursive).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.8

Prove that if $f$ is a general recursive (primitive recursive) function and $a$ is a fixed number, then the set of solutions of the equation $f(x_{1}, \ldots , x_{n}) = a$ is recursive (primitive recursive).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.9

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.10

Prove that if the sets $A$ and $B$ are recursive (primitive recursive), then the sets $A \cap B$ , $A \cup B$ , $\mathbb {N} \setminus A$ are also recursive (primitive recursive).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.11

Prove that if the sets $A$ and $B$ are recursively enumerable, then the sets $A \cap B$ and $A \cup B$ are recursively enumerable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.12

Prove that every primitive recursive set is recursively enumerable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.13

(a)(b)

Let the sets $A$ and $B$ differ by finitely many elements. Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $A$ is recursive, then $B$ is recursive;

(b)

if $A$ is recursively enumerable, then $B$ is recursively enumerable.

Problem III.3.14

Prove that if a set $A$ and its complement $\mathbb {N} \setminus A$ are recursively enumerable, then $A$ is recursive (Post's theorem).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.15

(a)(b)(c)

Let $M \subseteq \mathbb {N}^{n}$ . Set

c^{n}(M) = \left\{ c^{n}(x_{1}, \ldots , x_{n}) \mid \langle x_{1}, \ldots , x_{n} \rangle \in M\right\} ,

where $c^{n}$ is defined in problem III.1.14. Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$M$ is primitive recursive if and only if $c^{n}(M)$ is primitive recursive;

(b)

$M$ is recursive if and only if $c^{n}(M)$ is recursive;

(c)

$M$ is recursively enumerable if and only if $c^{n}(M)$ is recursively enumerable.

Problem III.3.16

Let $M \subseteq \mathbb {N}$ be a nonempty set. Prove that $M$ is recursively enumerable if and only if there is a primitive recursive function $\alpha (x)$ such that $M = \left\{ \alpha (x) \mid x \in \mathbb {N}\right\}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.17

Let $M$ be a nonempty set of $n$ -tuples. Prove that the set $M$ is recursively enumerable if and only if there are one-place primitive recursive functions $\alpha_{1}, \ldots , \alpha_{n}$ such that

M = \left\{ \langle \alpha _{1}(x), \ldots , \alpha _{n}(x) \rangle \mid x \in \mathbb {N}\right\} .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.18

Let the general recursive function $f(x)$ satisfy the condition: $f(x) \geq x$ for all $x \in \mathbb {N}$ . Prove that the range of values $\rho_{f}$ of the function $f$ is recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.19

Prove that an infinite set $A$ is recursive if and only if $A$ is the range of values of a strictly increasing general recursive function.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.20

Prove that a nonempty set $A$ is recursive if and only if $A$ is the range of values of a monotonically (not necessarily strictly) increasing general recursive function.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.21

Prove that every infinite recursively enumerable set contains an infinite recursive subset.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.22

Prove that every infinite recursively enumerable set can be represented as $A = \rho_{f}$ for some 1--1 general recursive function $f$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.23

Prove that the graph of a general recursive function is recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.24

Prove that if the graph $\Gamma_{f}$ of a function $f$ is recursively enumerable, then the function $f$ is partial recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.25

Prove that the full preimage of a recursive set under a general recursive function is recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.26

Let $A$ be a recursive set, $f$ a general recursive function with $\rho_{f} = \mathbb {N}$ , $f(A) \cap f(\mathbb {N} \setminus A) = \emptyset$ . Prove that $f(A)$ is recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.27

Let $A, B$ be recursively enumerable sets, and $C$ a recursive set such that $A \cap B = \emptyset$ , $A \subseteq C \subseteq A \cup B$ . Prove that $A$ is recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.28

Let $f, g$ be general recursive functions, with $g$ a 1--1 function. Suppose also that $f(x) \geq g(x)$ for all $x$ . Prove that if $\rho_{g}$ is recursive, then $\rho_{f}$ is recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.29

Let $A, B$ be recursively enumerable sets. Prove that there exist recursively enumerable sets $A_{1} \subseteq A$ , $B_{1} \subseteq B$ such that $A_{1} \cap B_{1} = \emptyset$ , $A_{1} \cup B_{1} = A \cup B$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.30

(a)(b)(c)(d)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

a function obtained by means of superposition from functions with recursively enumerable graph has recursively enumerable graph;

(b)

a function obtained by means of the primitive recursion scheme from functions with recursively enumerable graph has recursively enumerable graph;

(c)

a function obtained by means of the $\mu$ -operator from a function with recursively enumerable graph has recursively enumerable graph;

(d)

the graph of any partial recursive function is recursively enumerable.

Problem III.3.31

Prove that a function is partial recursive if and only if its graph is recursively enumerable (the graph theorem).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.32

Prove that the domain of definition of a partial recursive function is a recursively enumerable set.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.33

Prove that the range of values of a partial recursive function is recursively enumerable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.34

Prove that any recursive set is recursively enumerable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.35

Prove that a set of $n$ -tuples is recursively enumerable if and only if its partial characteristic function is partial recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.36

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

the image of a recursively enumerable set under a partial recursive function is recursively enumerable;

(b)

the full preimage of a recursively enumerable set under a partial recursive function is recursively enumerable.

Problem III.3.37

Prove that the set $A$ of solutions of the equation

f(x_{1}, \ldots , x_{n}) = a

is recursively enumerable, if $f$ is a partial recursive $n$ -ary function.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.38

Prove that if $f^{n+1}$ is a partial recursive function, then the set $M = \left\{ \langle x_{1}, \ldots , x_{n} \rangle \mid \exists y\, f(x_{1}, \ldots , x_{n}, y) = 0\right\}$ is recursively enumerable.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.39

Let $M_{1}, \ldots , M_{k}$ be pairwise disjoint recursively enumerable sets of $n$ -tuples, $f_{1}, \ldots , f_{n}$ partial recursive functions. Prove that $g(x_{1}, \ldots , x_{n})$ , defined as follows:

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.40

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

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

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.41

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

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(x_{1}, \ldots , x_{n}, t)$ if and only if the graph of the function $f(x_{1}, \ldots , x_{n})$ is primitive recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.42

Let $F(x,y)$ be defined by means of recursion on two variables:

\begin{cases} F(0,y) = \varphi (y), \\ F(x+1,0) = \psi (x, F(x, \alpha (x)), F(x, F(x, \gamma (x)))), \\ F(x+1,y+1) = \tau (x,y,F(x,F(x+1,y))). \end{cases}

Prove that if the functions $\varphi , \psi , \alpha , \gamma , \tau$ are general recursive, then the function $F$ is general recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.43

Prove that the set

H = \left\{ x \mid \exists y\, T_{1}(x,x,y) = 0\right\} ,

where $T_{1}$ is the function from problem III.2.25, is recursively enumerable but not recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.44

Prove that if the domain of definition of a partial recursive function $f^{n}$ is a recursive set, then $f^{n}$ has a recursive extension.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.45

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.46

Find a partial recursive function $f(x)$ that has no general recursive extension.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.47

Find a partial recursive function $f(x)$ not representable in the form

f(x) = \mu y \left[g(x,y) = 0\right]

for any general recursive function $g$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.3.48

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.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Chapter III.4Kleene and Post Numberings[43/91%]

Problem III.4.1

(a)(b)(c)(d)(e)(f)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$[x,y]$ is a bijection between $\mathbb {N}^{2}$ and $\mathbb {N}$ ;

(b)

$[x_{1}, \ldots , x_{n}]$ is a bijection between $\mathbb {N}^{n}$ and $\mathbb {N}$ ;

(c)

$[[x]_{1}^{2}, [x]_{2}^{2}] = x$ , $[[x,y]]_{1}^{2} = x$ , $[[x,y]]_{2}^{2} = y$ ;

(d)

$[[x]_{1}^{n}, \ldots , [x]_{n}^{n}] = x$ , $[[x_{1}, \ldots , x_{n}]]_{i}^{n} = x_{i}$ ;

(e)

$[x_{1}, \ldots , x_{m}, x_{m+1}, \ldots , x_{n}] = [[x_{1}, \ldots , x_{m}], x_{m+1}, \ldots , x_{n}]$ ;

(f)

$c(x_{0}, c(x_{1}, x_{2})) = [c(x_{0}, x_{1}), x_{2}]$ .

Problem III.4.2

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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

(a)(b)

Prove that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.5

(a)(b)(c)(d)

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:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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.6

(a)(b)

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(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

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.8

(a)(b)(c)

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

by means of superposition;

(b)

by means of primitive recursion;

(c)

by means of the $\mu$ -operator.

Problem III.4.9

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

\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}

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.10

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

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

\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)$ there is a natural number $a$ such that

\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.11

Prove that for any partial recursive function $f(x,y)$ there is a number $n$ such that $f(n,y) = \kappa_{n}(y)$ for all $y$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.12

(a)(b)

Prove that there is a number $n$ such that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\kappa_{n}(0) = n$ ;

(b)

$\kappa_{n}(n) = n$ .

Problem III.4.13

Prove that there is a primitive recursive function $f$ such that for any $x$ , if $\kappa_{x}$ is a general recursive function, then

\kappa _{\kappa _{x}(f(x))} = \kappa _{f(x)}.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.14

(a)(b)(c)

Construct partial recursive functions $\kappa_{a}$ such that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\kappa_{a} = \chi_{\left\{ a\right\} }$ ;

(b)

$\kappa_{a} = \chi_{\left\{ a\right\} }^{*}$ ;

(c)

$\kappa_{a} = \chi_{\mathbb {N} - \left\{ a\right\} }^{*}$ .

Problem III.4.15

Let $\mathcal{F}$ be the family of all one-place partial functions. We call a map $F: \mathcal{F} \to \mathcal{F}$ an effective operator, if the function $g(n,x) = (F(\kappa_{n}))(x)$ is partial recursive. Prove that for any effective operator $F$ there is a partial recursive function $f$ such that $f = F(f)$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.16

(a)(b)

Prove that for any partial recursive functions $\alpha , \gamma , \delta$ there is a partial recursive function $f$ satisfying the conditions:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

if $\alpha (x) = 0$ , then $f(x) = 0$ ;

(b)

if $\alpha (x) > 0$ , then $f(x) = \gamma (f(\delta (x)))$ .

Problem III.4.17

Let $\mathcal{A}$ be a nonempty family of one-place partial recursive functions, distinct from the family of all such functions. Prove that the set

\kappa ^{-1}(\mathcal{A}) = \left\{ x \mid \kappa _{x} \in \mathcal{A}\right\}

is not recursive (Rice's theorem).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.18

(a)(b)(c)(d)(e)

Prove that the following sets are not recursive:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$A_{1} = \left\{ x \mid \kappa_{x} \text{ is a constant}\right\}$ ;

(b)

$A_{2} = \left\{ x \mid \kappa_{x}(a) = b\right\}$ , where $a, b$ are fixed numbers;

(c)

$A_{3} = \left\{ c(x,y) \mid y \in \delta_{\kappa_{x}}\right\}$ ;

(d)

$A_{4} = \left\{ c(x,y) \mid y \in \rho_{\kappa_{x}}\right\}$ ;

(e)

$A_{5} = \left\{ c(x,y) \mid \kappa_{x} = \kappa_{y}\right\}$ .

Problem III.4.19

(a)(b)(c)

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

functions defined at the point $0$ ;

(b)

functions $f$ such that $f(a) = b$ for given numbers $a$ and $b$ ;

(c)

functions with nonempty domain of definition.

Problem III.4.20

Prove that every recursively enumerable set has infinitely many Post numbers.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.21

Let $\mathcal{A}$ be a nonempty family of recursively enumerable sets, distinct from the family of all recursively enumerable sets. Prove that the set

\pi ^{-1}(\mathcal{A}) = \left\{ x \mid \pi _{x} \in \mathcal{A}\right\}

is not recursive (Rice's theorem).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.22

(a)(b)(c)(d)(e)

Prove that the following sets are not recursive:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\left\{ x \mid \pi_{x} \neq \emptyset \right\}$ ;

(b)

$\left\{ x \mid \pi_{x} = \mathbb {N}\right\}$ ;

(c)

$\left\{ x \mid a \in \pi_{x}\right\}$ , where $a$ is a fixed number;

(d)

$\left\{ x \mid \pi_{x} \text{ is finite}\right\}$ ;

(e)

$\left\{ c(x,y) \mid \pi_{x} = \pi_{y}\right\}$ .

Problem III.4.23

(a)(b)

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

those containing a given number $a$ ;

(b)

the nonempty ones.

Problem III.4.24

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

\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}

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.25

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

\langle x_{0}, x_{1}, \ldots , x_{n} \rangle \in P \Leftrightarrow x_{0} \in \pi _{\alpha (x_{1}, \ldots , x_{n})}.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.26

(a)(b)(c)(d)(e)(f)

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

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

(b)

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

(c)

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

(d)

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

(e)

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

(f)

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

Problem III.4.27

(a)(b)

Prove that there exist primitive recursive functions $f$ and $g$ such that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\delta_{\kappa_{x}} = \rho_{\kappa_{f(x)}}$ ;

(b)

$\rho_{\kappa_{x}} = \delta_{\kappa_{g(x)}}$ .

Problem III.4.28

(a)(b)

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

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

\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 $f$ there is a number $a$ such that

\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

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

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

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.30

(a)(b)(c)

Prove that there is a number $n$ such that:

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

(a)

$\pi_{n} = \left\{ n\right\}$ ;

(b)

$\pi_{n} = \left\{ n^{2}\right\}$ ;

(c)

$\pi_{n} = \mathbb {N} \setminus \left\{ n\right\}$ .

Problem III.4.31

Prove that the relation $\leq_{m}$ is reflexive and transitive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.32

Prove that every recursive set is $m$ -reducible to any nonempty set with nonempty complement.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.33

Prove that if $A$ is $m$ -reducible to a recursive (recursively enumerable) set, then $A$ is recursive (recursively enumerable).

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.34

Prove that the set

K_{1} = \left\{ c(x,y) \mid x \in \pi _{y}\right\}

is $m$ -universal.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.35

Prove that every $m$ -universal set is not recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.36

Prove that the set

K = \left\{ x \mid x \in \pi _{x}\right\}

is creative.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.37

Prove that every creative set is not recursive.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.38

Prove that if $A$ is a creative set, $A \leq_{m} B$ , and $B$ is recursively enumerable, then $B$ is creative.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.39

Prove that every creative set is $m$ -universal.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.40

Prove that a set is $m$ -universal if and only if it is creative.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.41

Prove that the set

K_{2} = \left\{ x \mid \pi _{x} \neq \emptyset \right\}

is creative.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.42

Prove that there is a primitive recursive function $\sigma (x)$ such that the Turing machine with number $\sigma (x)$ computes the function $\kappa_{x}$ .

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source

Problem III.4.43

Prove that the set $H$ from problem III.3.43 of 3 is creative.

Origin: AI-translated from another node content of the same node

Generated from: Stated according to the original source