Rambler's Top100 Service
Поиск   
 
Обратите внимание!   BOAI: наука должна быть открытой Обратите внимание!
 
  Наука >> Математика >> Математическое образование | Популярные статьи
 Написать комментарий  Добавить новое сообщение
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)$, где

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

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

Помимо ленты машина Тьюринга имеет управляющее устройство, состояние которого задается элементом $q$ множества ${\cal Q}$.

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

  • читает символ, находящийся под головкой (т. е. определяет $s_p$);
  • вычисляет значение функции переходов: $\delta(q,s_p)=(q',s,\Delta p)$ (если функция переходов на паре $(q,s_p)$ не определена, то останавливает машину Тьюринга);
  • записывает на ленту в ячейку $p$ символ $s$, сдвигает головку на $\Delta p$ и переходит в состояние $q'$ (другими словами, новое состояние машины задается тройкой $((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.   Частичная функция $f$ из $\ensuremath{{\cal A}}^* $ в $\ensuremath{{\cal A}}^* $ называется вычислимой, если существует машина Тьюринга $М$, для которой $\varphi _М=f$. При этом будем говорить, что $f$ вычислима на $М$.

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

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

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


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


    Написать комментарий
     Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования