Примеры машин Тьюринга

Покажите, что $A=\left\{ w w^{R} \mid w \in \left\{ 0,1\right\}^{*}\right\}$ является тьюринг-допустимым языком.

Покажите, что следующая функция является тьюринг-вычислимой:

Покажите, что $\left\{ w w^{R} \mid w \in \left\{ 0,1\right\}^{*}\right\}$ является тьюринг-разрешимым языком.

Покажите, что функция $\pi_{2}^{2}\left(n_{1}, n_{2}\right)=n_{2}$ при $n_{1}, n_{2} \in \mathbf{N}$ является тьюринг-вычислимой.

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

Покажите, что при $1 \leq i \leq k$ функция $\pi_{i}^{k}\left(x_{1}, x_{2}, \cdots , x_{k}\right)=x_{i}$ на натуральных числах является тьюринг-вычислимой.

Покажите, что при любом $1 \leq i \leq k+1$ функция

на строках над алфавитом $\left\{ a, b\right\}$ является тьюринг-вычислимой.

Для каждой из следующих ДМТ проследите работу машины и покажите вычисление на заданных входах:

Постройте ДМТ для процедур $R$ и $T$ из примера 4.9.

Постройте ДМТ, разрешающие следующие языки:

Постройте ДМТ, вычисляющие следующие функции:

Для произвольной заданной ДМТ $M$ постройте новую ДМТ $M^{\prime }$ такую, что $M^{\prime }$ допускает в точности то же множество строк, что и $M$ (то есть $L(M)=L\left(M^{\prime }\right)$), но когда $M^{\prime }$ останавливается, её лента всегда пуста (то есть финальная конфигурация всегда равна $(h, \mathrm{BB})$).

Рассмотрим регулярный язык $L=\left\{ 0^{n_{1}} 10^{n_{2}} 1 \cdots 10^{n_{k}} \mid k \geq 5\text{, }n_{1}, \ldots , n_{k} \geq 0, n_{j} \equiv n_{j+1}(\bmod 5)\text{, где }j=(k \bmod 5)+1\right\}$.

В доказательстве теоремы 4.10 мы заметили, что если ДМТ $M$ в ходе вычисления на входе $x$ посещает некоторые пустые ячейки справа от входного слова, то НКА $M^{\prime }$ после считывания всех символов входного слова должен переходить в другие состояния с помощью $\varepsilon$-переходов, чтобы решить, допускает ли он входное слово. Покажите, что в этом нет необходимости. То есть можно исключить все $\varepsilon$-переходы в $\delta^{\prime }$ и изменить множество $F$ финальных состояний так, чтобы оно включало все последовательности пересечений $S$, содержащие $\langle h, R\rangle$ в качестве последней пары, такие что $S \stackrel{\mathrm{~ B}}{\rightleftharpoons } S_{1} \stackrel{\mathrm{~ B}}{\rightleftharpoons } S_{2} \stackrel{\mathrm{~ B}}{\rightleftharpoons } \ldots \stackrel{\mathrm{~ B}}{\rightleftharpoons }(\langle h, R\rangle )$. Объясните, как определить итоговое множество $F$.

Рассмотрим расширение ДМТ только для чтения. ДМТ только для чтения с одним камешком (или, короче, ДМТ с одним камешком) — это ДМТ только для чтения $M$ с дополнительной возможностью помечать определённую ячейку входной ленты, помещая на неё камешек. Машина $M$ имеет только один камешек, поэтому в любой момент времени на ленте может быть помечен не более чем один символ. Точнее, ДМТ с одним камешком $M$ — это ДМТ $M=\left(Q, \Sigma , \Gamma , \delta , s^{*}\right)$, где $Q=Q_{1} \cup \left\{ q^{*} \mid q \in Q_{1}\right\}$ для некоторого конечного множества $Q_{1}$, $\Gamma =\Sigma \cup \left\{ \mathrm{B}\right\} \cup \left\{ a^{*} \mid a \in \Sigma \text{ или }a=\mathrm{B}\right\}$, $s \in Q_{1}$, и $\delta$ удовлетворяет следующим свойствам: для любых $q \in Q_{1}$ и $a \in \Sigma \cup \left\{ \mathrm{~ B}\right\}$,

1. $\delta (q, a)=(p, a, D)$ для некоторых $p \in Q_{1}$ и $D \in \left\{ L, R\right\}$.

