Math Problems Vault

Problem 558

Let three functions be given: $f(x, y, z)=x y+z, g(x, y)=2 x+y$ , $h(x)=2 x^{2}$ . Determine the function $F^{(2)}$ defined as follows: $f\left(h\left(\operatorname {id}_{1}^{2}\right), g\left(h\left(\operatorname {id}_{2}^{2}\right), \operatorname {id}_{2}^{2}\right), \operatorname {id}_{2}^{2}\right)$ ? $\circledast$

?

Problem 559

(a)(b)(c)

Determine the value of the following p.r.f.'s (partial recursive functions):

?

(a)

$f=\operatorname {Pr}\left[0, s\left(\operatorname {id}_{1}^{2}+\operatorname {id}_{1}^{2}\right)+\operatorname {id}_{2}^{2}\right]$ ;

(b)

$f=\operatorname {Pr}\left[0, s\left(\operatorname {id}_{1}^{2}\right)+s\left(\operatorname {id}_{1}^{2}\right)+\operatorname {id}_{2}^{2}\right]$ ;

(c)

$f=\operatorname {Pr}\left[0, s\left(3 \cdot \operatorname {id}_{1}^{2} \cdot s\left(\operatorname {id}_{1}^{2}\right)\right)+\operatorname {id}_{2}^{2}\right]$ . $\circledast$

Problem 560

The g.r.f. (general recursive function) $f(x)$ is given as follows:

\operatorname {Pr}\left[0, s\left(\operatorname {id}_{1}^{2}\right)+s\left(\operatorname {id}_{1}^{2}\right)+\operatorname {id}_{1}^{2}+\operatorname {id}_{1}^{2}+\operatorname {id}_{2}^{2}+\operatorname {id}_{2}^{2}\right].

Prove that $f(x)=3 \cdot 2^{x+1}-4 x-6$ . $\circledast$

?

Problem 561

(a)(b)(c)

Find the value $F(5)$ for the following functions:

?

(a)

$F=\operatorname {Pr}[1, h]$ , where $h(y, z)=\left\lfloor 2^{z} / z^{2}\right\rfloor$ ;

(b)

$F=\operatorname {Pr}[1, h]$ , where $h(y, z)=\left\lfloor 2^{z} / z\right\rfloor$ ;

(c)

$F=\operatorname {Pr}[2, h]$ , where $h(y, z)=3 z \div (2 y+1)$ . $\circledast$

Problem 562

Show that the following functions are g.r.f.'s:

?

(a)

$\operatorname {pow}(x, y)=x^{y}$ — exponentiation;

(b)

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

(c)

$\operatorname {if}(x, y, z)$ — the conditional operation,

\operatorname {if}(x, y, z)= \begin{cases} y, & \text{ if } x \neq 0 \\ z, & \text{ otherwise }\end{cases}

(d)

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

(e)

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

(f)

$\operatorname {diff}=\left|x-y\right|$ — the absolute difference;

(g)

$\bmod (x, y)$ — the remainder of dividing $x$ by $y$ ;

(h)

$\operatorname {div}(x, y)=\lfloor x / y\rfloor$ — integer quotient. $\circledast$

Problem 563

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

?

Problem 564

We say that the function $h^{(n+1)}$ is obtained by bounded minimization of the function $f^{(n+1)}$ (denoted $h=\mu_{\lim } f$ ), if $h(\bar{x}, y)=y$ , when $f(\bar{x}, y) \neq 0$ for all $z<y$ , and otherwise $h(\bar{x}, y)$ equals the smallest $z<y$ for which $f(\bar{x}, z)=0$ . Prove that the function $\mu_{\lim } f$ can be constructed from $f$ and the basis functions by means of superposition and primitive recursion. $\circledast$

?

Problem 565

Let $g\left(x_{1}, \ldots , x_{n-1}, x_{n}\right)$ be a p.r.f., 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 a p.r.f. $\circledast$

?

Problem 566

Find the value $F(9)$ and $F(17)$ for $F=\mu f$ and the following functions $f^{(2)}$ . Determine for which of them $F(x)=\lfloor \sqrt{x}\rfloor$ holds:

?

(a)

$f(x, y)=y^{2} \div x$ ;

(b)

$f(x, y)=x \div y^{2}$ ;

(c)

$f(x, y)=(x+1) \div y^{2}$ ;

(d)

$f(x, y)=(x+1) \div (y+1)^{2}$ ;

(e)

$f(x, y)=x \div (y+1)^{2}$ . $\circledast$

Problem 567

Determine for which of the following functions $f^{(3)}$ we have $F(x)=\lfloor y / x\rfloor$ , where $F=\mu f$ and $x \neq 0$ :

?

(a)

$f(x, y, i)=y \div i x$ ;

(b)

$f(x, y, i)=y \div (i+1) x$ ;

(c)

$f(x, y, i)=(y+1) \div i x$ ;

(d)

$f(x, y, i)=(y+1) \div i(x+1)$ ;

(e)

$f(x, y, i)=(y+1) \div (i+1) x$ . $\circledast$

Problem 568

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

Which of the following expressions define the number $\tau (x)$ of distinct divisors of $x$ ?

?

(a)

$x-\sum_{i<x} \operatorname {test}(\bmod (x, s(i)))$ ;

(b)

$x-\sum_{i<x} \operatorname {not}(\bmod (x, s(i)))$ ;

