Аноним

Машина Тьюринга: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Машина Тьюринга'''([[Turing machine|''Turing machine'']]) - одна из основных конструкций, которые были предложены для уточнения, или адекватной формализации, общего интуитивного понятия [[алгоритм|''алгоритма'']].
'''Машина Тьюринга'''([[Turing machine|''Turing machine'']]) одна из основных конструкций, которые были предложены для уточнения, или адекватной формализации, общего интуитивного понятия [[алгоритм|''алгоритма'']].


[[Недетерминированная машина Тьюринга|''Недетерминированной машиной Тьюринга'']] (сокращенно [[НМТ |''НМT'']] или просто [[МТ |''МT'']]) <math>M</math> называется семерка
[[Недетерминированная машина Тьюринга|''Недетерминированной машиной Тьюринга'']] (сокращенно [[НМТ |''НМT'']] или просто [[МТ |''МT'']]) <math>\,M</math> называется семерка
<math>(Q,T,\Sigma,b,q_0,q_f,\delta)</math>, где
<math>\,(Q,T,\Sigma,b,q_0,q_f,\delta)</math>, где


(1) <math>Q</math> --- конечное множество ''состояний'' управляющего
(1) <math>\,Q</math> конечное множество ''состояний'' управляющего
устройства;
устройства;


(2) <math>T</math> --- конечное множество ''символов на ленте'';
(2) <math>\,T</math> конечное множество ''символов на ленте'';


(3) <math>\Sigma</math> --- множество ''входных символов'',
(3) <math>\,\Sigma</math> множество ''входных символов'',
<math>\Sigma\subseteq T</math>;
<math>\Sigma\subseteq T</math>;


(4) <math>b</math> --- ''пустой символ'', <math>b\in T \setminus \Sigma</math>;
(4) <math>\,b</math> ''пустой символ'', <math>b\in T \setminus \Sigma</math>;


(5) <math>q_0</math> --- ''начальное состояние'', <math>q_0\in Q</math>;
(5) <math>\,q_0</math> ''начальное состояние'', <math>q_0\in Q</math>;


(6) <math>q_f</math> --- ''заключительное'' (или ''допускающее'')
(6) <math>\,q_f</math> ''заключительное'' (или ''допускающее'')
состояние, <math>q_f\in Q</math>;
состояние, <math>q_f\in Q</math>;


(7) <math>\delta</math> --- так называемая функция ''перехода'' --- отображение множества <math>Q\times T</math> в множество подмножеств в <math>Q\times T\times \{L, R, S\}</math>, где <math>L</math>  означает сдвиг головки по ленте влево, <math>R</math> --- вправо, <math>S</math> --- головка
(7) <math>\,\delta</math> так называемая функция ''перехода'' отображение множества <math>Q\times T</math> в множество подмножеств в <math>Q\times T\times \{L, R, S\}</math>, где <math>\,L</math>  означает сдвиг головки по ленте влево, <math>\,R</math> вправо, <math>\,S</math> головка
остается на месте.
остается на месте.


Машина Тьюринга работает на неограниченной с обеих сторон ленте, разделяемой на ячейки, одну из которых обозревает ''головка''. В любой момент времени все ячейки, кроме конечного числа, заняты
Машина Тьюринга работает на неограниченной с обеих сторон ленте, разделяемой на ячейки, одну из которых обозревает ''головка''. В любой момент времени все ячейки, кроме конечного числа, заняты
пустыми символами. ''Конфигурацией'' (или ''мгновенным описанием'') машины Тьюринга <math>M</math> называется слово вида <math>xqy</math>, где <math>xy</math> --- непустая часть ленты, а <math>q</math> --- текущее состояние управляющего устройства (головка на ленте обозревает символ,
пустыми символами. ''Конфигурацией'' (или ''мгновенным описанием'') машины Тьюринга <math>\,M</math> называется слово вида <math>\,xqy</math>, где <math>\,xy</math> непустая часть ленты, а <math>\,q</math> текущее состояние управляющего устройства (головка на ленте обозревает символ,
стоящий справа от <math>q</math>).
стоящий справа от <math>\,q</math>).


''Начальной'' конфигурацией <math>M</math> называется конфигурация вида <math>q_0\omega</math>, где <math>\omega\in\Sigma^*</math>. Заключительная конфигурация --- это конфигурация вида  <math>xq_f y</math>.
''Начальной'' конфигурацией <math>\,M</math> называется конфигурация вида <math>\,q_0\omega</math>, где <math>\omega\in\Sigma^*</math>. Заключительная конфигурация это конфигурация вида  <math>\,xq_f y</math>.


''Tакт'' работы машины Тьюринга <math>M</math> представляется в виде
''Tакт'' работы машины Тьюринга <math>\,M</math> представляется в виде
бинарного отношения <math>\vdash_M</math>, определенного на конфигурациях,
бинарного отношения <math>\vdash_M</math>, определенного на конфигурациях,
для которого <math>\alpha \vdash_M\beta</math> в одном из трех следующих
для которого <math>\alpha \vdash_M\beta</math> в одном из трех следующих
Строка 42: Строка 42:
\in \delta(q,X)</math> для некоторых <math>\gamma,\omega\in T^*</math> .
\in \delta(q,X)</math> для некоторых <math>\gamma,\omega\in T^*</math> .


<math>M</math> ''допускает'' цепочку <math>\omega\in\Sigma^*</math>, если <math>q_0\omega\vdash^*_M\alpha</math>, где <math>\alpha</math> - некоторая заключительная конфигурация с пустой лентой, так называемая ''допускающая'' конфигурация. ''Языком, допускаемым'' <math>M</math> (обозначается <math>L(M)</math>), называют множество всех цепочек, допускаемых <math>M</math>.
<math>\,M</math> ''допускает'' цепочку <math>\omega\in\Sigma^*</math>, если <math>\,q_0\omega\vdash^*_M\alpha</math>, где <math>\,\alpha</math> - некоторая заключительная конфигурация с пустой лентой, так называемая ''допускающая'' конфигурация. ''Языком, допускаемым'' <math>\,M</math> (обозначается <math>\,L(M)</math>), называют множество всех цепочек, допускаемых <math>\,M</math>.


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


Однако в машине Тьюринга лента неограниченно простирается вправо и влево, а головка не только читает, но и пишет. В силу этого лента в машине Тьюринга играет роль не только входной ленты
Однако в машине Тьюринга лента неограниченно простирается вправо и влево, а головка не только читает, но и пишет. В силу этого лента в машине Тьюринга играет роль не только входной ленты
в конечном и магазинном автоматах, но и бесконечной вспомогательной памяти последнего, причем без присущих [[МП-автомат|''МП-автомату'']] ограничений на "магазинный" характер ее использования.
в конечном и магазинном автоматах, но и бесконечной вспомогательной памяти последнего, причем без присущих [[МП-Автомат|''МП-автомату'']] ограничений на "магазинный" характер ее использования.


Поэтому не случайно, что машины Тьюринга обладают большей вычислительной мощностью, чем МП- автоматы, определяющие класс [[КС-язык|''КС-языков'']]. Известно, что язык порождается [[Грамматика составляющих | ''грамматикой составляющих'']] тогда и только тогда, когда он допускается машиной Тьюринга.
Поэтому не случайно, что машины Тьюринга обладают большей вычислительной мощностью, чем МП- автоматы, определяющие класс [[КС-язык|''КС-языков'']]. Известно, что язык порождается [[Грамматика составляющих | ''грамматикой составляющих'']] тогда и только тогда, когда он допускается машиной Тьюринга.


В дополнение к естественной интерпретации машины Тьюринга как распознавателя, допускающего тот или иной язык, ее можно рассматривать как устройство, которое вычисляет некоторую функцию <math>f</math>. Аргументы этой функции кодируются на ленте в виде слова <math>X</math> со специальным символом (маркером), отделяющим их друг от друга. Если машина Тьюринга останавливается с заключительной конфигурацией <math>vq_fw</math>, то слово <math>Y=vw</math> рассматривается как код значения функции <math>f</math>, т.е. <math>f(X)=Y</math>.
В дополнение к естественной интерпретации машины Тьюринга как распознавателя, допускающего тот или иной язык, ее можно рассматривать как устройство, которое вычисляет некоторую функцию <math>\,f</math>. Аргументы этой функции кодируются на ленте в виде слова <math>\,X</math> со специальным символом (маркером), отделяющим их друг от друга. Если машина Тьюринга останавливается с заключительной конфигурацией <math>\,vq_fw</math>, то слово <math>\,Y=vw</math> рассматривается как код значения функции <math>\,f</math>, т.е. <math>\,f(X)=Y</math>.


Машина Тьюринга <math>M</math> называется [[Детерминированная машина Тьюринга|''детерминированной'']] (сокращенно [[ДМТ |''ДМT'']]), если для любых <math>q\in Q</math> и <math>X\in T</math> множество <math>\delta(q,X)</math> содержит не более одного элемента.
Машина Тьюринга <math>\,M</math> называется [[Детерминированная машина Тьюринга|''детерминированной'']] (сокращенно [[ДМТ |''ДМT'']]), если для любых <math>q\in Q</math> и <math>X\in T</math> множество <math>\,\delta(q,X)</math> содержит не более одного элемента.
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],  
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —  М.: Мир, 1979.
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. —
Новосибирск: НГУ, 1995.


[Касьянов/95]




[[Категория: Теория автоматов]]
[[Категория: Теория автоматов]]