Одноленточные машины Тьюринга

Пусть $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$. Можете ли вы сделать то же самое для тьюринг-допустимых языков?