Основные определения
Рассматриваемая в этом разделе модель алгоритмов была предложена
английским математиком Тьюрингом в 1937 г. еще до создания современных компьютеровАналогичная модель вычислений была примерно в то же время определена Е. Постом. Поэтому иногда такие машины называют машинами Тьюринга-Поста
Он исходил из общей идеи моделирования работы вычислителя,
оперирующего в соответствии с некоторым строгим предписанием.
В машине Тьюринга расчленение процесса вычисления на элементарные шаги доведено
в известном смысле до предела. Элементарным действием является замена одного символа
в ячейке на другой и перемещение к соседней ячейке. При таком подходе процесс вычисления значительно удлиняется, но зато логическая структура процесса
сильно упрощается и приобретает удобный для теоретического исследования вид.
Машина Тьюринга (м.Т.) состоит из неограниченной в обе стороны ленты,
разбитой на ячейки, по которой передвигается головка машины.
Такая "бесконечность" ленты является математической абстракцией,
отражающей потенциальную неограниченность памяти вычислителя.
Разумеется, в каждом завершающемся вычислении используется только конечная часть
этой памяти - конечное число ячеек.
В каждой
ячейке ленты записан один символ из конечного внешнего алфавита машины $$\Sigma = \{ a_{0}, a_{1}, \dots ,a_{m} \}$$. Головка машины представляет конечный автомат,
который в каждый момент
времени находится в одном из внутренних состояний Q ={q0,q1,... ,
qn }. На каждом шаге головка в зависимости от своего
внутреннего состояния и символа в ячейке, которую она наблюдает,
изменяет свое внутреннее состояние и содержимое наблюдаемой ячейки
и может сдвинуться на одну ячейку вправо или влево либо остаться
на месте.
Дадим более формальное определение.
Определение 9.1. Машина Тьюринга - это система вида
$${\cal M} = < Q, \Sigma, P,q_0, q_f >,$$
включающая следующие компоненты:
Q ={q0,q1,... ,qn } - внутренний алфавит (алфавит состояний);
$$\Sigma = \{ a_{0}, a_{1}, \dots , a_{m-1} \}$$ - внешний алфавит (алфавит ленты );
P - программа машины, в которой для каждой пары $$q_{i} \in Q \setminus \{ q_{f} \} , a_{j} \in \Sigma$$ имеется (одна!) команда вида
$$q_i a_j \rightarrow q_k a_l C,\ q_k \in Q, a_l \in \Sigma,$$
$$C \in \{ Л, П, Н\}$$ задает сдвиг головки вправо, влево или на месте;
$$q_{0} \in Q$$ - начальное состояние;
$$q_{f} \in Q$$ - заключительное состояние.
Выделим в алфавите $$\Sigma$$ специальный пустой символ $$a_{0} =\wedge$$ и будем считать, что во всех ячейках ленты, кроме конечного их числа, в начальный и во все последующие моменты находится пустой символ.
Будем говорить, что некоторый символ стирается, если он заменяется на пустой. Два слова из $$\Sigma ^{*}$$ будем считать равными, если они совпадают после
отбрасывания всех пустых символов слева и справа. Например, $$\wedge \wedge ab\wedge c\wedge =\wedge ab\wedge c = ab\wedge c$$, но $$ab \wedge c \ne abc$$.
Как и для конечных автоматов, программу P можно задавать с помощью таблицы
размера n x m, строки которой соответствуют состояниям из Q,
а столбцы - символам из входного алфавита $$\Sigma,$$ в которой на пересечении строки qi и столбца aj стоит тройка qk al C - правая часть команды qi aj -> qk al C.
Определение 9.2. Назовем конфигурацией м.Т. $${\cal M }\ $$ в некоторый момент времени слово K= wл qi aj wп, где $$w_{л} \in \Sigma ^{*}$$ - слово на ленте левее текушего положения головки, qi - внутреннее состояние в данный момент, aj - символ, обозреваемый головкой, $$w_{п} \in \Sigma ^{*}$$ - слово на ленте правее текушего положения головки.
Будем считать, что слово wл aj wп содержит
все значащие символы на ленте. Поэтому, с точностью до
описанного выше равенства слов, конфигурация определена однозначно.
В частности, если $$w_{л}=\varepsilon$$, т.е. пусто, то левее положения головки все ячейки пусты, а если $$w_{п}=\varepsilon$$, то
правее положения головки все ячейки пусты.
Начальная конфигурация - это конфигурация вида q0w, т.е.
в начальный момент времени головка в состоянии q0 обозревает
первый символ входного слова w. { it Заключительная } конфигурация - это конфигурация вида w1 qf w2, в которой машина находится в
заключительном состоянии qf.
Определение 9.3. Скажем, что конфигурация K= w1 qi aj w2 м.Т. $${\cal M }$$ за один шаг (такт) переходит в конфигурацию $$K^\prime= w_1^\prime q_k a_{j^\prime} w_2^\prime\ (K \vdash_{\cal M } K^\prime)$$, если в программе имеется команда qi aj -> qk al C и при этом,
если С=Н, то w1'=w1, w2'=w2 и a{j'}=al;
если С=Л, то w1=w1' a, a{j'}=a, w2'=al w2 (если $$w_{1}=\varepsilon , /$$ то $$w_{1}^{'} = \varepsilon$$ и $$a_{j^'} =\wedge$$);
если С=П, то w2=aw2', a{j'}=a, w1'=w1 al (если $$w_{2}=\varepsilon , /$$ то $$w_{2}^{'} = \varepsilon$$ и $$a_{j^'} =\wedge$$).
Как обычно, через $$\vdash^*_{\cal M }$$ обозначим рефлексивное и транзитивное
замыкание отношения $$\vdash_{\cal M },\ $$ а $$K \vdash^n_{\cal M } K^\prime$$ будет
означать, что конфигурация K за n шагов переходит в K'.
(Если из контекста ясно, о какой машине идет речь, то
индекс $${\cal M }$$ будем опускать).
Пример 9.1.
(рис 9.1) Выполнение команды q3 0 -> q5 1 П Например, ситуации, представленной на рис.9.1 слева соответствует конфигурация $$K= 1q_{3}01\wedge 0$$. Предположим, что программа P содержит команду q30 -> q51 П. Тогда после выполнения этой команды K перейдет за один шаг в конфигурацию $$K^{'}= 11q_{5}1\wedge 0$$, показанную на этом рисунке
справа. Следовательно, $$K \vdash K^\prime$$.
Определение 9.4. Вычисление м.Т. $${\cal M}\ $$ на входе w - это конечная или
бесконечная последовательность конфигураций $$K_0 \vdash K_1 \vdash\ldots \vdash K_t\vdash K_{t+1}\ldots $$
такая, что K0=q0w - начальная конфигурация.
Эта последовательность конечна, когда
ее последняя конфигурация Kn= v1 qf v2 - заключительная.
В этом случае вычисление назовем результативным, а слово v = v1 v2 -
его результатом на входе w (всегда будем предполагать, что v не
содержит пустых символов слева и справа).
Определение 9.5. Скажем, что м.Т. $${\cal M}\ $$ вычисляет частичную словарную функцию $$f:\ \Sigma^* \rightarrow \Sigma^*,\ $$ если для каждого слова w из области определения f существует результативное вычисление $${\cal M}\$$ с результатом $$f(w)$$, а если f(w) не определена $$(f(w)=\infty)$$, то вычисление $${\cal M}\ $$ на входе w бесконечно.
Скажем, что две м.Т. $${\cal M}_1$$ и $${\cal M}_2\ $$ эквивалентны, если они вычисляют одинаковые функции.
Далее мы будем также рассматривать вычисления арифметических функций, т.е. функций с натуральными аргументами, принимающих натуральные значения. Для представления натуральных чисел используем унарное кодирование: число n будет представляться как слово из n палочек |n, а последовательные аргументы будем отделять *.
Определение 9.6. Скажем, что м.Т. $${\cal M}\ $$ вычисляет частичную арифметическую функцию f: Nk -> N, если для любого набора чисел (x1,x2, ... ,xk), на котором f определена, существует
результативное вычисление $${\cal M}\ $$ на входе $$|^{x_1}* |^{x_2}*\ldots * |^{x_k}$$ с результатом $$|^{f(x_1,x_2,\ldots ,x_k)}$$,
а если $$f(x_{1},x_{2},\dots ,x_{k})=\infty$$,
то вычисление $${\cal M}\$$ на соответствующем входе бесконечно.
Аналогичное определение можно дать и для других спосбов кодирования
чисел (двоичного, десятичного и др.). Ниже мы покажем, что класс
вычислимых функций не зависит от выбора одного из таких кодирований.
Тьюрингово программирование
В этом разделе мы приведем примеры вычислений на машинах Тьюринга
и рассмотрим некоторые общие приемы, позволяющие комбинировать программы
различных м. Т. для получения более сложных вычислений. Будем считать, что
ячейки ленты м.Т. занумерованы от $$-\infty$$ до $$+\infty$$, причем
в начальной конфигурации головка находится в 1-ой ячейке:
(рис 9.2) Нумерация ячеек ленты машины ТьюрингаПример 9.2.Функция f(x)=x+1
Унарное кодирование.
Пусть м.Т. $${\cal M}_1=<\{q_0,q_f \},\{\wedge,|\},P_1,q_0,q_f>$$, где $$P_{1}: q_{0} |\to q_{0} | П, q_{0} \wedge \to q_{f} | Н$$.
Ясно, что м.Т. $${\cal M}_1$$ проходит по массиву палочек слева направо и записывает в первой пустой ячейке новую |.
Бинарное кодирование.
Пусть м.Т. $${\cal M}_1^\prime=<\{q_0,q_1,q_f \},\{\wedge,0,1\}, P_1^\prime,q_0,q_f>$$, где $$P_1^\prime$$:
$$q_0 0\rightarrow q_0 0 \textit{П},\ \ q_0 1\rightarrow q_0 1 \textit{П},\ \ q_0 \wedge \rightarrow q_1 \wedge \textit{Л},\\q_1 0\rightarrow q_f 1 \textit{Н},\ \ q_1 1\rightarrow q_1 0 \textit{П},\ \ q_1 \wedge \rightarrow q_f 1 \textit{Н}.$$
Нетрудно видеть, что эта машина в состоянии q0 находит младший разряд двоичного входа, затем в состоянии q1, идя справа налево, заменяет единицы на нули до тех пор, пока не
находит 0 (или $$\wedge$$ ) и заменяет его на 1. Следовательно, м.Т. $${\cal M}_1^\prime\ $$ вычисляет функцию f(x) = x+1.
Пример 9.2. Копирование.
Рассмотрим функцию копирования (дублирования) слов в алфавите $$\Sigma : copy(x)= x \times x$$ (мы предполагаем, что $$* \notin \Sigma$$ ).
Для ее реализации используем один из типичных приемов Тьюрингова программирования - { it расширение алфавита}.Пусть $$\Sigma ^{'}= \{ a^{'} | a \in \Sigma \}$$ и $$\Sigma _{1}=\Sigma \cup \Sigma ^{'}$$. М.Т. $${\cal M}_2$$, копирующая вход, работает следующим образом:
отмечает 1-ый символ входа, идет направо, ставит * после входа и возвращается в начало:$$q_0 a \rightarrow q_1 a^\prime \textit{П}\ (a \in \Sigma); \ q_1 a \rightarrow q_1 a \textit{П}\ (a \in \Sigma \backslash \{\wedge\}; \ q_1 \wedge \rightarrow q_2 * \textit{Л}; \\ q_2 a \rightarrow q_2 a \textit{Л}\ (a \in \Sigma \cup \{*\}); \ q_2 a^\prime \rightarrow q_a a^\prime \textit{П}\ (a \in \Sigma );$$
в состоянии qa движется направо и записывает a в первую свободную ячейку:$$q_a b \rightarrow q_a b \textit{П}\ (b \in \Sigma \cup \{*\}); \ \ q_a \wedge \rightarrow q_4 a \textit{Л}\;$$
возвращается в отмеченную ячейку и передвигает метку ' на одну ячейку вправо, снова переходя в состояние q2:$$q_4 a \rightarrow q_4 a \textit{Л}\ (a \in \Sigma \cup \{*\}); \ q_4 a^\prime \rightarrow q_5 a \textit{П}\ (a \in \Sigma ); \ q_5 a \rightarrow q_2 a^\prime \textit{Н}\ (a \in \Sigma );$$
увидев символ * в состоянии q5, останавливается:$$q_5 * \rightarrow q_f*\textit{Н}.$$
Из этого описания непосредственно следует, что $$q_0x {\vdash}^* xq_f*x$$ для любого $$x \in \{ \Sigma \} ^{*}$$.
Стандартная заключительная конфигурация
Назовем заключительную конфигурацию стандартной, если в ней головка наблюдает первый значащий символ результата, который находится
в 1-ой ячейке (т.е. в той же ячейке, где начиналось входное слово).
Лемма 9.1.Для всякой м.Т. $${\cal M}\ $$ можно построить
эквивалентную м.Т. $${\cal M}^\prime$$, у которой все заключительные конфигурации стандартны.
Доказательство. Пусть $${\cal M} = <Q, \Sigma, P,q_0, q_f>$$. Определим по ней м.Т. $$\ {\cal M}^\prime = <Q^\prime, \Sigma^\prime, P^\prime,q_0^\prime, q_f^\prime>$$, которая удовлетворяет требованиям
леммы. Положим $$\Sigma ' = \Sigma \cup \{ a' | a \in \Sigma \} \cup \{ #\}$$, где # - новый символ. $${\cal M}^\prime\ $$ работает
следующим образом.
Отмечает символ в первой ячейке штрихом и переходит в начальное состояние $${\cal M}:\ \ q_0^\prime a \rightarrow q_0 a^\prime \textit{Н}$$.
Далее работает как $${\cal M},\ $$ но сохраняет штрих в первой ячейке и вместо пустого символа $$\wedge$$ записывает #. Для этого для каждой команды qiaj -> qk alC из P'
в P' добавляется ее дубликат qiaj' -> qk al'C, в правых частях команд символ $$\wedge$$ всюду заменяется на # и для каждой команды вида $$q_{i} \wedge \to q_{k} a_{l} C$$ в P' добавляется команда qi # -> qk al C. После завершения этого этапа все посещенные в процессе работы головкой $${\cal M}\$$ ячейки составляет непрерывный отрезок, не содержащий пустых символов.
Далее $${\cal M}^\prime\ $$ стирает ненужные символы # слева и справа от блока ячеек, содержащего первую ячейку и все ячейки с символами результата, и переходит в одну из трех следующих конфигураций:$$K_1= q_\textit{л} \#^\prime \#\ldots \# w\wedge,\ \ K_2=\wedge q_\textit{п} w \# \ldots \#\#^\prime, \ \ K_3 =\wedge q_\textit{н} w_1 a^\prime w_2\wedge,$$
где w - результат работы { cal M} (с заменой символов $$\wedge$$ внутри w на #) и w1aw2 = w.
Сдвигает в нужном направлении результат, совмещая его начало с ячейкой, помеченной штрихом, заменяет все # внутри w на $$\wedge$$ , снимает штрих в 1-ой ячейке и останавливается. Например, для K1 это достигается с помощью следующих команд (мы предполагаем, что ни одно из используемых ниже состояний $$q_{л}, q_{1}, p, p_{1}, p_{2}, p_{3}, p^{a}, p^{a'} (a \in \Sigma \cup \{ #\} )$$ не входит в Q ):поиск левого конца w: $$q_{л} a \to q_{л}aП (a \in \{ \#', \#\} )$$ ; $$q_{л}a \to q_{1}a'П (a \in \Sigma )$$ (отметили первый символ w ), $$q_{л} \wedge \to p_{3} \wedge Л;$$ (результат пуст);
поиск правого конца w: $$q_{1} a \to q_{1}aП (a \in \Sigma \cup \{ #\} )$$, $$q_{1} \wedge \to p \wedge Л$$ (в состоянии p наблюдает последний символ w );
сдвиг результата на 1 ячейку влево: $$pa \to p^{a} \wedge Л; p^{a} b \to p^{b} aЛ;$$ pa b' -> pb'aП; pb' # -> p1 b'П;
возврат к правому концу и переход к следующему сдвигу: $$p_{1} a \to p_{1}aП (a \ne \wedge ); p_{1}\wedge \to p \wedge Л;$$
при сдвиге до 1-ой ячейки замена символов # на $$\wedge$$ и удаление
штриха:$$p^{a\prime} \#^\prime \rightarrow p_2 a^\prime \textit{Н}; p_2 b \rightarrow p_2 b \textit{П};\\ p_2 \wedge \rightarrow p_3 \wedge \textit{Л};\\
p_3 \# \rightarrow p_3 \wedge \textit{Л}; \ \ p_3 b \rightarrow p_3 b \textit{П}\ (b \neq \#, b \neq a^\prime) ;
\ \ p_3 a^\prime \rightarrow q_f^\prime a \textit{Н}.$$
Из построения непосредственно следует, что м.Т. $${\cal M}^\prime\ $$ удовлетворяет требованиям леммы.
Односторонние машины Тьюринга
Машина Тьюринга $${\cal M}\ $$ называется односторонней,
если в процессе вычисления ее головка никогда не сдвигается левее
начальной ячейки (т.е. всегда находится в ячейках с положительными
номерами).
Лемма 9.2. Для всякой м.Т. $$\cal M$$ можно построить
эквивалентную одностороннюю м.Т. $${\cal M}^\prime\ $$.
Доказательство. Пусть $$\ {\cal M} = <Q, \Sigma, P,q_0, q_f>$$. Будем считать (используя лемму 1 ), что $$\cal M\ $$ завершает работу в стандартных конфигурациях. Требуемая м.Т. $$\ {\cal M}^\prime = <Q^\prime, \Sigma^\prime,
P^\prime,q_0^\prime, q_f^\prime>\ $$ будет моделировать работу $$\cal M$$, используя "многоэтажную" ленту. Содержимое ячеек
на 1-ом (нижнем) этаже будет на каждом такте совпадать с содержимым
тех же ячеек $$\cal M$$, на 2-ом этаже будет копироваться
содержимое левой полуленты: на нем в i -ой ячейке $${\cal M}^\prime\ $$
будет тот же символ, что и в -i -ой ячейке $$\cal M$$. Кроме того,
на 3-ем этаже в 1-ой ячейке будет стоять отмечающий ее символ #.
Таким образом, $$\Sigma ' = \Sigma x \Sigma x \{ \wedge , # \} \cup \Sigma$$. Работа $${\cal M}^\prime\ $$ будет происходить следующим образом.
1) На первом этапе отмечается 1-я ячейка и содержимое входа переписывается на 1-ый этаж трехэтажной ленты:$$q_0^\prime a \rightarrow p_1 \left(\frac{\frac {\#}{\wedge}}{a}\right)\textit{П}\ \ (a \in
\Sigma);\qquad p_1 a \rightarrow p_1 \left(\frac{\frac {\wedge}{\wedge}}{a}\right)\textit{П}\ (
a \in \Sigma \backslash \{\wedge \};\\\qquad p_1 \wedge \rightarrow p_2\,\wedge\, \textit{Л};\\
\ p_2 \left( \frac{\frac {\wedge}{\wedge}}{a} \right) \rightarrow
p_2 \left(\frac{\frac {\wedge}{\wedge}}{a} \right)\,\textit{Л}\ \ (a \in \Sigma);\ \ p_2
\left(\frac{\frac {\#}{\wedge}}{a}\right) \rightarrow
q_0 \left(\frac{\frac {\#}{\wedge}}{a}\right)\textit{Л}\ \ (a \in \Sigma).$$
Затем $${\cal M}^\prime\ $$ моделирует работу $$\cal M\ $$,
используя для работы на 2-ом этаже дубликаты состояний (со штрихами)
и команды со сдвигами в обратном направлении. Для команды q ,a -> r , b ,C из P и для всех $$c\in \Sigma$$ в P'
поместим команды:
$$\ q\,\left(\frac{\frac{\wedge}{c}}{a}\right) \rightarrow\ r
\left(\frac{\frac {\wedge}{c}}{b}\right)\,C\ \ \mbox{ и }
q^\prime\,\left(\frac{\frac {\wedge}{a}}{c}\right) \rightarrow\ r^\prime
\left(\frac{\frac {\wedge}{b}}{c}\right)\,C^\prime,\, \\
\mbox{где }C^\prime =
\left\{ \begin{array}{lcl}
\textit{ П } \mbox { при } C=\textit{Л}\\
\textit{Л } \mbox { при } C=\textit{П}\\
\textit{Н} \mbox { при } C=\textit{Н}
\end{array} \right.$$
Кроме того, для $$a =\wedge$$ сохраним и старые команды для работы на впервые посещаемых ячейках:
$$\ q\,\wedge \rightarrow\ r
\left(\frac{\frac {\wedge}{\wedge}}{b}\right)\,C\ \mbox{ и }
q^\prime\,\wedge \rightarrow\ r^\prime
\left(\frac{\frac {\wedge}{b}}{\wedge}\right)\,C^\prime.$$
Сдвиги $$\cal M\ $$ из 1-ой ячейки налево в -1-ю и обратно моделируются переходом с одного этажа на другой в 1-ой ячейке $$\cal M^\prime$$:
$$\ q\,\left(\frac{\frac{\#}{c}}{a}\right) \rightarrow\ \overline{r}
\left(\frac{\frac {\#}{c}}{b}\right)\,\overline{C}, \mbox{ где при } C=\textit{Л} \overline{r}=r^\prime, \overline{C}= \textit{Н},\\
\mbox { а при } C\neq \textit{Л}\ \ \overline{r}=r, \overline{C}= C \\
\ q^\prime\,\left(\frac{\frac{\#}{a}}{c}\right) \rightarrow\ \overline{r}
\left(\frac{\frac {\#}{b}}{c}\right)\,\overline{C},
\mbox{ где при }C=\textit{П}\ \ \overline{r}=r,\ \overline{C}= \textit{Н},\\
\mbox{ а при } C\neq \textit{П}\ \ \overline{r}=r^\prime, \overline{C}= C.$$
После завершения моделирования $$\cal M\ $$ результат записан
в начальных ячейках на 1-ом этаже. $$\cal M^\prime\ $$ переводит его
в первоначальный алфавит $$\Sigma.$$
$$\ q_f\,\left(\frac{\frac{c}{\wedge}}{a}\right) \rightarrow\ q_f\,a\,\textit{П}
\quad (a \in \Sigma \backslash \{\wedge\},\ c \in \{\wedge, \#\}\ ),\\
\qquad q_f\, \wedge \rightarrow\ q_f^\prime\,\wedge\, \textit{Н}.$$
Проверка правильности работы м.Т. $$\cal M^\prime\ $$ предоставляется
читателю (см. задачу 9.4).
Последовательная и параллельная композиции машин Тьюринга
Используя возможность моделирования произвольной м.Т.
на м.Т. со стандартными заключительными конфигурациями, легко установить
справедливость следующей леммы о последовательной композиции машин Тьюринга.
Лемма 9.3.( Последовательная композиция ) Пусть м.Т. $${\cal M}_1$$ вычисляет функцию f(x),
а м.Т. $${\cal M}_2$$ - функцию g(x). Тогда существует м.Т. $$\cal M,\ $$ вычисляющая функцию h(x) = f(g(x)).
Доказательство Действительно, пусть $$\ {\cal M}_1 = <Q_1, {\Sigma}_1, P_1,q_0^1, q_f^1>,\ $$ а $$\ {\cal M}_2 = <Q_2, {\Sigma}_2, P_2,q_0^2, q_f^2>$$.
Используя лемму 9.1, будем считать, что у $$\ {\cal M}_2$$ заключительные конфигурации стандартны. Тогда легко проверить, что функция h
вычисляется следующей м.Т. $$\ {\cal M} = <Q_1 \cup Q_2, {\Sigma}_1 \cup {\Sigma}_2,
P, q_0^2, q_f^1>,\ $$ где $$P= P_{1} \cup P_{2} \cup \{ q_{f}^{2} a \to q_{0}^{1} aН | a \in \Sigma _{2}\}$$.
Покажем, что работу двух м.Т. можно комбинировать так, чтобы
в заключительной конфигурации содержались результаты работы каждой из
них над независимыми входами.
Лемма 9.4. ( Параллельная композиция ) Пусть м.Т. $${\cal M}_1$$ вычисляет функцию f(x), а м.Т. $${\cal M}_2$$ - функцию g(x) и символ * не входит
в алфавит м.Т. $${\cal M}_1$$. Тогда существует м.Т. $$\cal M,\ $$ которая по любому входу вида x*y
выдает результат f(x)*g(y), т.е.
вычисляет функцию H(x*y) = f(x)*g(y).
Доказательство. Пусть $$\ {\cal M}_1 = <Q_1, {\Sigma}_1, P_1,q_0^1, q_f^1>$$ и $$\ {\cal M}_2 = <Q_2, {\Sigma}_2, P_2,q_0^2, q_f^2>$$ - м.Т. Не ограничивая общности, будем считать, что эти машины односторонние (по Лемме 2). Определим теперь м.Т. $$\ {\cal M} = <Q_1 \cup Q_2 \cup Q^\prime,
{\Sigma}_1 \cup {\Sigma}_2 \cup \{*\},P_1 \cup P_2 \cup P^\prime,
p_0, p_f>$$, которая работает следующим образом.
Начав в конфигурации (p0x*y), находит 1-ый символ y
и переходит в конфигурацию (x*q02y).
Работая как $$\ {\cal M}_2,\ $$ вычисляет g(y) и переходит при этом в конфигурацию (x*qf2g(y)).
Переписывает *x после g(y) и переходит в конфигурацию g(y)*q01x).
Работая как $$\ {\cal M}_1,\ $$ вычисляет f(x) и переходит при этом в конфигурацию (g(y)*qf1f(x).
Меняет $$g(y)$$ и $$f(x)$$ местами и останавливается.
Корректность этапов 2 и 4 следует из односторонности $$\ {\cal M}_2$$ и $${\cal M}_1,\ $$ а реализация этапов 1, 3 и 5 достаточно очевидна (см. задачу 9.6).
Построенную в этой лемме м.Т. $$\ {\cal M}$$, полученную в результате параллельной композиции $$\ {\cal M}_1$$ и $$\ {\cal M}_2$$, будем обозначать
как $$\mathbf{par}_*(\mathcal{M}_1,\mathcal{M}_2)$$. Здесь индекс * указывает
символ, которым отделяются аргументы $$\ {\cal M}_1$$ и $$\ {\cal M}_2$$
на ленте $$\ {\cal M}$$. Этот символ может быть любым символом, не входящим в алфавит
машины $$\ {\cal M}_1$$. Например, $$\mathbf{par}_\#(\mathcal{M}_1,\mathcal{M}_2)$$ будет обозначать параллельную композицию
машин $$\ {\cal M}_1$$ и $$\ {\cal M}_2$$, в которой их аргументы отделены
символом #.
Конструкцию параллельной композиции можно обобщить на произвольное конечное
число машин Тьюринга.
Следствие. Пусть $${\cal M}_1, \ldots , \ {\cal M}_m$$ - машины Тьюринга,
вычисляющие функции f1, ... , fm, соответственно. Пусть символ * не входит в алфавиты этих машин. Тогда существует м.Т. $$\ {\cal M}$$, перерабатывающая любой
вход вида x1*x2* ... *xm $$(x_{i} \in \Sigma _{i}^{*}, i=1,\dots , m)$$
в выход f1(x1)*f2(x2)* ... *fm(xm).
Действительно, в качестве $$\ {\cal M}$$ можно взять м.Т., определяемую
выражением $$\ \mathbf{par}_*(\mathcal{M}_1,\mathbf{par}_*(\mathcal{M}_2, \mathbf{par}_*(\mathcal{M}_3,\ldots
\mathbf{par}_*(\mathcal{M}_{m-1},\mathcal{M}_m)\ldots )))$$.\\
Будем обозначать эту машину Тьюринга как $$\mathbf{par}_*(\mathcal{M}_1,\mathcal{M}_2, \ldots , \mathcal{M}_m)$$.
Ветвление (условный оператор)
Машину Тьюринга $$\Phi$$ будем называть распознающей,
если для некоторого алфавита $$\Sigma$$ и каждого входа $$x \in \Sigma ^{*}$$, на котором $$\Phi$$ останавливается,
ее результат $$\{ \Phi \} (x) \in \{ 0, 1\}$$, т.е. $$\Phi$$ вычисляет
некоторую двузначную функцию (возможно частичную) на словах
из $$\Sigma.$$
Лемма 9.5. Пусть $$\Phi$$ - распознающая м.Т., м.Т. $${\cal M}_1$$ вычисляет функцию f(x),
а м.Т. $${\cal M}_2$$ - функцию g(x). Тогда существует м.Т. $$\cal M,\ $$ вычисляющая функцию
$$h(x) =\left\{ \begin{array}{lcl}
f(x) \mbox { при } \Phi(x)=0 \\
g(x) \mbox { при } \Phi(x)=1
\end{array} \right.$$
Доказательство. Требуемая м.Т. $$\cal M\ $$
вначале копирует вход x и получает на ленте слово x*x, затем вычисляет параллельную композицию функций $$\Phi (x)$$ и тождественной функции e(x)=x и переходит в конфигурацию $$p\{ \Phi \} (x)*x$$. Выбор между f и g происходит
по следующим командам:
$$\ p 0 \rightarrow p_0 \wedge \textit{ П };
\ \ p1 \rightarrow p_1 \wedge \textit{ П};
\ \ p_0* \rightarrow q_0^1 \wedge \textit{ П};
\ \ p_1* \rightarrow q_0^2 \wedge \textit{ П}$$
Кроме того, обеспечим переход в новое заключительное состояние:
$$\ q_f^1 a \rightarrow q_f a \textit{ Н };
\ \ \ q_f^2 a \rightarrow q_f a \textit{ Н}\ \ (a \in \Sigma ).$$
Таким образом, мы реализовали в терминах машин Тьюринга обычный в языках программирования оператор ветвления:
$$\mbox {\bf if }\ \Phi(x)=0\ \mbox {\bf then }\ f(x)
\ \mbox {\bf else }\ g(x)\ \mbox {\bf endif }.$$
Повторение (цикл)
Используя конструкцию для ветвления легко реализовать в терминах машин Тьюринга и оператор цикла.
Лемма 9.6. Пусть $$\Phi$$ - распознающая м.Т., а м.Т. $${\cal M}_1$$ вычисляет функцию f(x).
Тогда существует м.Т. $$\cal N,\ $$ которая вычисляет функцию, задаваемую выражением:
$$g(x) =\ '\mbox {\bf while}\ \Phi(x)= 0\ \mbox {\bf do }\ \ x := f(x)\ \mbox {\bf enddo}'$$
Доказательство. Действительно, пусть м.Т. $${\cal M}_2$$ - вычисляет тождественную функцию g(x)=x. Построим по м.Т. $$\Phi, {\cal M}_1 \mbox { и }\ {\cal M}_2\ $$ м.Т. $$\cal M,\ $$ реализующую ветвление как в лемме 9.5. Тогда
искомая м.Т. $$\cal N\$$ получается из $$\cal M\ $$ заменой команд $$q_{f}^{1} a \to q_{f} a H (a \in \Sigma )$$ на
соответствующие команды $$q_{f}^{1} a \to q_{0} a H (a \in \Sigma )$$,
обеспечивающие зацикливание.
Реализованные выше операции над машинами Тьюринга
и вычислимыми функциями позволяют получать программы новых м.Т., используя обычные конструкции языка программирования
"высокого" уровня: последовательную и параллельную композицию, ветвление и цикл. Пусть $$M, M_{1}, M_{2},\dots , M_{m}, \Phi$$ - машины Тьюринга. Последовательную композицию M1 и M2 будем обозначать M1;M2, параллельную композицию M1, M2,... , Mm
обозначаем как $$\mathbf {par}_b(M_1,M_2,\ldots , M_m)\ $$ (здесь b -
это символ, разделяющий аргументы и результаты этих машин), ветвление -
$${\bf if}\ \Phi\ {\bf then}\ M_1\ {\bf else}\ M_2\ {\bf endif}$$
цикл -
$${\bf while}\ \Phi\ {\bf do }\ M\ {\bf enddo}.$$
Пример 9.4. Рассмотрим в качестве примера задачу
перевода чисел из унарной системы счисления в двоичную.
Пусть fub(|n) = n(2) для всех $$n \in N$$, где n(2) - двоичная запись числа n.
Пусть M1 - м.Т., которая начальную конфигурацию q0 ,|n переводит в конфигурацию q1 ,0*|n; M2 - м.Т., которая прибавляет 1 к двоичному
числу-аргументу (см. пример ref{ex8-suc}); M3 - м.Т., которая вычитает 1 из унарного
числа; $$\Phi$$ - м.Т., которая на аргументе вида x*|y выдает
0, если число y > 0, и выдает 1 при y=0 (т.е. на аргументе $$x*\wedge$$); M4 - м.Т., которая стирает * в аргументе вида x* и
останавливается. Реализация каждой из указанных м.Т. очевидна.
Теперь требуемая м.Т. Mub, вычисляющая fub, получается как
$$M_1; {\bf while}\ \Phi\ \mathbf{ do\ \ par}_*(M_2,M_3)\ {\bf enddo}; M_4.$$
Действительно, после работы M1 получаем конфигурацию q10*|n. Предположим теперь по индукции, что после i (i <n) итераций цикла
while получается конфигурация q1 i(2)*|n-i.
Тогда на (i+1) -ой итерации цикла после параллельного
применения M2 к i(2) и M3 к |n-i
получаем конфигурацию q1(i+1)(2)*|n-i-1.
Поэтому после n итераций получится конфигурация $$q_{1} n_{(2)}*\wedge$$. На ней $$\Phi$$ выдаст 1, и цикл завершится с записью $$n_{(2)}*\wedge$$ на ленте,
из которой M4 сотрет * и оставит требуемый результат n(2).
Отметим, что из приведенного примера и из задачи \oldref{prb3-6}(a) следует,
что класс вычислимых на м.Т. арифметических функций не зависит от
выбора унарного или двоичного кодирования аргументов и результатов.
Это же справедливо и для троичной, десятичной и других позиционных
систем счисления ( почему ?).
Задачи
Задача 9.1. Постройте м.Т. для функции копирования, не
увеличивая исходный алфавит $$\Sigma.$$
Задача 9.2. Постройте программу м.Т., которая выполняла бы
перенос непустого слова в заданное место ленты, т.е. для любого
слова $$w \in (\Sigma \setminus \{ \wedge \} )^{*}$$ и n > 0 выполняла
преобразование конфигураций: $$q_1w \wedge^n \#\ \vdash^*\ \wedge^n q_2\#w\$$.
Задача 9.3. Достройте программу м.Т. $${\cal M}^\prime\ $$ из леммы 9.1 на этапах 3 и 4.
Задача 9.4. Докажите, что односторонняя м.Т. $${\cal M}^\prime,\ $$ построенная в лемме 9.2, корректно моделирует исходную м.Т. $${\cal M}$$.
Задача 9.5. Другой, по сравнению с конструкцией леммы 9.2,
подход к моделированию двухсторонней ленты на
односторонней заключается в том, чтобы содержимое правой полуленты $$\cal M\$$ хранить в четных ячейках $$\cal M^\prime,\$$ а содержимое
левой полуленты - в нечетных, поместив в 1-ю ячейку специальный маркер.
Постройте программу, реализующую этот подход (ее достоинство -
увеличение алфавита ленты всего на 1 символ).
Задача 9.6. Достройте программу м.Т. $$\cal M$$ из
леммы 9.4 на этапах 1, 3 и 5.
Задача 9.7. Построить программы машин Тьюринга, вычисляющих следующие
функции.
Перевод из двоичной системы в унарную: fbu(n(2))= |n.
Сложение и вычитание в двоичной системе: sum(n*m)=n+m и $$sub(n*m)= n \dot - m,\ ( \dot - $$ совпадает с - при n >= m и $$n \dot - m =0$$ при m > n ).
Умножение в двоичной системе: mul(n*m)= n x m. ( Реализуйте алгоритм умножения "в столбик".)
Возведение в степень: exp(n*m)= nm.
Извлечение квадратного корня: $$sqr(n) =\lfloor\sqrt{n}\rfloor$$.
Логарифмирование: $$log(n)=\lfloor log_{2n} \rfloor$$.
Деление: $$div(n*m) =\lfloor \frac{n}{ m} \rfloor\ (m \neq 0)$$.
Остаток от деления: rest(n*m) = n mod m.
Функция выбора аргумента: $$I_m^n(|^{x_1}*|^{x_2}*\ldots *|^{x_n})= |^{x_m}\ \ (1\leq m \leq n)$$.
Задача 9.8. Используя машины Тьюринга из предыдущей
задачи, построить программы машин Тьюринга, вычисляющих следующие
функции.
$$\begin{array}{lll}
f_1(x, y) = \left \{\begin{array}{ll}
x^2y^3, \mbox{ если }\ x < y \\
\lfloor (x+y)/2 \rfloor , \mbox{ в противном случае}
\end{array} \right. \\
\end{array}$$
$$\begin{array}{lll}
f_2(x, y) = \left \{\begin{array}{ll}
\lfloor \sqrt{x}\ \rfloor , \mbox{ если } x+1 \geq y \\
2(x +y), \mbox{ в противном случае}
\end{array} \right. \\
\end{array}$$
$$\begin{array}{lll}
f_3(x, y) = \left \{\begin{array}{ll}
\lfloor \log_2 (1+ \lfloor \frac{x}{ y} \rfloor)\ \rfloor, \mbox{ если } x > 2 y\\
xy, \mbox{ в противном случае}
\end{array} \right. \\
\end{array}$$
$$\begin{array}{lll}
f(x, y) = \left \{\begin{array}{ll}
\lfloor \sqrt{x}\ \rfloor , \mbox{ если } 2x \geq y \\
(x\ mod\ y), \mbox{ в противном случае}
\end{array} \right. \\
\end{array}$$
Задача 9.9. Докажите, что всякую арифметическую функцию f(x),
вычислимую на некоторой м. Т. $$M = <Q, \Sigma , P,q_{0}, q_{f}>$$, можно также вычислить на м. Т. M',, алфавит ленты которой содержит лишь два символа $$\wedge$$ и |. (Указание: используйте для моделирования
одного символа из $$\Sigma$$ блок из нескольких подряд идущих ячеек,
содержащих его код в алфавите $$\{ \wedge , , | \}$$ ) и замените
каждую команду M группой команд, обрабатывающих соответствующий
блок ячеек).
Задача 9.10.
Построить машину Тьюринга, определяющую по слову x в алфавите {1, 2} симметрично ли оно,
т. е. вычисляющую функцию:
$$f(x) = \left \{\begin{array}{ll}
1, \mbox{ если слово x симметрично}\\
2, \mbox{ в противном случае}
\end{array} \right.$$
Задача 9.11.
Построить машину Тьюринга, сравнивающую два слова x=x1x2... xn и y=y1y2... ym в алфавите {1, 2, 3} лексикографически: $$x \prec y \Leftrightarrow\ \exists i \leq n [(x_1=y_1)\ \\ ( x_2=y_2)\ \ \ldots\ (x_{i-1}=y_{i-1})
\ \\ ( x_i < y_i )]$$ или для некоторого непустого слова x' выполнено y = x x'.
Эта машина Тьюринга должна вычислять функцию:
$$f(x, y) = \left \{\begin{array}{ll}
1 , \text{ если $x \prec y$ }\\
2 , \text{ если $x = y$ }\\
3 , \text{ если $y \prec x$ }
\end{array} \right.$$
Основные определения
Рассматриваемая в этом разделе модель алгоритмов была предложена
английским математиком Тьюрингом в 1937 г. еще до создания современных компьютеровАналогичная модель вычислений была примерно в то же время определена Е. Постом. Поэтому иногда такие машины называют машинами Тьюринга-Поста
Он исходил из общей идеи моделирования работы вычислителя,
оперирующего в соответствии с некоторым строгим предписанием.
В машине Тьюринга расчленение процесса вычисления на элементарные шаги доведено
в известном смысле до предела. Элементарным действием является замена одного символа
в ячейке на другой и перемещение к соседней ячейке. При таком подходе процесс вычисления значительно удлиняется, но зато логическая структура процесса
сильно упрощается и приобретает удобный для теоретического исследования вид.
Машина Тьюринга (м.Т.) состоит из неограниченной в обе стороны ленты,
разбитой на ячейки, по которой передвигается головка машины.
Такая "бесконечность" ленты является математической абстракцией,
отражающей потенциальную неограниченность памяти вычислителя.
Разумеется, в каждом завершающемся вычислении используется только конечная часть
этой памяти - конечное число ячеек.
В каждой
ячейке ленты записан один символ из конечного внешнего алфавита машины $$\Sigma = \{ a_{0}, a_{1}, \dots ,a_{m} \}$$. Головка машины представляет конечный автомат,
который в каждый момент
времени находится в одном из внутренних состояний Q ={q0,q1,... ,
qn }. На каждом шаге головка в зависимости от своего
внутреннего состояния и символа в ячейке, которую она наблюдает,
изменяет свое внутреннее состояние и содержимое наблюдаемой ячейки
и может сдвинуться на одну ячейку вправо или влево либо остаться
на месте.
Дадим более формальное определение.
Определение 9.1. Машина Тьюринга - это система вида
$${\cal M} = < Q, \Sigma, P,q_0, q_f >,$$
включающая следующие компоненты:
Q ={q0,q1,... ,qn } - внутренний алфавит (алфавит состояний);
$$\Sigma = \{ a_{0}, a_{1}, \dots , a_{m-1} \}$$ - внешний алфавит (алфавит ленты );
P - программа машины, в которой для каждой пары $$q_{i} \in Q \setminus \{ q_{f} \} , a_{j} \in \Sigma$$ имеется (одна!) команда вида
$$q_i a_j \rightarrow q_k a_l C,\ q_k \in Q, a_l \in \Sigma,$$
$$C \in \{ Л, П, Н\}$$ задает сдвиг головки вправо, влево или на месте;
$$q_{0} \in Q$$ - начальное состояние;
$$q_{f} \in Q$$ - заключительное состояние.
Выделим в алфавите $$\Sigma$$ специальный пустой символ $$a_{0} =\wedge$$ и будем считать, что во всех ячейках ленты, кроме конечного их числа, в начальный и во все последующие моменты находится пустой символ.
Будем говорить, что некоторый символ стирается, если он заменяется на пустой. Два слова из $$\Sigma ^{*}$$ будем считать равными, если они совпадают после
отбрасывания всех пустых символов слева и справа. Например, $$\wedge \wedge ab\wedge c\wedge =\wedge ab\wedge c = ab\wedge c$$, но $$ab \wedge c \ne abc$$.
Как и для конечных автоматов, программу P можно задавать с помощью таблицы
размера n x m, строки которой соответствуют состояниям из Q,
а столбцы - символам из входного алфавита $$\Sigma,$$ в которой на пересечении строки qi и столбца aj стоит тройка qk al C - правая часть команды qi aj -> qk al C.
Определение 9.2. Назовем конфигурацией м.Т. $${\cal M }\ $$ в некоторый момент времени слово K= wл qi aj wп, где $$w_{л} \in \Sigma ^{*}$$ - слово на ленте левее текушего положения головки, qi - внутреннее состояние в данный момент, aj - символ, обозреваемый головкой, $$w_{п} \in \Sigma ^{*}$$ - слово на ленте правее текушего положения головки.
Будем считать, что слово wл aj wп содержит
все значащие символы на ленте. Поэтому, с точностью до
описанного выше равенства слов, конфигурация определена однозначно.
В частности, если $$w_{л}=\varepsilon$$, т.е. пусто, то левее положения головки все ячейки пусты, а если $$w_{п}=\varepsilon$$, то
правее положения головки все ячейки пусты.
Начальная конфигурация - это конфигурация вида q0w, т.е.
в начальный момент времени головка в состоянии q0 обозревает
первый символ входного слова w. { it Заключительная } конфигурация - это конфигурация вида w1 qf w2, в которой машина находится в
заключительном состоянии qf.
Определение 9.3. Скажем, что конфигурация K= w1 qi aj w2 м.Т. $${\cal M }$$ за один шаг (такт) переходит в конфигурацию $$K^\prime= w_1^\prime q_k a_{j^\prime} w_2^\prime\ (K \vdash_{\cal M } K^\prime)$$, если в программе имеется команда qi aj -> qk al C и при этом,
если С=Н, то w1'=w1, w2'=w2 и a{j'}=al;
если С=Л, то w1=w1' a, a{j'}=a, w2'=al w2 (если $$w_{1}=\varepsilon , /$$ то $$w_{1}^{'} = \varepsilon$$ и $$a_{j^'} =\wedge$$);
если С=П, то w2=aw2', a{j'}=a, w1'=w1 al (если $$w_{2}=\varepsilon , /$$ то $$w_{2}^{'} = \varepsilon$$ и $$a_{j^'} =\wedge$$).
Как обычно, через $$\vdash^*_{\cal M }$$ обозначим рефлексивное и транзитивное
замыкание отношения $$\vdash_{\cal M },\ $$ а $$K \vdash^n_{\cal M } K^\prime$$ будет
означать, что конфигурация K за n шагов переходит в K'.
(Если из контекста ясно, о какой машине идет речь, то
индекс $${\cal M }$$ будем опускать).
Пример 9.1.
(рис 9.1) Выполнение команды q3 0 -> q5 1 П Например, ситуации, представленной на рис.9.1 слева соответствует конфигурация $$K= 1q_{3}01\wedge 0$$. Предположим, что программа P содержит команду q30 -> q51 П. Тогда после выполнения этой команды K перейдет за один шаг в конфигурацию $$K^{'}= 11q_{5}1\wedge 0$$, показанную на этом рисунке
справа. Следовательно, $$K \vdash K^\prime$$.
Определение 9.4. Вычисление м.Т. $${\cal M}\ $$ на входе w - это конечная или
бесконечная последовательность конфигураций $$K_0 \vdash K_1 \vdash\ldots \vdash K_t\vdash K_{t+1}\ldots $$
такая, что K0=q0w - начальная конфигурация.
Эта последовательность конечна, когда
ее последняя конфигурация Kn= v1 qf v2 - заключительная.
В этом случае вычисление назовем результативным, а слово v = v1 v2 -
его результатом на входе w (всегда будем предполагать, что v не
содержит пустых символов слева и справа).
Определение 9.5. Скажем, что м.Т. $${\cal M}\ $$ вычисляет частичную словарную функцию $$f:\ \Sigma^* \rightarrow \Sigma^*,\ $$ если для каждого слова w из области определения f существует результативное вычисление $${\cal M}\$$ с результатом $$f(w)$$, а если f(w) не определена $$(f(w)=\infty)$$, то вычисление $${\cal M}\ $$ на входе w бесконечно.
Скажем, что две м.Т. $${\cal M}_1$$ и $${\cal M}_2\ $$ эквивалентны, если они вычисляют одинаковые функции.
Далее мы будем также рассматривать вычисления арифметических функций, т.е. функций с натуральными аргументами, принимающих натуральные значения. Для представления натуральных чисел используем унарное кодирование: число n будет представляться как слово из n палочек |n, а последовательные аргументы будем отделять *.
Определение 9.6. Скажем, что м.Т. $${\cal M}\ $$ вычисляет частичную арифметическую функцию f: Nk -> N, если для любого набора чисел (x1,x2, ... ,xk), на котором f определена, существует
результативное вычисление $${\cal M}\ $$ на входе $$|^{x_1}* |^{x_2}*\ldots * |^{x_k}$$ с результатом $$|^{f(x_1,x_2,\ldots ,x_k)}$$,
а если $$f(x_{1},x_{2},\dots ,x_{k})=\infty$$,
то вычисление $${\cal M}\$$ на соответствующем входе бесконечно.
Аналогичное определение можно дать и для других спосбов кодирования
чисел (двоичного, десятичного и др.). Ниже мы покажем, что класс
вычислимых функций не зависит от выбора одного из таких кодирований.
Тьюрингово программирование
В этом разделе мы приведем примеры вычислений на машинах Тьюринга
и рассмотрим некоторые общие приемы, позволяющие комбинировать программы
различных м. Т. для получения более сложных вычислений. Будем считать, что
ячейки ленты м.Т. занумерованы от $$-\infty$$ до $$+\infty$$, причем
в начальной конфигурации головка находится в 1-ой ячейке:
(рис 9.2) Нумерация ячеек ленты машины ТьюрингаПример 9.2.Функция f(x)=x+1
Унарное кодирование.
Пусть м.Т. $${\cal M}_1=<\{q_0,q_f \},\{\wedge,|\},P_1,q_0,q_f>$$, где $$P_{1}: q_{0} |\to q_{0} | П, q_{0} \wedge \to q_{f} | Н$$.
Ясно, что м.Т. $${\cal M}_1$$ проходит по массиву палочек слева направо и записывает в первой пустой ячейке новую |.
Бинарное кодирование.
Пусть м.Т. $${\cal M}_1^\prime=<\{q_0,q_1,q_f \},\{\wedge,0,1\}, P_1^\prime,q_0,q_f>$$, где $$P_1^\prime$$:
$$q_0 0\rightarrow q_0 0 \textit{П},\ \ q_0 1\rightarrow q_0 1 \textit{П},\ \ q_0 \wedge \rightarrow q_1 \wedge \textit{Л},\\q_1 0\rightarrow q_f 1 \textit{Н},\ \ q_1 1\rightarrow q_1 0 \textit{П},\ \ q_1 \wedge \rightarrow q_f 1 \textit{Н}.$$
Нетрудно видеть, что эта машина в состоянии q0 находит младший разряд двоичного входа, затем в состоянии q1, идя справа налево, заменяет единицы на нули до тех пор, пока не
находит 0 (или $$\wedge$$ ) и заменяет его на 1. Следовательно, м.Т. $${\cal M}_1^\prime\ $$ вычисляет функцию f(x) = x+1.
Пример 9.2. Копирование.
Рассмотрим функцию копирования (дублирования) слов в алфавите $$\Sigma : copy(x)= x \times x$$ (мы предполагаем, что $$* \notin \Sigma$$ ).
Для ее реализации используем один из типичных приемов Тьюрингова программирования - { it расширение алфавита}.Пусть $$\Sigma ^{'}= \{ a^{'} | a \in \Sigma \}$$ и $$\Sigma _{1}=\Sigma \cup \Sigma ^{'}$$. М.Т. $${\cal M}_2$$, копирующая вход, работает следующим образом:
отмечает 1-ый символ входа, идет направо, ставит * после входа и возвращается в начало:$$q_0 a \rightarrow q_1 a^\prime \textit{П}\ (a \in \Sigma); \ q_1 a \rightarrow q_1 a \textit{П}\ (a \in \Sigma \backslash \{\wedge\}; \ q_1 \wedge \rightarrow q_2 * \textit{Л}; \\ q_2 a \rightarrow q_2 a \textit{Л}\ (a \in \Sigma \cup \{*\}); \ q_2 a^\prime \rightarrow q_a a^\prime \textit{П}\ (a \in \Sigma );$$
в состоянии qa движется направо и записывает a в первую свободную ячейку:$$q_a b \rightarrow q_a b \textit{П}\ (b \in \Sigma \cup \{*\}); \ \ q_a \wedge \rightarrow q_4 a \textit{Л}\;$$
возвращается в отмеченную ячейку и передвигает метку ' на одну ячейку вправо, снова переходя в состояние q2:$$q_4 a \rightarrow q_4 a \textit{Л}\ (a \in \Sigma \cup \{*\}); \ q_4 a^\prime \rightarrow q_5 a \textit{П}\ (a \in \Sigma ); \ q_5 a \rightarrow q_2 a^\prime \textit{Н}\ (a \in \Sigma );$$
увидев символ * в состоянии q5, останавливается:$$q_5 * \rightarrow q_f*\textit{Н}.$$
Из этого описания непосредственно следует, что $$q_0x {\vdash}^* xq_f*x$$ для любого $$x \in \{ \Sigma \} ^{*}$$.
Стандартная заключительная конфигурация
Назовем заключительную конфигурацию стандартной, если в ней головка наблюдает первый значащий символ результата, который находится
в 1-ой ячейке (т.е. в той же ячейке, где начиналось входное слово).
Лемма 9.1.Для всякой м.Т. $${\cal M}\ $$ можно построить
эквивалентную м.Т. $${\cal M}^\prime$$, у которой все заключительные конфигурации стандартны.
Доказательство. Пусть $${\cal M} = <Q, \Sigma, P,q_0, q_f>$$. Определим по ней м.Т. $$\ {\cal M}^\prime = <Q^\prime, \Sigma^\prime, P^\prime,q_0^\prime, q_f^\prime>$$, которая удовлетворяет требованиям
леммы. Положим $$\Sigma ' = \Sigma \cup \{ a' | a \in \Sigma \} \cup \{ #\}$$, где # - новый символ. $${\cal M}^\prime\ $$ работает
следующим образом.
Отмечает символ в первой ячейке штрихом и переходит в начальное состояние $${\cal M}:\ \ q_0^\prime a \rightarrow q_0 a^\prime \textit{Н}$$.
Далее работает как $${\cal M},\ $$ но сохраняет штрих в первой ячейке и вместо пустого символа $$\wedge$$ записывает #. Для этого для каждой команды qiaj -> qk alC из P'
в P' добавляется ее дубликат qiaj' -> qk al'C, в правых частях команд символ $$\wedge$$ всюду заменяется на # и для каждой команды вида $$q_{i} \wedge \to q_{k} a_{l} C$$ в P' добавляется команда qi # -> qk al C. После завершения этого этапа все посещенные в процессе работы головкой $${\cal M}\$$ ячейки составляет непрерывный отрезок, не содержащий пустых символов.
Далее $${\cal M}^\prime\ $$ стирает ненужные символы # слева и справа от блока ячеек, содержащего первую ячейку и все ячейки с символами результата, и переходит в одну из трех следующих конфигураций:$$K_1= q_\textit{л} \#^\prime \#\ldots \# w\wedge,\ \ K_2=\wedge q_\textit{п} w \# \ldots \#\#^\prime, \ \ K_3 =\wedge q_\textit{н} w_1 a^\prime w_2\wedge,$$
где w - результат работы { cal M} (с заменой символов $$\wedge$$ внутри w на #) и w1aw2 = w.
Сдвигает в нужном направлении результат, совмещая его начало с ячейкой, помеченной штрихом, заменяет все # внутри w на $$\wedge$$ , снимает штрих в 1-ой ячейке и останавливается. Например, для K1 это достигается с помощью следующих команд (мы предполагаем, что ни одно из используемых ниже состояний $$q_{л}, q_{1}, p, p_{1}, p_{2}, p_{3}, p^{a}, p^{a'} (a \in \Sigma \cup \{ #\} )$$ не входит в Q ):поиск левого конца w: $$q_{л} a \to q_{л}aП (a \in \{ \#', \#\} )$$ ; $$q_{л}a \to q_{1}a'П (a \in \Sigma )$$ (отметили первый символ w ), $$q_{л} \wedge \to p_{3} \wedge Л;$$ (результат пуст);
поиск правого конца w: $$q_{1} a \to q_{1}aП (a \in \Sigma \cup \{ #\} )$$, $$q_{1} \wedge \to p \wedge Л$$ (в состоянии p наблюдает последний символ w );
сдвиг результата на 1 ячейку влево: $$pa \to p^{a} \wedge Л; p^{a} b \to p^{b} aЛ;$$ pa b' -> pb'aП; pb' # -> p1 b'П;
возврат к правому концу и переход к следующему сдвигу: $$p_{1} a \to p_{1}aП (a \ne \wedge ); p_{1}\wedge \to p \wedge Л;$$
при сдвиге до 1-ой ячейки замена символов # на $$\wedge$$ и удаление
штриха:$$p^{a\prime} \#^\prime \rightarrow p_2 a^\prime \textit{Н}; p_2 b \rightarrow p_2 b \textit{П};\\ p_2 \wedge \rightarrow p_3 \wedge \textit{Л};\\
p_3 \# \rightarrow p_3 \wedge \textit{Л}; \ \ p_3 b \rightarrow p_3 b \textit{П}\ (b \neq \#, b \neq a^\prime) ;
\ \ p_3 a^\prime \rightarrow q_f^\prime a \textit{Н}.$$
Из построения непосредственно следует, что м.Т. $${\cal M}^\prime\ $$ удовлетворяет требованиям леммы.
Односторонние машины Тьюринга
Машина Тьюринга $${\cal M}\ $$ называется односторонней,
если в процессе вычисления ее головка никогда не сдвигается левее
начальной ячейки (т.е. всегда находится в ячейках с положительными
номерами).
Лемма 9.2. Для всякой м.Т. $$\cal M$$ можно построить
эквивалентную одностороннюю м.Т. $${\cal M}^\prime\ $$.
Доказательство. Пусть $$\ {\cal M} = <Q, \Sigma, P,q_0, q_f>$$. Будем считать (используя лемму 1 ), что $$\cal M\ $$ завершает работу в стандартных конфигурациях. Требуемая м.Т. $$\ {\cal M}^\prime = <Q^\prime, \Sigma^\prime,
P^\prime,q_0^\prime, q_f^\prime>\ $$ будет моделировать работу $$\cal M$$, используя "многоэтажную" ленту. Содержимое ячеек
на 1-ом (нижнем) этаже будет на каждом такте совпадать с содержимым
тех же ячеек $$\cal M$$, на 2-ом этаже будет копироваться
содержимое левой полуленты: на нем в i -ой ячейке $${\cal M}^\prime\ $$
будет тот же символ, что и в -i -ой ячейке $$\cal M$$. Кроме того,
на 3-ем этаже в 1-ой ячейке будет стоять отмечающий ее символ #.
Таким образом, $$\Sigma ' = \Sigma x \Sigma x \{ \wedge , # \} \cup \Sigma$$. Работа $${\cal M}^\prime\ $$ будет происходить следующим образом.
1) На первом этапе отмечается 1-я ячейка и содержимое входа переписывается на 1-ый этаж трехэтажной ленты:$$q_0^\prime a \rightarrow p_1 \left(\frac{\frac {\#}{\wedge}}{a}\right)\textit{П}\ \ (a \in
\Sigma);\qquad p_1 a \rightarrow p_1 \left(\frac{\frac {\wedge}{\wedge}}{a}\right)\textit{П}\ (
a \in \Sigma \backslash \{\wedge \};\\\qquad p_1 \wedge \rightarrow p_2\,\wedge\, \textit{Л};\\
\ p_2 \left( \frac{\frac {\wedge}{\wedge}}{a} \right) \rightarrow
p_2 \left(\frac{\frac {\wedge}{\wedge}}{a} \right)\,\textit{Л}\ \ (a \in \Sigma);\ \ p_2
\left(\frac{\frac {\#}{\wedge}}{a}\right) \rightarrow
q_0 \left(\frac{\frac {\#}{\wedge}}{a}\right)\textit{Л}\ \ (a \in \Sigma).$$
Затем $${\cal M}^\prime\ $$ моделирует работу $$\cal M\ $$,
используя для работы на 2-ом этаже дубликаты состояний (со штрихами)
и команды со сдвигами в обратном направлении. Для команды q ,a -> r , b ,C из P и для всех $$c\in \Sigma$$ в P'
поместим команды:
$$\ q\,\left(\frac{\frac{\wedge}{c}}{a}\right) \rightarrow\ r
\left(\frac{\frac {\wedge}{c}}{b}\right)\,C\ \ \mbox{ и }
q^\prime\,\left(\frac{\frac {\wedge}{a}}{c}\right) \rightarrow\ r^\prime
\left(\frac{\frac {\wedge}{b}}{c}\right)\,C^\prime,\, \\
\mbox{где }C^\prime =
\left\{ \begin{array}{lcl}
\textit{ П } \mbox { при } C=\textit{Л}\\
\textit{Л } \mbox { при } C=\textit{П}\\
\textit{Н} \mbox { при } C=\textit{Н}
\end{array} \right.$$
Кроме того, для $$a =\wedge$$ сохраним и старые команды для работы на впервые посещаемых ячейках:
$$\ q\,\wedge \rightarrow\ r
\left(\frac{\frac {\wedge}{\wedge}}{b}\right)\,C\ \mbox{ и }
q^\prime\,\wedge \rightarrow\ r^\prime
\left(\frac{\frac {\wedge}{b}}{\wedge}\right)\,C^\prime.$$
Сдвиги $$\cal M\ $$ из 1-ой ячейки налево в -1-ю и обратно моделируются переходом с одного этажа на другой в 1-ой ячейке $$\cal M^\prime$$:
$$\ q\,\left(\frac{\frac{\#}{c}}{a}\right) \rightarrow\ \overline{r}
\left(\frac{\frac {\#}{c}}{b}\right)\,\overline{C}, \mbox{ где при } C=\textit{Л} \overline{r}=r^\prime, \overline{C}= \textit{Н},\\
\mbox { а при } C\neq \textit{Л}\ \ \overline{r}=r, \overline{C}= C \\
\ q^\prime\,\left(\frac{\frac{\#}{a}}{c}\right) \rightarrow\ \overline{r}
\left(\frac{\frac {\#}{b}}{c}\right)\,\overline{C},
\mbox{ где при }C=\textit{П}\ \ \overline{r}=r,\ \overline{C}= \textit{Н},\\
\mbox{ а при } C\neq \textit{П}\ \ \overline{r}=r^\prime, \overline{C}= C.$$
После завершения моделирования $$\cal M\ $$ результат записан
в начальных ячейках на 1-ом этаже. $$\cal M^\prime\ $$ переводит его
в первоначальный алфавит $$\Sigma.$$
$$\ q_f\,\left(\frac{\frac{c}{\wedge}}{a}\right) \rightarrow\ q_f\,a\,\textit{П}
\quad (a \in \Sigma \backslash \{\wedge\},\ c \in \{\wedge, \#\}\ ),\\
\qquad q_f\, \wedge \rightarrow\ q_f^\prime\,\wedge\, \textit{Н}.$$
Проверка правильности работы м.Т. $$\cal M^\prime\ $$ предоставляется
читателю (см. задачу 9.4).
Последовательная и параллельная композиции машин Тьюринга
Используя возможность моделирования произвольной м.Т.
на м.Т. со стандартными заключительными конфигурациями, легко установить
справедливость следующей леммы о последовательной композиции машин Тьюринга.
Лемма 9.3.( Последовательная композиция ) Пусть м.Т. $${\cal M}_1$$ вычисляет функцию f(x),
а м.Т. $${\cal M}_2$$ - функцию g(x). Тогда существует м.Т. $$\cal M,\ $$ вычисляющая функцию h(x) = f(g(x)).
Доказательство Действительно, пусть $$\ {\cal M}_1 = <Q_1, {\Sigma}_1, P_1,q_0^1, q_f^1>,\ $$ а $$\ {\cal M}_2 = <Q_2, {\Sigma}_2, P_2,q_0^2, q_f^2>$$.
Используя лемму 9.1, будем считать, что у $$\ {\cal M}_2$$ заключительные конфигурации стандартны. Тогда легко проверить, что функция h
вычисляется следующей м.Т. $$\ {\cal M} = <Q_1 \cup Q_2, {\Sigma}_1 \cup {\Sigma}_2,
P, q_0^2, q_f^1>,\ $$ где $$P= P_{1} \cup P_{2} \cup \{ q_{f}^{2} a \to q_{0}^{1} aН | a \in \Sigma _{2}\}$$.
Покажем, что работу двух м.Т. можно комбинировать так, чтобы
в заключительной конфигурации содержались результаты работы каждой из
них над независимыми входами.
Лемма 9.4. ( Параллельная композиция ) Пусть м.Т. $${\cal M}_1$$ вычисляет функцию f(x), а м.Т. $${\cal M}_2$$ - функцию g(x) и символ * не входит
в алфавит м.Т. $${\cal M}_1$$. Тогда существует м.Т. $$\cal M,\ $$ которая по любому входу вида x*y
выдает результат f(x)*g(y), т.е.
вычисляет функцию H(x*y) = f(x)*g(y).
Доказательство. Пусть $$\ {\cal M}_1 = <Q_1, {\Sigma}_1, P_1,q_0^1, q_f^1>$$ и $$\ {\cal M}_2 = <Q_2, {\Sigma}_2, P_2,q_0^2, q_f^2>$$ - м.Т. Не ограничивая общности, будем считать, что эти машины односторонние (по Лемме 2). Определим теперь м.Т. $$\ {\cal M} = <Q_1 \cup Q_2 \cup Q^\prime,
{\Sigma}_1 \cup {\Sigma}_2 \cup \{*\},P_1 \cup P_2 \cup P^\prime,
p_0, p_f>$$, которая работает следующим образом.
Начав в конфигурации (p0x*y), находит 1-ый символ y
и переходит в конфигурацию (x*q02y).
Работая как $$\ {\cal M}_2,\ $$ вычисляет g(y) и переходит при этом в конфигурацию (x*qf2g(y)).
Переписывает *x после g(y) и переходит в конфигурацию g(y)*q01x).
Работая как $$\ {\cal M}_1,\ $$ вычисляет f(x) и переходит при этом в конфигурацию (g(y)*qf1f(x).
Меняет $$g(y)$$ и $$f(x)$$ местами и останавливается.
Корректность этапов 2 и 4 следует из односторонности $$\ {\cal M}_2$$ и $${\cal M}_1,\ $$ а реализация этапов 1, 3 и 5 достаточно очевидна (см. задачу 9.6).
Построенную в этой лемме м.Т. $$\ {\cal M}$$, полученную в результате параллельной композиции $$\ {\cal M}_1$$ и $$\ {\cal M}_2$$, будем обозначать
как $$\mathbf{par}_*(\mathcal{M}_1,\mathcal{M}_2)$$. Здесь индекс * указывает
символ, которым отделяются аргументы $$\ {\cal M}_1$$ и $$\ {\cal M}_2$$
на ленте $$\ {\cal M}$$. Этот символ может быть любым символом, не входящим в алфавит
машины $$\ {\cal M}_1$$. Например, $$\mathbf{par}_\#(\mathcal{M}_1,\mathcal{M}_2)$$ будет обозначать параллельную композицию
машин $$\ {\cal M}_1$$ и $$\ {\cal M}_2$$, в которой их аргументы отделены
символом #.
Конструкцию параллельной композиции можно обобщить на произвольное конечное
число машин Тьюринга.
Следствие. Пусть $${\cal M}_1, \ldots , \ {\cal M}_m$$ - машины Тьюринга,
вычисляющие функции f1, ... , fm, соответственно. Пусть символ * не входит в алфавиты этих машин. Тогда существует м.Т. $$\ {\cal M}$$, перерабатывающая любой
вход вида x1*x2* ... *xm $$(x_{i} \in \Sigma _{i}^{*}, i=1,\dots , m)$$
в выход f1(x1)*f2(x2)* ... *fm(xm).
Действительно, в качестве $$\ {\cal M}$$ можно взять м.Т., определяемую
выражением $$\ \mathbf{par}_*(\mathcal{M}_1,\mathbf{par}_*(\mathcal{M}_2, \mathbf{par}_*(\mathcal{M}_3,\ldots
\mathbf{par}_*(\mathcal{M}_{m-1},\mathcal{M}_m)\ldots )))$$.\\
Будем обозначать эту машину Тьюринга как $$\mathbf{par}_*(\mathcal{M}_1,\mathcal{M}_2, \ldots , \mathcal{M}_m)$$.
Ветвление (условный оператор)
Машину Тьюринга $$\Phi$$ будем называть распознающей,
если для некоторого алфавита $$\Sigma$$ и каждого входа $$x \in \Sigma ^{*}$$, на котором $$\Phi$$ останавливается,
ее результат $$\{ \Phi \} (x) \in \{ 0, 1\}$$, т.е. $$\Phi$$ вычисляет
некоторую двузначную функцию (возможно частичную) на словах
из $$\Sigma.$$
Лемма 9.5. Пусть $$\Phi$$ - распознающая м.Т., м.Т. $${\cal M}_1$$ вычисляет функцию f(x),
а м.Т. $${\cal M}_2$$ - функцию g(x). Тогда существует м.Т. $$\cal M,\ $$ вычисляющая функцию
$$h(x) =\left\{ \begin{array}{lcl}
f(x) \mbox { при } \Phi(x)=0 \\
g(x) \mbox { при } \Phi(x)=1
\end{array} \right.$$
Доказательство. Требуемая м.Т. $$\cal M\ $$
вначале копирует вход x и получает на ленте слово x*x, затем вычисляет параллельную композицию функций $$\Phi (x)$$ и тождественной функции e(x)=x и переходит в конфигурацию $$p\{ \Phi \} (x)*x$$. Выбор между f и g происходит
по следующим командам:
$$\ p 0 \rightarrow p_0 \wedge \textit{ П };
\ \ p1 \rightarrow p_1 \wedge \textit{ П};
\ \ p_0* \rightarrow q_0^1 \wedge \textit{ П};
\ \ p_1* \rightarrow q_0^2 \wedge \textit{ П}$$
Кроме того, обеспечим переход в новое заключительное состояние:
$$\ q_f^1 a \rightarrow q_f a \textit{ Н };
\ \ \ q_f^2 a \rightarrow q_f a \textit{ Н}\ \ (a \in \Sigma ).$$
Таким образом, мы реализовали в терминах машин Тьюринга обычный в языках программирования оператор ветвления:
$$\mbox {\bf if }\ \Phi(x)=0\ \mbox {\bf then }\ f(x)
\ \mbox {\bf else }\ g(x)\ \mbox {\bf endif }.$$
Повторение (цикл)
Используя конструкцию для ветвления легко реализовать в терминах машин Тьюринга и оператор цикла.
Лемма 9.6. Пусть $$\Phi$$ - распознающая м.Т., а м.Т. $${\cal M}_1$$ вычисляет функцию f(x).
Тогда существует м.Т. $$\cal N,\ $$ которая вычисляет функцию, задаваемую выражением:
$$g(x) =\ '\mbox {\bf while}\ \Phi(x)= 0\ \mbox {\bf do }\ \ x := f(x)\ \mbox {\bf enddo}'$$
Доказательство. Действительно, пусть м.Т. $${\cal M}_2$$ - вычисляет тождественную функцию g(x)=x. Построим по м.Т. $$\Phi, {\cal M}_1 \mbox { и }\ {\cal M}_2\ $$ м.Т. $$\cal M,\ $$ реализующую ветвление как в лемме 9.5. Тогда
искомая м.Т. $$\cal N\$$ получается из $$\cal M\ $$ заменой команд $$q_{f}^{1} a \to q_{f} a H (a \in \Sigma )$$ на
соответствующие команды $$q_{f}^{1} a \to q_{0} a H (a \in \Sigma )$$,
обеспечивающие зацикливание.
Реализованные выше операции над машинами Тьюринга
и вычислимыми функциями позволяют получать программы новых м.Т., используя обычные конструкции языка программирования
"высокого" уровня: последовательную и параллельную композицию, ветвление и цикл. Пусть $$M, M_{1}, M_{2},\dots , M_{m}, \Phi$$ - машины Тьюринга. Последовательную композицию M1 и M2 будем обозначать M1;M2, параллельную композицию M1, M2,... , Mm
обозначаем как $$\mathbf {par}_b(M_1,M_2,\ldots , M_m)\ $$ (здесь b -
это символ, разделяющий аргументы и результаты этих машин), ветвление -
$${\bf if}\ \Phi\ {\bf then}\ M_1\ {\bf else}\ M_2\ {\bf endif}$$
цикл -
$${\bf while}\ \Phi\ {\bf do }\ M\ {\bf enddo}.$$
Пример 9.4. Рассмотрим в качестве примера задачу
перевода чисел из унарной системы счисления в двоичную.
Пусть fub(|n) = n(2) для всех $$n \in N$$, где n(2) - двоичная запись числа n.
Пусть M1 - м.Т., которая начальную конфигурацию q0 ,|n переводит в конфигурацию q1 ,0*|n; M2 - м.Т., которая прибавляет 1 к двоичному
числу-аргументу (см. пример ref{ex8-suc}); M3 - м.Т., которая вычитает 1 из унарного
числа; $$\Phi$$ - м.Т., которая на аргументе вида x*|y выдает
0, если число y > 0, и выдает 1 при y=0 (т.е. на аргументе $$x*\wedge$$); M4 - м.Т., которая стирает * в аргументе вида x* и
останавливается. Реализация каждой из указанных м.Т. очевидна.
Теперь требуемая м.Т. Mub, вычисляющая fub, получается как
$$M_1; {\bf while}\ \Phi\ \mathbf{ do\ \ par}_*(M_2,M_3)\ {\bf enddo}; M_4.$$
Действительно, после работы M1 получаем конфигурацию q10*|n. Предположим теперь по индукции, что после i (i <n) итераций цикла
while получается конфигурация q1 i(2)*|n-i.
Тогда на (i+1) -ой итерации цикла после параллельного
применения M2 к i(2) и M3 к |n-i
получаем конфигурацию q1(i+1)(2)*|n-i-1.
Поэтому после n итераций получится конфигурация $$q_{1} n_{(2)}*\wedge$$. На ней $$\Phi$$ выдаст 1, и цикл завершится с записью $$n_{(2)}*\wedge$$ на ленте,
из которой M4 сотрет * и оставит требуемый результат n(2).
Отметим, что из приведенного примера и из задачи \oldref{prb3-6}(a) следует,
что класс вычислимых на м.Т. арифметических функций не зависит от
выбора унарного или двоичного кодирования аргументов и результатов.
Это же справедливо и для троичной, десятичной и других позиционных
систем счисления ( почему ?).
Задачи
Задача 9.1. Постройте м.Т. для функции копирования, не
увеличивая исходный алфавит $$\Sigma.$$
Задача 9.2. Постройте программу м.Т., которая выполняла бы
перенос непустого слова в заданное место ленты, т.е. для любого
слова $$w \in (\Sigma \setminus \{ \wedge \} )^{*}$$ и n > 0 выполняла
преобразование конфигураций: $$q_1w \wedge^n \#\ \vdash^*\ \wedge^n q_2\#w\$$.
Задача 9.3. Достройте программу м.Т. $${\cal M}^\prime\ $$ из леммы 9.1 на этапах 3 и 4.
Задача 9.4. Докажите, что односторонняя м.Т. $${\cal M}^\prime,\ $$ построенная в лемме 9.2, корректно моделирует исходную м.Т. $${\cal M}$$.
Задача 9.5. Другой, по сравнению с конструкцией леммы 9.2,
подход к моделированию двухсторонней ленты на
односторонней заключается в том, чтобы содержимое правой полуленты $$\cal M\$$ хранить в четных ячейках $$\cal M^\prime,\$$ а содержимое
левой полуленты - в нечетных, поместив в 1-ю ячейку специальный маркер.
Постройте программу, реализующую этот подход (ее достоинство -
увеличение алфавита ленты всего на 1 символ).
Задача 9.6. Достройте программу м.Т. $$\cal M$$ из
леммы 9.4 на этапах 1, 3 и 5.
Задача 9.7. Построить программы машин Тьюринга, вычисляющих следующие
функции.
Перевод из двоичной системы в унарную: fbu(n(2))= |n.
Сложение и вычитание в двоичной системе: sum(n*m)=n+m и $$sub(n*m)= n \dot - m,\ ( \dot - $$ совпадает с - при n >= m и $$n \dot - m =0$$ при m > n ).
Умножение в двоичной системе: mul(n*m)= n x m. ( Реализуйте алгоритм умножения "в столбик".)
Возведение в степень: exp(n*m)= nm.
Извлечение квадратного корня: $$sqr(n) =\lfloor\sqrt{n}\rfloor$$.
Логарифмирование: $$log(n)=\lfloor log_{2n} \rfloor$$.
Деление: $$div(n*m) =\lfloor \frac{n}{ m} \rfloor\ (m \neq 0)$$.
Остаток от деления: rest(n*m) = n mod m.
Функция выбора аргумента: $$I_m^n(|^{x_1}*|^{x_2}*\ldots *|^{x_n})= |^{x_m}\ \ (1\leq m \leq n)$$.
Задача 9.8. Используя машины Тьюринга из предыдущей
задачи, построить программы машин Тьюринга, вычисляющих следующие
функции.
$$\begin{array}{lll}
f_1(x, y) = \left \{\begin{array}{ll}
x^2y^3, \mbox{ если }\ x < y \\
\lfloor (x+y)/2 \rfloor , \mbox{ в противном случае}
\end{array} \right. \\
\end{array}$$
$$\begin{array}{lll}
f_2(x, y) = \left \{\begin{array}{ll}
\lfloor \sqrt{x}\ \rfloor , \mbox{ если } x+1 \geq y \\
2(x +y), \mbox{ в противном случае}
\end{array} \right. \\
\end{array}$$
$$\begin{array}{lll}
f_3(x, y) = \left \{\begin{array}{ll}
\lfloor \log_2 (1+ \lfloor \frac{x}{ y} \rfloor)\ \rfloor, \mbox{ если } x > 2 y\\
xy, \mbox{ в противном случае}
\end{array} \right. \\
\end{array}$$
$$\begin{array}{lll}
f(x, y) = \left \{\begin{array}{ll}
\lfloor \sqrt{x}\ \rfloor , \mbox{ если } 2x \geq y \\
(x\ mod\ y), \mbox{ в противном случае}
\end{array} \right. \\
\end{array}$$
Задача 9.9. Докажите, что всякую арифметическую функцию f(x),
вычислимую на некоторой м. Т. $$M = <Q, \Sigma , P,q_{0}, q_{f}>$$, можно также вычислить на м. Т. M',, алфавит ленты которой содержит лишь два символа $$\wedge$$ и |. (Указание: используйте для моделирования
одного символа из $$\Sigma$$ блок из нескольких подряд идущих ячеек,
содержащих его код в алфавите $$\{ \wedge , , | \}$$ ) и замените
каждую команду M группой команд, обрабатывающих соответствующий
блок ячеек).
Задача 9.10.
Построить машину Тьюринга, определяющую по слову x в алфавите {1, 2} симметрично ли оно,
т. е. вычисляющую функцию:
$$f(x) = \left \{\begin{array}{ll}
1, \mbox{ если слово x симметрично}\\
2, \mbox{ в противном случае}
\end{array} \right.$$
Задача 9.11.
Построить машину Тьюринга, сравнивающую два слова x=x1x2... xn и y=y1y2... ym в алфавите {1, 2, 3} лексикографически: $$x \prec y \Leftrightarrow\ \exists i \leq n [(x_1=y_1)\ \\ ( x_2=y_2)\ \ \ldots\ (x_{i-1}=y_{i-1})
\ \\ ( x_i < y_i )]$$ или для некоторого непустого слова x' выполнено y = x x'.
Эта машина Тьюринга должна вычислять функцию:
$$f(x, y) = \left \{\begin{array}{ll}
1 , \text{ если $x \prec y$ }\\
2 , \text{ если $x = y$ }\\
3 , \text{ если $y \prec x$ }
\end{array} \right.$$
