Turing Machines

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

Let the machine $T$ have the following program:

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

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

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

Construct the following Turing machines:

1. Zero transfer: $q_{1}001^{x}0 \mid \Rightarrow_{A} q_{0}01^{x}00$.

2. Right shift: $q_{1}001^{x}0 \mid \Rightarrow_{B^{+}} 01^{x}q_{0}0$.

3. Left shift: $01^{x}q_{1}0 \mid \Rightarrow_{B^{-}} q_{0}01^{x}0$.

4. Transposition: $01^{x}q_{1}01^{y}0 \mid \Rightarrow_{C} 01^{y}q_{0}01^{x}0$.

5. Doubling: $q_{1}01^{x}0 \Rightarrow_{D} q_{0}01^{x}01^{x}0$.

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

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

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

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

Prove that:

Prove that every partial recursive function is correctly Turing computable.

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

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

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

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}')$.

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}')$.

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

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

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

Prove that every Turing computable function is partial recursive.

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.

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

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.

Prove that the following functions are not partial recursive:

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

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