Math Problems Vault

Problem 289

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

Show that the following functions are general recursive:

?

(a)

$\operatorname {fact}(x)=x!$ — factorial;

(b)

$\min^{(n)}\left(x_{1}, \ldots , x_{n}\right)$ — the smallest of the arguments, $n>0$ ;

(c)

$\max^{(n)}\left(x_{1}, \ldots , x_{n}\right)$ — the largest of the arguments, $n>0$ ;

(d)

diff $=\left|x-y\right|$ — the absolute value of the difference;

Problem 290

Prove that if the function $f\left(x_{1}, \ldots , x_{n}\right)$ is partial recursive, then the function $g\left(x_{1}, \ldots , x_{n}\right)=f\left(x_{i_{1}}, \ldots , x_{i_{n}}\right)$ is also partial recursive for every permutation $\left(i_{1}, \ldots , i_{n}\right)$ of the numbers $1,2, \ldots , n$ .

?

Problem 291

Let $g\left(x_{1}, \ldots , x_{n-1}, x_{n}\right)$ be a partial recursive function, and let $a$ and $b>0$ be natural numbers. Prove that the function

f\left(x_{1}, \ldots , x_{n-1}, x_{n}\right)= \begin{cases} a, & \text{ if } x_{n}<b, \\ g\left(x_{1}, \ldots , x_{n-1}, x_{n}-b\right), & \text{ if } x_{n} \geqslant b \end{cases}

is also partial recursive.

?

Problem 292

Show that the following functions are partial recursive:

?

(a)

$\operatorname {rt}(n, x)=\lfloor \sqrt[n]{x}\rfloor$ — the integer part of the $n$ -th root of $x$ ;

(b)

$\log (i, x)=\left\lfloor \log_{i} x\right\rfloor$ ;

(c)

$\tau (x)$ — the number of distinct divisors of $x$ , $\tau (0)=0$ ;

(d)

$p(x)=1$ , if $x$ is a prime number, and $p(x)=0$ otherwise;

(e)

$\operatorname {pn}(k)$ — the $k$ -th prime number in increasing order, $\operatorname {pn}(0)=2$ ;

(f)

$\sigma (x)$ — the sum of the divisors of $x$ ; take $\sigma (0)=0$ ;

(g)

$\operatorname {digit}(n, m, i)$ — the $i$ -th digit in the base- $m$ representation of $n$ : that is, if $n=\sum_{i=0}^{\infty } a_{i} m^{i}$ , where $0 \leqslant a_{i}<m$ , then $\operatorname {digit}(n, m, i)=a_{i} ;$

(h)

$\gcd (x, y)$ — the greatest common divisor of $x$ and $y$ .

Problem 293

A general recursive function that can be constructed without using minimization is called primitive recursive. Let the functions $g$ and $f$ be primitive recursive, $h=\mu g$ , $h$ — a general recursive function, and let $h$ be majorized by the function $f: h(\bar{x})<f(\bar{x})$ for all $\bar{x}$ . Prove that $h$ is also primitive recursive.

?

Problem 294

Prove that if the values of a general recursive function $f(x)$ are changed on a finite set, then the resulting function $f^{\prime }(x)$ is also general recursive.

?

Problem 295

Prove that from the constant 0 and the functions $\operatorname {id}_{m}^{n}$ , using superposition and primitive recursion, one cannot obtain the function $s(x)=x+1$ or the function $d(x)=2 x$ . Hint. By induction on the construction of the function, prove that for all functions constructed in this way the inequality $f\left(x_{1}, \ldots , x_{n}\right)<2$ holds for arbitrary $x_{1}, \ldots , x_{n}<2$ .

?

Problem 296

Let $f$ be a general recursive function that is one-to-one on $\omega$ . Prove that the inverse function $f^{-1}$ is also general recursive, by explicitly constructing it.

?

Problem 297

Let $g\left(x_{1}, \ldots , x_{n}, y\right)$ be a general recursive function. Prove that the function

f\left(x_{1}, \ldots , x_{n}, y, z\right)= \begin{cases} \sum _{i=0}^{z} g\left(x_{1}, \ldots , x_{n}, y+i\right), & \text{ if } y \leqslant z, \\ 0, & \text{ if } y>z \end{cases}

is general recursive.

?

Problem 298

Prove that if the functions $f\left(x_{1}, \ldots , x_{n}, y\right), g\left(x_{1}, \ldots , x_{n}, y\right)$ and $h\left(x_{1}, \ldots , x_{n}, y\right)$ are general recursive, then the function $F\left(x_{1}, \ldots , x_{n}\right)=\min \left\{ y: f\left(x_{1}, \ldots , x_{n}, y\right)=0 \text{ or } g\left(x_{1}, \ldots , x_{n}, y\right)>h\left(x_{1}, \ldots , x_{n}, y\right)\right\}$ is partial recursive.

?

Problem 299

(a)(b)(c)

Suppose that all pairs $(x, y)$ of natural numbers are ordered by increasing sum $x+y$ , and pairs with the same sum are ordered by increasing coordinate $x$ . This order looks as follows:

\begin{aligned} (0,0),(0,1),(1,0),(0,2) & ,(1,1),(2,0), \ldots \\ & \ldots ,(0, x+y),(1, x+y-1), \ldots ,(x, y), \ldots ,(x+y, 0), \ldots \end{aligned}

Let $\langle x, y\rangle$ be the number of the pair $(x, y)$ in this order (we take the pair $(0,0)$ to have number 0). Then the function $\langle \cdot ,\cdot \rangle$ enumerates all pairs of natural numbers bijectively.

?

(a)

Prove that $\langle x, y\rangle =\frac{(x+y)(x+y+1)}{2}+x$ .

(b)

Find the inverse functions $\left\rangle_{1}\right.$ and $\left\rangle_{2}\right.$ such that the equalities $\langle \langle x, y\rangle \rangle_{1}=x,\langle \langle x, y\rangle \rangle_{2}=y$ hold, and hence $\left\langle \langle z\rangle_{1},\langle z\rangle_{2}\right\rangle =z$ .

(c)

Show that all these functions are general recursive.

Problem 300

Show that the function $F(x)$ from Problem 281 on page 381 is general recursive. Hint. First show that the function $g(x)=\langle F(x), F(x+1)\rangle$ is general recursive.

?

Problem 301

(a)(b)

For the Ackermann function

?

(a)

find $A(1, y)$ and $A(2, y)$ for all natural numbers $y$ ;

(b)

prove that $A(3, y)=2^{y+3}-3$ .