(c)

$\sum_{i<x} \operatorname {test}(\bmod (x, s(i)))$ ;

(d)

$\sum_{i<x} \operatorname {not}(\bmod (x, s(i)))$ . $\circledast$

Problem 569

Show that the following functions are p.r.f.'s:

?

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

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

(d)

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

(e)

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

(f)

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

(g)

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

Problem 570

Determine the p.r.f. $l^{(1)}$ whose value equals $\log_{2} x$ when $x$ is a power of two, and is undefined otherwise. $\circledast$

?

Problem 571

On the Euclidean coordinate plane, a disk $C$ is given, centered at the point $(100,100)$ with radius 50. Prove that the following function $r^{(2)}$ is partially recursive: $r(x, y)$ is defined if and only if the point $(x, y)$ lies outside the disk $C$ , and its value equals the integer part of the distance from $(x, y)$ to the disk (that is, to the point of the disk $C$ closest to $(x, y)$ ). $\circledast$

?

Problem 572

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

?

Problem 573

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

?

Problem 574

Prove that from the constant 0 and the functions $\operatorname {id}_{m}^{n}$ , by means of 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$ . $\circledast$

?

Problem 575

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

?

Problem 576

Let $g\left(x_{1}, \ldots , x_{n}, y\right)$ be a g.r.f. 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{ for } y \leqslant z, \\ 0, & \text{ for } y>z\end{cases}

is general recursive. $\circledast$

?

Problem 577

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

\begin{aligned} & F\left(x_{1}, \ldots , x_{n}\right)=\min \left\{ y: f\left(x_{1}, \ldots , x_{n}, y\right)=0 \text{ or } \\ & \quad g\left(x_{1}, \ldots , x_{n}, y\right)>h\left(x_{1}, \ldots , x_{n}, y\right)\right\} \end{aligned}

is a p.r.f. $\circledast$

?

Problem 578

(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 — by increasing coordinate $x$ . This order looks like this:

\begin{aligned} & (0,0),(0,1),(1,0),(0,2),(1,1),(2,0), \ldots \\ & \quad \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 ,\rangle$ numbers all pairs of natural numbers in a one-to-one fashion.

?

(a)

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

(b)

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

(c)

Show that all these functions are general recursive.

Problem 579

Show that the function $F(x)$ from Problem 547 on p. 168 is a g.r.f.

Hint. First show that the function $g(x)=\langle F(x), F(x+1)\rangle$ is a g.r.f. $\circledast$

?

Problem 580

Another function that allows one to number pairs of natural numbers looks like this: $c(x, y)=2^{x}(2 y+1)-1$ . Prove that $c$ itself and the inverse functions $c_{1}$ and $c_{2}$ to it (that is, $c_{1}(c(x, y))=x$ and $c_{2}(c(x, y))=y$ ) are general recursive. $\circledast$

?

Problem 581

(a)(b)(c)

Given a one-to-one numbering of pairs $k$ (for example, from Problems 578 or 580), one can inductively number ordered $n$ -tuples of arbitrary length:

\begin{aligned} K() & =0 \\ K\left(x_{1}, \ldots , x_{n}, x_{n+1}\right) & =k\left(k\left(k_{1}\left(K\left(x_{1}, \ldots , x_{n}\right)\right), x_{n+1}\right), n+1\right) \end{aligned}

?

(a)

Prove that the function $K$ is one-to-one.

(b)

Prove that the functions $K^{(n)}\left(x_{1}, \ldots , x_{n}\right)$ are general recursive.

(c)

Prove that the inverse function $K^{\prime }$ to $K$ is also general recursive: $\circledast$

K^{\prime }\left(K\left(x_{0}, \ldots , x_{n}\right), m\right)= \begin{cases} x_{m}, & \text{ for } m \leqslant n, \\ 0, & \text{ otherwise. }\end{cases}

Problem 582

(a)(b)(c)

Yet another way of coding finite sequences of natural numbers uses binary notation: the sequence $\left(n_{0}, n_{1}, \ldots , n_{k}\right)$ is coded by the binary number $1^{n_{k}} 01^{n_{k-1}} 0 \ldots 01^{n_{1}} 01^{n_{0}}$ (sequences that arise from one another by adding or removing trailing zeros are not distinguished).

?

(a)

Find the codes of the sequences $(2,3,0,1)$ and $(0,0,2,1,2)$ .

(b)

Determine of which sequences the numbers 169 and 19783 are codes.

(c)

Prove that the function $k(x, y)$ is general recursive. Here $x$ is the code of a sequence, $y$ is the index of an element, and the value of the function equals that element. $\circledast$

Problem 583

(a)(b)(c)

The Ackermann function is defined as follows:

\begin{aligned} A(0, y) & =y+1 \\ A(x+1,0) & =A(x, 1) \\ A(x+1, y+1) & =A(x, A(x+1, y)) \end{aligned}

?

(a)

Find $A(1, y)$ and $A(2, y)$ for all natural $y$ .

(b)

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

(c)

Prove that the Ackermann function is general recursive. Hint. Using the functions $K$ and $K^{\prime }$ (Problem 581 on the facing page), construct sequences $(x_{1}, x_{2}, \ldots , x_{n}, z)$ such that $\circledast$

A(x, y)=A\left(x_{1}, A\left(x_{2}, \ldots , A\left(x_{n}, z\right) \ldots \right)\right).