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

Пусть $M_{1}$ — одноленточная ДМТ, заданная пятёркой ($Q, \Sigma$, $\Gamma , \delta , s)$, где $Q=\left\{ s, q_{1}, q_{2}, q_{3}, p\right\} , \Sigma = \left\{ a, b\right\} , \Gamma =\left\{ a, b, \mathrm{~ B}\right\}$, а $\delta$ задана следующей таблицей:

Постройте диаграмму переходов. Каким будет вычисление на входе $a b b a$? На входе $a^{3} b$?

Проследите работу ДМТ $M_{1}$ из примера 4.1 и покажите вычисление $M_{1}$ на входах aabba и bbbab.

Рассмотрим ДМТ $M_{2}=(Q, \Sigma , \Gamma , \delta , s)$ с $Q=\left\{ s, q_{1}, q_{2}\right\} , \Sigma = \left\{ a, b\right\}$, $\Gamma =\left\{ a, b, \mathrm{~ B}\right\}$, и

Рассмотрим ДМТ $M_{3}=(Q, \Sigma , \Gamma , \delta , s)$, с $Q=\left\{ s, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}\right\}$, $\Sigma = \left\{ a, b\right\} , \Gamma =\left\{ a, b, \mathrm{~ B}\right\}$, и

Рассмотрим ДМТ $M_{4}=(Q, \Sigma , \Gamma , \delta , s)$, в которой $Q, \Sigma$ и $\Gamma$ такие же, как у $M_{3}$, а $\delta$ совпадает с $\delta$ машины $M_{3}$, за исключением

.

Чему равен $L\left(M_{4}\right)$?

Покажите, что каждый регулярный язык тьюринг-разрешим.

Пусть $L \subseteq \left\{ 0,1\right\}^{*}$ тьюринг-разрешим. Покажите, что язык $\left\{ 0,1\right\}^{*}-L$ также тьюринг-разрешим. То есть для данной ДМТ $M$, вычисляющей характеристическую функцию $\chi_{L}$ языка $L$, подробно опишите, как изменить $M$, чтобы получить новую ДМТ $M^{\prime }$, такую что $M^{\prime }$ вычисляет характеристическую функцию $\left\{ 0,1\right\}^{*}-L$. Можете ли вы сделать то же самое для тьюринг-допустимых языков?

Покажите, что $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$ не может пометить ячейку, если в данный момент она не держит камешек в своём конечном управлении.)

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

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

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

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

Найдите трёхленточную ДМТ $M$, которая вычисляет функцию $f(n, m)=n \cdot m$ на натуральных числах $n$ и $m$.

Докажите, что для любого языка $A \subseteq (0+1)^{*}$ существует ДМТ $M$ с бесконечным числом лент, допускающая $L$.

Опишите подробно последнюю часть одноленточной ДМТ $M^{\prime }$ из теоремы 4.11, моделирующей двустороннюю ДМТ $M$. То есть покажите инструкции $M^{\prime }$, которые восстанавливают результат из двухдорожечной формы в однодорожечную форму. Например, она должна преобразовывать конфигурацию ленты

в конфигурацию $\mathrm{B} a \mathrm{~ B} a b b a b \mathrm{~ B}$, а также преобразовывать конфигурацию ленты

в конфигурацию $\mathrm{B} a b b \mathrm{~ B}$.

Опишите подробно шаг моделирования двусторонней ДМТ $M_{1}$ из теоремы 4.13, моделирующей трёхленточную ДМТ $M$. То есть покажите инструкции $M_{1}$, которые сдвигают головку влево, чтобы собрать информацию о лентах $M$, а затем сдвигают её вправо, чтобы на основе этой информации выполнить инструкцию $M$.

Для заданной двусторонне бесконечной одноленточной ДМТ $M$ с $\Sigma =\left\{ 1\right\}$ и $\Gamma = \left\{ 0,1, \mathrm{~ B}\right\}$ постройте многоленточную ДМТ $M^{\prime }$, которая на входе $\left(1^{n}, 1^{k}\right)$ моделирует $M$ на входе $1^{n}$ не более чем за $k$ шагов, так что она останавливается тогда и только тогда, когда $M$ останавливается на входе $1^{n}$ за не более чем $k$ шагов.

Постройте многоленточные ДМТ, допускающие следующие языки. Для каждого языка обсудите, сколько времени экономит ваша машина по сравнению с одноленточной ДМТ, использующей тот же алгоритм.

