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

циклическая перестановка букв: $f(x w)=w x, x \in \Sigma$;

циклическая перестановка слов: $f\left(w_{1}, \ldots , w_{n}\right)=\left(w_{2}, \ldots , w_{n}, w_{1}\right)$;

«переворачивание» последовательности слов: $f\left(w_{1}, \ldots , w_{n}\right)=\left(w_{n}, \ldots , w_{1}\right)$;

удвоение каждой буквы: $f\left(x_{1} \ldots x_{n}\right)=x_{1} x_{1} \ldots x_{n} x_{n}$;

нахождение образа при гомоморфизме $\varphi : \varphi (a)=a, \varphi (b)=c b, \varphi (c)=\varepsilon$;

удаление всех одиночных букв $a$, стоящих на чётных позициях;

проверка, содержат ли два слова одно и то же количество букв $a$ (результат равен 1, если ответ «да», 0, если «нет»);

проверка, является ли слово палиндромом (то есть симметричным);

проверка, есть ли в слове две последовательности букв $a$ одной и той же длины;

проверка, образуют ли в слове количества букв $a, b$ и $c$ возрастающую арифметическую прогрессию.

$x+y$;

$\lfloor x-y\rfloor$

$x y$

сравнение $x<y$;

возведение в степень: $x^{y}$;

квадратный корень: $\lfloor \sqrt{x}\rfloor$;

логарифм: $\left\lfloor \log_{2} x\right\rfloor ;$

деление нацело: $\lfloor x / y\rfloor$;

остаток: $x \bmod y$;

функция выбора $m$-го аргумента: $\mathrm{id}_{m}, m$ — заранее заданная константа.

машины $\mathfrak {M}_{1} ; \ldots ; \mathfrak {M}_{n}$, вычисляющей функцию $g_{1}(x)=f_{n}\left(\ldots f_{1}(x) \ldots \right)$;

машины $\operatorname {par}\left(a, \mathfrak {M}_{1}, \ldots , \mathfrak {M}_{n}\right)$, вычисляющей функцию

машины $\operatorname {if}\left(\mathfrak {M}_{1}, \mathfrak {M}_{2}, \mathfrak {M}_{3}\right)$, вычисляющей функцию

машины $\operatorname {while}\left(\mathfrak {M}_{1}, \mathfrak {M}_{2}\right)$, вычисляющей функцию $g_{4}(x)=x_{q}$, где $q$ — наименьшее натуральное число, для которого $\mathfrak {M}_{1}\left(x_{q}\right)$ пусто, при этом $x_{0}=x$ и $x_{j+1}=\mathfrak {M}_{2}\left(x_{j}\right)$. Считать, что $\left|x_{j}\right| \leqslant L(x)$ и $t_{i}\left(x_{j}\right) \leqslant T_{i}(x)$.

$f_{1}(x, y)= \begin{cases} x^{2} y^{3}, & \text{ если } x<y, \\ \lfloor (x+y) / 2\rfloor , & \text{ в противном случае; }\end{cases}$

$f_{2}(x, y)= \begin{cases} \lfloor \sqrt{x}\rfloor , & \text{ если } x+1 \geqslant y, \\ 2(x+y), & \text{ в противном случае; }\end{cases}$

$f_{3}(x, y)= \begin{cases} \left\lfloor \log_{2}(1+\lfloor x / y\rfloor )\right\rfloor , & \text{ если } x>2 y, \\ x y, & \text{ в противном случае; }\end{cases}$

$f_{4}(x, y)= \begin{cases} \lfloor \sqrt{x}\rfloor , & \text{ если } 2 x \geqslant y, \\ x \bmod y, & \text{ в противном случае. }\end{cases}$

$q, a \rightarrow p, b$, return — возврат головки в ту из соседних ячеек, из которой она пришла в текущую;

$q, a \rightarrow p, b$, zero — возврат головки в нулевую ячейку;

$q, a \rightarrow p, b$, mirror — сдвиг головку в ячейку $-i$, если она была в ячейке с номером $i$;

$q, a \rightarrow p, b$, double — сдвиг головку в ячейку $2 i$, если она была в ячейке с номером $i$;

$q, a \rightarrow p, b$, next — сдвиг головки в ближайшую справа к текущей ячейку, содержащую $a$ (если она есть, иначе головка остаётся на месте);

$q, a \rightarrow p, \operatorname {insert} b$ — сдвиг текущей и всех ячеек справа от неё на одну позицию вправо и запись символа $b$ в освободившуюся ячейку, головка оказывается в новой ячейке;

$q, a \rightarrow p$, restore, $s$ — замена символа $a$ на тот, который находился в ячейке в начальной конфигурации.