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

Задача 584

Дана машина Тьюринга $\mathfrak {M}=(\left\{ q, p, r\right\} ,\left\{ \Lambda , 0,1\right\} , P, q)$ со следующей программой $P=\left\{ q, 0 \rightarrow q, 0,+1 ; q, 1 \rightarrow q, 1,+1 ; q, \Lambda \rightarrow p, \Lambda ,-1 ; p, 0 \rightarrow p, 1,-1 ; p, 1 \rightarrow r, 0,-1 ; r, 0 \rightarrow r, 0,-1 ; r, 1 \rightarrow r, 1,-1\right\}$ . Какой будет заключительная конфигурация этой машины при работе на входе 1100? Сколько шагов при этом будет сделано? $\circledast$

?

Задача 585

Имеются три машины Тьюринга $\mathfrak {M}_{i}=\left(Q, \Sigma , P_{i}, q\right), i=1,2,3$ , которые имеют общие алфавит ленты $\Sigma =\left\{ \Lambda , a, b\right\}$ , множество состояний $Q=\left\{ q, p, r, s, t\right\}$ и начальное состояние $q$ . Их программы $P_{i}$ представлены в таблицах на рис. 38 на следующей странице. Определить, какие из этих машин переводят любое входное слово вида $a^{2 n} b$ , $n>0$ , в выходное $b a^{n}$ . $\circledast$

Рис. 38: Программы машин из задачи 585.

?

Задача 586

(а)(б)(в)

Пусть $\Sigma$ — произвольный алфавит, не содержащий $\Lambda$ . Требуется построить машину Тьюринга $\mathfrak {C}$ , которая меняет местами два аргумента, точнее переводит любой вход вида $x \Lambda y$ ( $x$ и $y$ — слова в алфавите $\Sigma )$ в выход $y \Lambda x$ со стандартной заключительной конфигурацией.

Определить, какие из следующих программ можно использовать для машины $\mathfrak {C}$ . В текстах программ $q_{0}$ — начальное состояние, $\alpha , \beta$ — это произвольные символы из $\Sigma , \gamma , \delta$ — это произвольные символы из $\Sigma \cup \left\{ u, v\right\}$ , где $u, v$ — новые символы.

?

(а)

$P_{1}=\left\{ q_{0}, \alpha \rightarrow q_{1}^{\alpha }, \Lambda ,+1 ; q_{1}^{\alpha }, \beta \rightarrow q_{1}^{\alpha }, \beta ,+1 ; q_{1}^{\alpha }, \Lambda \rightarrow q_{2}, \alpha ,+1 ; q_{2}, \alpha \rightarrow q_{3}^{\alpha }, \Lambda ,-1 ; q_{2}, \Lambda \rightarrow q_{4}, \Lambda ,-1 ; q_{3}^{\alpha }, \beta \rightarrow q_{3}^{\alpha }, \beta ,-1 ; q_{3}^{\alpha }, \Lambda \rightarrow q_{0}, \alpha ,+1 ; q_{4}, \alpha \rightarrow q_{4}, \alpha ,-1 ; q_{4}, \Lambda \rightarrow q_{5}, \Lambda ,-1 ; q_{5}, \alpha \rightarrow q_{5}, \alpha ,-1 ; q_{5}, \Lambda \rightarrow q_{6}, \Lambda ,+1\right\} ;$

(б)

$P_{2}=\left\{ q_{0}, \alpha \rightarrow q_{0}, \alpha ,+1 ; q_{0}, \Lambda \rightarrow q_{1}, u,+1 ; q_{1}, \alpha \rightarrow q_{1}, \alpha ,+1 ; q_{1}, \Lambda \rightarrow q_{2}, v, 0 ; q_{2}, \gamma \rightarrow q_{3}^{\gamma }, \Lambda ,-1 ; q_{3}^{\gamma }, \delta \rightarrow q_{3}^{\delta }, \gamma ,-1 ; q_{3}^{\alpha }, \Lambda \rightarrow q_{9}^{\alpha }, \Lambda ,+1 ; q_{3}^{u}, \Lambda \rightarrow q_{6}, \Lambda ,+1 ; q_{6}, \alpha \rightarrow q_{6}, \alpha ,+1 ; q_{6}, v \rightarrow q_{7}, \Lambda ,-1 ; q_{7}, \alpha \rightarrow q_{7}, \alpha ,-1 ; q_{7}, \Lambda \rightarrow q_{8}, \Lambda ,+1 ; q_{9}^{\alpha }, \delta \rightarrow q_{9}^{\alpha }, \delta ,+1 ; q_{9}^{\alpha }, \Lambda \rightarrow q_{2}, \alpha , 0\right\} ;$

