Closure properties of general and partial recursive functions

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

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

is also partial recursive.

Show that the following functions are partial recursive:

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.

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.

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

is general recursive.

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.

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$

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

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

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:

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$:

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$

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$

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$

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$

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

is general recursive. $\circledast$

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

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

Design a multi-tape Turing machine that "adds" two strings over $\Sigma = \left\{ 1,2, \ldots , X\right\}$; that is, on inputs $x, y \in \Sigma^{*}$, compute $z \in \Sigma^{*}$ such that $\iota_{\Sigma }^{-1}(z)=\iota_{\Sigma }^{-1}(x)+\iota_{\Sigma }^{-1}(y)$.

Complete the proof of the primitive recursion part of Theorem 4.47. That is, given multi-tape DTM's $M_{g}$ and $M_{h}$ computing functions $g$ and $h$, design a multi-tape DTM $M$ that computes the function $f$ which is defined from functions $g$ and $h$ by primitive recursion.

Prove that every partial recursive function can be obtained from initial functions with a finite number of applications of composition and primitive recursion operations and a single application of unbounded minimization operation.

Let $f(k, 0)=\left\lfloor e^{k}\right\rfloor$, and $f(k, n)=$ the $n$th digit to the right of the decimal point of the decimal expansion of $e^{k}$, where $e=\sum_{n=0}^{\infty } 1 / n!$. Show that $f$ is a recursive function. Is $f$ a primitive recursive function?

For any partial recursive function $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$, we write $D_{f}$ to denote its domain $\left\{ x \mid f(x) \downarrow \right\}$. Let $f, g, h: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ be three partial recursive functions.

Define

Is $f$ a partial recursive function? Prove your answer.

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

Prove that the following functions are partial recursive:

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:

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:

is partial recursive.

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

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