Постройте многоленточные ДМТ, вычисляющие следующие функции. Для каждой функции обсудите, сколько времени экономит ваша машина по сравнению с одноленточной ДМТ, использующей тот же алгоритм.

Двумерная ДМТ $M$ — это МТ, «лента» которой представляет собой двумерную плоскость, разделённую на бесконечное число ячеек (см. рисунок 4.15). Двумерная ДМТ $M$ работает подобно двусторонней ДМТ, за исключением того, что на каждом шаге она может сдвигать головку вверх (U), вниз (D), влево (L), вправо (R) или оставаться на месте (S). Изначально входное слово хранится в горизонтальной строке, и головка находится над пустой ячейкой справа от него. Когда машина останавливается, результат также хранится в горизонтальной строке (но не обязательно в той же строке, что и вход), при этом головка указывает на пустую ячейку справа от него. Все остальные символы, не находящиеся в этой строке, игнорируются.

Рисунок 4.15: Двумерная ДМТ.

Рисунок 4.16: Изменение конфигурации в упражнении 6(b).

Мы говорим, что автомат с магазинной памятью является детерминированным, если для любой конфигурации применима не более чем одна инструкция. Покажите, что любой детерминированный автомат с магазинной памятью может быть смоделирован двухленточной ДМТ. (В разделе 4.7 мы покажем, что все контекстно-свободные языки являются тьюринг-допустимыми.)

Рассмотрим RAM более подробно. RAM задаётся списком инструкций, пронумерованных от 1 до $n$. Инструкция относится к одному из типов, показанных на рисунке 4.17. (Заметим: мы приводим инструкции только в форме прямой адресации. Как обсуждалось в тексте, они также могут использовать константы или косвенную адресацию.) Изначально все регистры RAM содержат

значение 0, выходная лента «пуста» (что обозначается специальным символом, например B), а входная лента содержит конечное число неотрицательных целых чисел $\left(n_{1}, \ldots , n_{k}\right)$, хранящихся в ячейках с 1 по $k$, причём ячейка $k+1$ пуста. RAM начинает работу с инструкции 1 и после выполнения каждой инструкции $i$ переходит к инструкции $i+1$, если инструкция $i$ относится к одному из первых семи типов, либо переходит к инструкции $j$, заданной в инструкции $i$, если инструкция $i$ относится к одному из последних двух типов. RAM останавливается, когда достигает инструкции $k>n$.

Для произвольного RAM $M$ определим $L(M)=\left\{ \left(n_{1}, \ldots , n_{k}\right) \mid M\text{ останавливается на входе }\left(n_{1}, \ldots , n_{k}\right)\right\}$. Мы говорим, что $M$ вычисляет функцию $f: \bigcup_{k=1}^{\infty } \mathbf{N}^{k} \rightarrow \bigcup_{k=1}^{\infty } \mathrm{N}^{k}$, если на входе $\left(n_{1}, \ldots , n_{k}\right)$ машина $M$ останавливается с выходом $\left(m_{1}, \ldots , m_{\ell }\right)= f\left(n_{1}, \ldots , n_{k}\right)$.

Найдите грамматику $G$ такую, что $L(G)=\left\{ a^{n} b^{n} c^{n} \mid n \geq 0\right\}$.

Найдите грамматику $G$ такую, что $L(G)=\left\{ a^{2^{n}} \mid n \geq 0\right\}$.

Найдите грамматику $G$ такую, что $L(G)=\left\{ w w \mid w \in \left\{ a, b\right\}^{*}\right\}$.

Найдите грамматику $G$ такую, что $L(G)=\left\{ a^{n} b^{m} c^{n m} \mid n, m \geq 0\right\}$.

Рассмотрим грамматику $G_{1}$ с нетерминалами $V=\left\{ S, A, B, C\right\}$, терминалами $\Sigma = \left\{ a, b, c\right\}$ и правилами

Рассмотрим грамматику $G_{2}$ с нетерминалами $V=\left\{ S, A, L, L_{h}, R,[],\right\}$, терминалом $\Sigma =\left\{ a\right\}$ и правилами

Постройте грамматики для каждого из следующих языков. Также приведите (i) вывод заданной строки $x$ и (ii) доказательство того, почему ваша грамматика не порождает ни одной строки, не принадлежащей языку.