Банк задач по математике

Пример 4.12

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

?

Пример 4.14

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

?

Задача 4.3.1

Опишите подробно последнюю часть одноленточной ДМТ $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}$ .

?

Задача 4.3.2

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

?

Задача 4.3.3

Для заданной двусторонне бесконечной одноленточной ДМТ $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$ шагов.

?

Задача 4.3.4

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

?

(a)

$\left\{ w \in \left\{ a, b\right\}^{*} \mid w=w^{R}\right\}$ .

(b)

$\left\{ \left(x_{1}, x_{2}\right) \mid x_{1}, x_{2} \in \left\{ a, b\right\}^{*}, x_{1}\text{ является подстрокой }x_{2}\right\}$ .

(c)

$\left\{ a^{n} b^{n} c^{n} \mid n \geq 0\right\}$ .

(d)

$\left\{ a^{m} b^{n} c^{k} \mid m, n, k \geq 0, m \neq n\text{ или }n \neq k\text{ или }k \neq m\right\}$ .

(e)

$\left\{ w \in \left\{ a, b, c\right\}^{*} \mid \#_{a}(w)=\#_{b}(w)=\#_{c}(w)\right\}$ .

Задача 4.3.5

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

?

(a)

$f(x)=x^{R}$ на строках $x \in \left\{ a, b\right\}^{*}$ .

(b)

$f(m, n)=n^{m}$ на натуральных числах $m, n$ .

(c)

$f\left(n_{1}, n_{2}, \ldots , n_{k}\right)=\max \left\{ n_{1}, n_{2}, \ldots , n_{k}\right\}$ на положительных целых числах $n_{1}$ , $\ldots , n_{k}$ , где $k$ не фиксировано.

(d)

$f\left(n_{1}, n_{2}, \ldots , n_{k}\right)=$ максимальное число вхождений одного и того же положительного целого числа в $\left(n_{1}, \ldots , n_{k}\right)$ , где $k$ не фиксировано. (Например, $f(3,5,3,6,7)=2$ и $f(3,6,3,6,6,5,6)=4$ .

(e)

$\operatorname {sort}\left(n_{1}, n_{2}, \ldots , n_{k}\right)=$ список $\left(n_{1}, \ldots , n_{k}\right)$ , отсортированный по возрастанию, где $n_{1}, \ldots , n_{k}$ — положительные целые числа, а $k$ не фиксировано.

Задача 4.3.6

(a)(b)(c)

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

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

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

?

(a)

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

(b)

Разработайте двумерную ДМТ, переводящую начальную конфигурацию ленты (a) в новую конфигурацию (b), как показано на рисунке 4.16.

(c)

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

Задача 4.3.7

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

?

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