Машины Тьюринга

Какую функцию $f(x)$ вычисляет машина $T$ со следующей программой команд:

Пусть машина $T$ имеет следующую программу:

Какие функции $f_{1}(x), f_{2}(x_{1}, x_{2}), \ldots , f_{n}(x_{1}, \ldots , x_{n}), \ldots$ вычисляет эта машина?

Построить машину Тьюринга, которая правильно вычисляет функцию $f(x) = x+1$.

Построить машину Тьюринга, которая правильно вычисляет функцию $o(x) = 0$.

Построить следующие машины Тьюринга:

1. Перенос нуля: $q_{1}001^{x}0 \mid \Rightarrow_{А} q_{0}01^{x}00$.

2. Правый сдвиг: $q_{1}001^{x}0 \mid \Rightarrow_{Б^{+}} 01^{x}q_{0}0$.

3. Левый сдвиг: $01^{x}q_{1}0 \mid \Rightarrow_{Б^{-}} q_{0}01^{x}0$.

4. Транспозиция: $01^{x}q_{1}01^{y}0 \mid \Rightarrow_{В} 01^{y}q_{0}01^{x}0$.

5. Удвоение: $q_{1}01^{x}0 \Rightarrow_{Г} q_{0}01^{x}01^{x}0$.

6. Циклический сдвиг: $q_{1}01^{x_{1}}01^{x_{2}}\ldots 01^{x_{n}}0 \mid \Rightarrow_{\text{Ц}_{n}} q_{0}01^{x_{2}}\ldots 01^{x_{n}}01^{x_{1}}0$.

7. Копирование: $q_{1}01^{x_{1}}\ldots 01^{x_{n}}0 \Rightarrow_{\text{К}_{n}} q_{0}01^{x_{1}}\ldots 01^{x_{n}}01^{x_{1}}\ldots 01^{x_{n}}0$.

Построить машину Тьюринга, которая правильно вычисляет функцию $I_{m}^{n}(x_{1}, \ldots , x_{n})$ (где $1 \leq m \leq n$).

Построить машину Тьюринга для правильного вычисления функций:

Доказать, что:

Доказать, что любая частично рекурсивная функция правильно вычислима по Тьюрингу.

Доказать, что существуют примитивно рекурсивные функции $\alpha , \beta , \gamma$ такие, что:

Построить примитивно рекурсивные функции $\gamma^{n}(x_{1}, \ldots , x_{n})$ такие, что

Построить примитивно рекурсивную функцию $\rho (s, k, l, u, \nu )$ удовлетворяющую условию: если $u = k_{l}(A)$, $\nu = k_{r}(B)$, $0 \leq s \leq 2$, то $\rho (s, k, l, u, \nu ) = \nu ((Aq_{i}a_{j}B)_{T}')$, где $T(i,j)$ есть $q_{i}a_{j} \to q_{k}a_{l}$ при $s=0$, $q_{i}a_{j} \to q_{k}a_{l}L$ при $s=1$, $q_{i}a_{j} \to q_{k}a_{l}R$ при $s=2$.

Построить примитивно рекурсивную функцию $\sigma (t, i, j, u, \nu )$, удовлетворяющую условию: если $u = k_{l}(A)$, $\nu = k_{r}(B)$, $t = \lambda (T)$, $q_{i}$ входит в алфавит внутренних состояний, а $a_{j}$ --- во внешний алфавит машины $T$, то $\sigma (t, i, j, u, \nu ) = \nu ((Aq_{i}a_{j}B)_{T}')$.

Построить примитивно рекурсивную функцию $\tau (t, x)$, удовлетворяющую условию: если $t = \lambda (T)$, $x = \nu (M)$, где $M = Aq_{i}a_{j}B$ --- машинное слово в алфавите машины $T$, то $\tau (t,x) = \nu (M_{T}')$.

Построить примитивно рекурсивную функцию $w(t, x, y)$, удовлетворяющую условию: если $t = \lambda (T)$, $x = \nu (M)$, где $M$ --- машинное слово в алфавите машины $T$, то $w(t, x, y) = \nu (M_{T}^{(y)})$.

Построить примитивно рекурсивную функцию $\varepsilon (x)$, удовлетворяющую условию: если $x = \nu (M)$, то $\varepsilon (x)$ есть число вхождений символа $a_{1}$ в слово $M$.

Доказать, что если машина $T$ вычисляет $f(x_{1}, \ldots , x_{n})$ и $t_{0} = \lambda (T)$, то:

Доказать, что любая вычислимая по Тьюрингу функция частично рекурсивна.

Доказать, что функция вычислима по Тьюрингу тогда и только тогда, когда существует машина Тьюринга с внешним алфавитом $\left\{ 0,1\right\}$, вычисляющая эту функцию.

Доказать, что существует двуместная частично рекурсивная функция $U(t, x)$, универсальная для семейства всех одноместных частично рекурсивных функций.

Доказать, что существует $(n+1)$-местная частично рекурсивная функция $U^{n+1}(t, x_{1}, \ldots , x_{n})$, универсальная для семейства всех $n$-местных частично рекурсивных функций.

Доказать, что следующие функции не являются частично рекурсивными:

Доказать, что существует примитивно рекурсивная функция $S(z, x, y, w)$ такая, что

Доказать, что существуют примитивно рекурсивные функции $p, T_{1}, T_{2}, \ldots$ такие, что: