Научная Сеть >> М.Н. Вялый "Сложность вычислительных задач"

Наука >> Математика >> Математическое образование | Популярные статьи

Next: 3. Сложность и сложностные Up: 2. Способы решения задач Previous: 2.1. Исполнитель Contents: Содержание

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

Приведем формальное определение алгоритма, согласованное с предыдущим неформальным обсуждением.

Машина Тьюринга (сокращенно МТ) однозначно задается указанием набора $({\cal S},\hbox{\unitlength=1pt\begin{picture}(6,8) \put(0,0){\line(1,0){6}} \p... ...(6,0){\line(0,1){2}} \end{picture}},\ensuremath{{\cal A}},{\cal Q},q_0, \delta)$ , где

${\cal S}$ - конечное множество, называемое алфавитом МТ (в предыдущем описании элементам этого множества соответствуют все возможные записи на одной странице тетради, выданной Исполнителю);
$\ensuremath{{\cal A}}$ - также конечное множество, называемое внешним алфавитом (в предыдущем описании элементам этого множества соответствуют символы, которыми записывается задание для Исполнителя и результат его работы);
$\hbox{\unitlength=1pt\begin{picture}(6,8) \put(0,0){\line(1,0){6}} \put(0,2){\line(1,0){6}} \put(0,0){\line(0,1){2}} \put(6,0){\line(0,1){2}} \end{picture}}$ - пустой символ (или пробел), это некоторый элемент ${\cal S}\setminus \ensuremath{{\cal A}}$ (в предыдущем описании ему соответствует пустая страница в тетради Исполнителя);
${\cal Q}$ - конечное множество состояний управляющего устройства МТ (неформально - Исполнителя);
$q_0\in{\cal Q}$ - начальное состояние;
$\delta\colon{\cal Q}\times{\cal S}\to {\cal Q}\times{\cal S}\times\{-1,0,1\}$ - (частичная) функция переходов МТ (неформально - книжка с инструкциями для Исполнителя).

Состояние МТ задается тройкой $(\sigma,p,q)$ , где $\sigma$ - бесконечное слово в алфавите ${\cal S}$ , т. е. произвольная последовательность $s_0,\dots, s_n,\dots$ элементов ${\cal S}$ ; - неотрицательное целое число; $q\in{\cal Q}$ . Символы слова $\sigma$ будем, как это принято, представлять записанными на ленте, разбитой на ячейки, по ячейке на символ. На ленте также имеется головка, которая расположена над ячейкой с номером . Наглядно это изображается так:

$\begin{displaymath}\begin{array}{l\vert c\vert c\vert c\vert c\vert l} \multicol... ...}{c}{}& \multicolumn{1}{c}{p}& \multicolumn{1}{c}{} \end{array}\end{displaymath}$

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

множества ${\cal Q}$ .

Состояния МТ меняются дискретно. За один такт работы управляющее устройство выполняет следующие действия (полагаем, что МТ находится в состоянии $(\sigma,p,q)$ ):

читает символ, находящийся под головкой (т. е. определяет

);

вычисляет значение функции переходов: $\delta(q,s_p)=(q',s,\Delta p)$ (если функция переходов на паре

не определена, то останавливает машину Тьюринга);

записывает на ленту в ячейку

символ

, сдвигает головку на $\Delta p$ и переходит в состояние

(другими словами, новое состояние машины задается тройкой $((s_0,\dots,s_{p-1},s,s_{p+1},\dots), p+\Delta p,q')$ );

если $p+\Delta p<0$ , то останавливает машину.

Работа машины Тьюринга начинается из состояния $(\alpha \hbox{\unitlength=1pt\begin{picture}(6,8) \put(0,0){\line(1,0){6}} \pu... ...}} \put(0,0){\line(0,1){2}} \put(6,0){\line(0,1){2}} \end{picture}}\dots,0,q_0)$ , где за конечным словом $\alpha$ , состоящим из символов внешнего алфавита, (множество таких слов обозначается $\ensuremath{{\cal A}}^*$ ) следует бесконечное слово, целиком состоящее из пустых символов. Слово $\alpha$ будем называть входом МТ. В любой момент времени слово, записанное на ленте, однозначно записывается в виде $\sigma\hbox{\unitlength=1pt\begin{picture}(6,8) \put(0,0){\line(1,0){6}} \put(0... ...(1,0){6}} \put(0,0){\line(0,1){2}} \put(6,0){\line(0,1){2}} \end{picture}}\dots$ , где последний символ слова $\sigma$ - не пустой, а за ним идут только пустые символы. Будем называть слово $\sigma$ используемой частью ленты.

Выполняя один такт работы за другим, машина Тьюринга порождает последовательность состояний

$\begin{displaymath} (\sigma_0,0,q_0), (\sigma_1,p_1,q_1), (\sigma_2,p_2,q_2), \dots \end{displaymath}$

Если МТ останавливается, используемая часть ленты в достигнутом перед остановкой состоянии называется результатом работы МТ.

Каждая машина Тьюринга вычисляет частичную функцию $\varphi _М$ из $\ensuremath{{\cal A}}^*$ в $\ensuremath{{\cal A}}^*$ , отображающую вход $\alpha$ в результат работы МТ на входе $\alpha$ при условии, что результат работы является словом во внешнем алфавите. Для входов, на которых машина не останавливается или результат содержит символы из ${\cal S}\setminus \ensuremath{{\cal A}}$ , функция $\varphi _М$ не определена. Из определения ясно, что любая МТ вычисляет ровно одну функцию (быть может, нигде не определенную).

Определение 1. Частичная функция из $\ensuremath{{\cal A}}^*$ в $\ensuremath{{\cal A}}^*$ называется вычислимой, если существует машина Тьюринга , для которой $\varphi _М=f$ . При этом будем говорить, что вычислима на .

Не все функции вычислимы. Это ясно из сравнения мощности множества функций (континуум) и мощности множества машин Тьюринга (счетное множество). Есть и явные примеры невычислимых функций. Один из важнейших - проблема остановки: дана машина Тьюринга и входное слово; нужно проверить, останавливается ли эта машина Тьюринга на данном входе.

Упражнение 1. Определите функцию на множестве слов в конечном алфавите, отвечающую проблеме остановки машины Тьюринга.

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

Next: 3. Сложность и сложностные Up: 2. Способы решения задач Previous: 2.1. Исполнитель Contents: Содержание

МЦНМО

Написать комментарий