(в)

$P_{3}=\left\{ q_{0}, \alpha \rightarrow q_{0}, \alpha ,+1 ; q_{0}, \Lambda \rightarrow q_{1}, u,-1 ; q_{1}, \alpha \rightarrow q_{1}, \alpha ,-1 ; q_{1}, \Lambda \rightarrow q_{2}, \Lambda ,+1 ; q_{2}, \alpha \rightarrow q_{3}^{\alpha }, v,+1 ; q_{3}^{\gamma }, \delta \rightarrow q_{3}^{\delta }, \gamma ,+1 ; q_{3}^{\gamma }, \Lambda \rightarrow q_{6}, \gamma , 0 ; q_{6}, \alpha \rightarrow q_{7}^{\alpha }, \Lambda ,-1 ; q_{6}, u \rightarrow q_{8}, \Lambda ,-1 ; q_{7}^{\alpha }, \delta \rightarrow q_{7}^{\alpha }, \delta ,-1 ; q_{7}^{\alpha }, \Lambda \rightarrow q_{9}^{\alpha }, \Lambda ,+1 ; q_{8}, \alpha \rightarrow q_{8}, \alpha ,-1 ; q_{8}, u \rightarrow q_{8}, \Lambda ,-1 ; q_{8}, v \rightarrow q_{8}, \Lambda ,-1 ; q_{8}, \Lambda \rightarrow q_{4}, \Lambda ,+1 ; q_{9}^{\alpha }, \delta \rightarrow q_{3}^{\delta }, \alpha ,+1\right\}$ . $\circledast$

Задача 587

Построить машину Тьюринга, которая по каждому входному слову вида $a^{n} b^{k}$ выдаёт результат $a^{\lfloor (n+k) / 2\rfloor } b^{\lfloor (n+k) / 2\rfloor }$ . Как работает машина на других входах — несущественно. Оценить время работы построенной машины. $\circledast$

?

Задача 588

Построить машину Тьюринга, которая по каждому входному слову вида $0^{n} 1^{k}$ , где $n>k>0$ , выдаёт результат 0, а для всех остальных слов — результат 1. Оценить время работы построенной машины. $\circledast$

?

Задача 589

Построить машину Тьюринга, которая переводит любое входное слово $w \in \left\{ a, b\right\}^{*}$ в выходное $a^{n} \Lambda b^{m}$ , где $n$ — количество букв $a$ , а $m$ — количество букв $b$ в слове $w$ . Другими словами, выполняется сортировка букв слова с последующим их разделением. Оценить время работы построенной машины. $\circledast$

?

Задача 590

Пусть алфавит $\Sigma$ не содержит символов $\Lambda$ и *. Построить программу машины Тьюринга, которая выполняла бы перенос последнего слова на ленте в алфавите $\Sigma$ слева направо в место ленты, отмеченное *. Точнее, из ленты $\alpha \Lambda w \Lambda^{n} *$ должно быть получено $\alpha \Lambda \Lambda^{n} w$ , где $w \in \Sigma^{*}$ . $\circledast$

?

Задача 591

Построить машину Тьюринга, выполняющую следующую задачу: по входу, состоящему из одного или нескольких слов $w_{1} \Lambda \ldots \Lambda w_{n}$ в алфавите $\Sigma$ (возможно, что $n=1$ ), построить выход, удвоив последнее из слов: $w_{1} \Lambda \ldots \Lambda w_{n} \Lambda w_{n}$ . $\circledast$

?

Задача 592

Доказать, что для любой константы $k>1$ можно построить машину Тьюринга, которая решает задачу 591 за время не большее $n^{2} / k+O(n)$ , где $n$ — это суммарная длина входных слов. $\circledast$

?

Задача 593