2. $\delta \left(q, a^{*}\right)$ равно либо $\left(p, a^{*}, D\right)$, либо $\left(p^{*}, a, D\right)$ для некоторых $p \in Q_{1}$ и $D \in \left\{ L, R\right\}$.

3. $\delta \left(q^{*}, a\right)$ равно либо $\left(p^{*}, a, D\right)$, либо $\left(p, a^{*}, D\right)$ для некоторых $p \in Q_{1}$ и $D \in \left\{ L, R\right\}$.

4. $\delta \left(q^{*}, a^{*}\right)$ не определена.

(Здесь верхний индекс * обозначает камешек. Таким образом, состояние $q^{*}$ означает, что $M$ держит камешек в своём конечном управлении, и все символы на ленте непомечены; а состояние $q \in Q_{1}$ означает, что камешек находится во входной ячейке. Заметим, что свойство (i) означает, что $M$ не может пометить ячейку, если в данный момент она не держит камешек в своём конечном управлении.)

1. Постройте ДМТ $M$ с одним камешком такую, что на каждом входе $x$ длины $n \geq 2$ машина $M$ останавливается ровно через $n^{2}$ шагов.

2. Покажите, что для каждой ДМТ $M$ только для чтения существуют такие константы $c$ и $d$, что если $M$ останавливается на входе $x$ длины $n \geq 1$, то она обязательно останавливается не более чем за $c n+d$ шагов.

3. Покажите, что для каждой ДМТ $M$ с одним камешком существуют такие константы $c$ и $d$, что если $M$ останавливается на входе $x$ длины $n \geq 1$, то она обязательно останавливается не более чем за $c n^{2}+d$ шагов.

4. Покажите, что если $L$ — регулярный язык, то существует ДМТ $M$ с одним камешком, допускающая язык $\operatorname {SQRT}(L)$. (Напомним, что $\operatorname {SQRT}(L)$ определён в примере 2.44 как $\left\{ x \mid (\exists y)\left[\left|y\right|=|x|^{2}, x y \in L\right]\right\}$.)

В этом упражнении мы докажем, что язык, допускаемый ДМТ с одним камешком, обязательно является регулярным. Предположим, что $M=\left(Q, \Sigma , \Gamma , \delta , s^{*}\right)$ — ДМТ с одним камешком, где $Q=Q_{1} \cup \left\{ q^{*} \mid q \in Q_{1}\right\}$. Также предположим, что $M$ работает на входе $x$ и посещает ячейки $C_{0}, C_{1}, \ldots , C_{n}$, причём в ячейке $C_{i}$ находится символ $s_{i}$, для $i=0,1, \ldots , n$ (то есть $s_{0} s_{1} \cdots s_{n}=\mathrm{B} x \mathrm{~ B} \cdots \mathrm{~ B}$). Для каждого $i$, $0 \leq i \leq n$, определим частичную функцию $f_{i}: Q_{1} \rightarrow Q_{1}$ следующим образом: если $\delta \left(q, s_{i}^{*}\right)=\left(p, s_{i}^{*}, D\right)$ для некоторых $p \in Q_{1}$ и $D \in \left\{ L, R\right\}$, то $f_{i}(q)$ — это следующее состояние $r \in Q_{1}$ $(r \neq h)$, в котором $M$ возвращается в ячейку $C_{i}$. В противном случае $f_{i}(q)$ не определена. То есть функция $f_{i}$ кодирует состояния $M$ в моменты, когда она посещает ячейку $C_{i}$ с камешком в ячейке $C_{i}$ (аналогично последовательности пересечений ДМТ только для чтения). Заметим, что $f_{i}$ зависит как от машины $M$, так и от входного слова $x$.

Рассмотрим ещё одно расширение ДМТ только для чтения. ДМТ $M$ называется ДМТ только для чтения/стирания, если на каждом шаге она может только считывать входной символ и/или стирать его (то есть заменять исходный символ на $B$). То есть ДМТ $M=(Q, \Sigma , \Gamma , \delta , s)$ является ДМТ только для чтения/стирания, если $\Gamma =\Sigma \cup \left\{ \mathrm{B}\right\}$, и функция переходов $\delta$ удовлетворяет следующему свойству: для любых $q \in Q$ и $a \in \Sigma \cup \left\{ \mathrm{~ B}\right\}$, $\delta (q, a)$ равно либо $(p, a, D)$, либо $(p, \mathrm{~ B}, D)$ для некоторых $p \in Q$ и $D \in \left\{ L, R\right\}$.