Построить машину Тьюринга, сравнивающую два входных слова в алфавите $\left\{ a, b, c\right\}$ лексикографически. Эта машина Тьюринга должна вычислять словарную функцию: $\circledast$

f(x, y)= \begin{cases} a, & \text{ если } x<y, \\ b, & \text{ если } x=y, \\ c, & \text{ если } y<x.\end{cases}

?

Задача 594

Построить программы машин Тьюринга, вычисляющих следующие словарные функции в алфавите $\Sigma =\left\{ a, b, c\right\}$ :

?

(а)

циклическая перестановка букв: $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$ возрастающую арифметическую прогрессию.

Задача 595

Построить машину Тьюринга для перевода записи числа из двоичной системы в унарную, входной алфавит $\left\{ 0,1\right\}$ . $\circledast$

?

Задача 596

Построить машину Тьюринга, которая по унарной записи трёх чисел, то есть входу вида $\left.\left.\left.\right|^{n+1} \Lambda \right|^{k+1} \Lambda \right|^{m+1}$ , выдаёт результат 0, если $0<n<k+m$ , и 1 в противном случае. Оценить время работы построенной машины. $\circledast$

?

Задача 597

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

?

(а)

$x+y$ ;

(б)

$x \div y$ ;

(в)

$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$ -го аргумента: $\operatorname {id}_{m}, m$ — заранее заданная константа. $\circledast$

Задача 598

(а)(б)(в)(г)

Даны машины Тьюринга со стандартной заключительной конфигурацией $\mathfrak {M}_{i}$ , каждая из которых вычисляет словарную функцию $f_{i}(x)$ за время $t_{i}(x), i=1, \ldots , n$ . Указать, как построить, и оценить время работы

?

(а)

машины $\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)$ , вычисляющей функцию

g_{2}\left(x_{1} a x_{2} a \ldots a x_{n}\right)=f_{1}\left(x_{1}\right) a f_{2}\left(x_{2}\right) a \ldots a f_{n}\left(x_{n}\right) ;

(в)

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

g_{3}(x)= \begin{cases} \mathfrak {M}_{2}(x), & \text{ если } \mathfrak {M}_{1}(x) \text{ непусто, } \\ \mathfrak {M}_{3}(x), & \text{ если } \mathfrak {M}_{1}(x) \text{ пусто; }\end{cases}

(г)

машины $\operatorname {while}(\mathfrak {M}_{1}, \mathfrak {M}_{2})$ , вычисляющей функцию $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)$ . $\circledast$

Задача 599

(а)(б)(в)

Даны следующие машины Тьюринга со стандартной заключительной конфигурацией: - $\operatorname {copy}(a)$ — копирует вход, используя символ $a$ как разделитель между оригиналом и копией: $w \mapsto w a w$ ; - $\operatorname {replace}(a, b)$ — заменяет самое левое вхождение символа $a$ на $b$ , если символа $a$ нет, то вход не меняется; - $\operatorname {add}$ — складывает два числа, записанных в унарной системе счисления; - $\operatorname {mult}$ — умножает два числа, записанных в унарной системе счисления; - $\operatorname {nop}$ — не изменяет вход.

Определить, какие арифметические функции вычисляются (в унарной системе счисления) следующими машинами Тьюринга, построенными методами из задачи 598 на предыдущей странице:

?

(а)

$\operatorname {copy}(*) ; \operatorname {par}(*, \operatorname {copy}(\Lambda ), \operatorname {copy}(\Lambda )) ; \operatorname {par}(*, \operatorname {mult}, \operatorname {add}) ; \operatorname {replace}(*$ , $\Lambda$ ); $\operatorname {add}$ ;

(б)

$\operatorname {copy}(*) ; \operatorname {par}(*, \operatorname {copy}(\Lambda ), \operatorname {copy}(\Lambda )) ; \operatorname {par}(*, \operatorname {mult}, \operatorname {add}) ; \operatorname {par}(*$ , ( $\operatorname {copy}(\Lambda ) ; \operatorname {add}), \operatorname {nop}) ; \operatorname {replace}(*, \Lambda ) ; \operatorname {add} ;$

(в)

$\operatorname {copy}(*) ; \operatorname {par}(*,(\operatorname {copy}(\Lambda ) ; \operatorname {mult}), \operatorname {nop}) ; \operatorname {par}(*,(\operatorname {copy}(\Lambda ) ; \operatorname {add})$ , $\operatorname {nop}$ ); $\operatorname {replace}$$(*, \Lambda )$ ; $\operatorname {add}$ .

Задача 600

Даны машины Тьюринга со стандартной заключительной конфигурацией из задачи 599 на предшествующей странице, а также следующие: - $\operatorname {id}_{i}$ — возвращает $i$ -й аргумент или пустое слово, если количество аргументов меньше $i$ ; - $\operatorname {pos}_{i}$ — проверяет, является ли $i$ -й аргумент положительным (числа записаны в унарной системе), возвращает пустое слово, если он равен нулю, или |, если он положителен; - $\operatorname {dec}$ — уменьшает аргумент на единицу, если он положителен, в противном случае вход не изменяется (числа записаны в унарной системе). Определить, какие арифметические функции (в унарной системе) вычисляются каждой из машин Тьюринга, программы которых схематично изображены на рис. 39 на следующей странице (см. задачу 598 на предшествующей странице). $\circledast$

?

Задача 601

(а)(б)(в)(г)

Используя машины Тьюринга из предыдущих задач, построить программы машин Тьюринга, вычисляющих следующие функции:

?

(а)

$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}$ $\circledast$

Задача 602

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

?

(а)

$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$ на тот, который находился в ячейке в начальной конфигурации. $\circledast$

Задача 603

Построить машину Тьюринга для задачи 591 на стр. 185, не увеличивая исходный алфавит $\Sigma$ . $\circledast$

?

Задача 604

(а)(б)

Реализовать следующие машины Тьюринга без расширения алфавита:

?

(а)

стереть вторую половину слова, оставив центральный символ, если длина была нечётной;

(б)

сложить два числа, записанных в двоичной системе. $\circledast$

Задача 605

Один из подходов к моделированию двухсторонней ленты на односторонней заключается в том, чтобы содержимое неотрицательной половины ленты $\mathfrak {M}$ хранить в ячейках с нечётными номерами, а содержимое левой половины — с чётными. То есть новая лента будет иметь вид $\beta (0)=\# , \beta (2 x+1)=\alpha (x)$ и $\beta (2 x)=\alpha (-x)$ при $x>0$ . Построить программу односторонней машины $\mathfrak {N}$ , реализующую этот подход. $\circledast$

?

Задача 606

Доказать, что всякую арифметическую функцию $f(x)$ , вычислимую на некоторой машине Тьюринга $\mathfrak {M}=\left(Q, \Sigma , P, q_{0}\right)$ в унарной системе счисления, можно также вычислить на машине Тьюринга $\mathfrak {N}$ , алфавит ленты которой содержит лишь два символа: $\Lambda$ и $\mid$ . Указание. Использовать для моделирования одного символа $a_{i}$ алфавита $\Sigma$ блок из нескольких подряд идущих ячеек, содержащих слово $\left.\right|^{i} \Lambda^{k-i}$ , где $\Sigma =\left\{ a_{0}, \ldots , a_{k}\right\}$ . Заменить каждую команду $\mathfrak {M}$ группой команд, обрабатывающих соответствующий блок ячеек. $\circledast$

?

Задача 607

$k$ -ленточная машина Тьюринга имеет $k$ лент, по каждой из которых перемещается своя головка. Команда $k$ -ленточной машины Тьюринга имеет вид

q, a_{1}, a_{2}, \ldots , a_{k} \rightarrow p, b_{1}, b_{2}, \ldots , b_{k}, s_{1}, s_{2}, \ldots , s_{k},

где $q, p \in Q$ — состояния, $a_{1}, \ldots , a_{k}$ — символы, наблюдаемые головками на соответствующих лентах, $b_{1}, \ldots , b_{k}$ — символы, записываемые головками на соответствующих лентах, $s_{1}, \ldots , s_{k}$ — направления сдвигов головок на соответствующих лентах. Входные данные записываются на первой ленте, а остальные в начальной конфигурации пусты. Результат также располагается на первой ленте.

Доказать, что любую функцию, вычислимую на $k$ -ленточной машине Тьюринга, можно также вычислить и на обычной машине Тьюринга. На сколько при этом увеличится время вычисления? $\circledast$

?

Задача 608

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

?

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