Машина Тьюринга: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
(не показана 1 промежуточная версия 1 участника) | |||
Строка 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> | (4) <math>\,b</math> — ''пустой символ'', <math>b\in T \setminus \Sigma</math>; | ||
(5) <math>q_0</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> | (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>\,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>\,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. | |||
[[Категория: Теория автоматов]] | [[Категория: Теория автоматов]] |
Текущая версия от 21:21, 14 декабря 2011
Машина Тьюринга(Turing machine) — одна из основных конструкций, которые были предложены для уточнения, или адекватной формализации, общего интуитивного понятия алгоритма.
Недетерминированной машиной Тьюринга (сокращенно НМT или просто МT) [math]\displaystyle{ \,M }[/math] называется семерка [math]\displaystyle{ \,(Q,T,\Sigma,b,q_0,q_f,\delta) }[/math], где
(1) [math]\displaystyle{ \,Q }[/math] — конечное множество состояний управляющего устройства;
(2) [math]\displaystyle{ \,T }[/math] — конечное множество символов на ленте;
(3) [math]\displaystyle{ \,\Sigma }[/math] — множество входных символов, [math]\displaystyle{ \Sigma\subseteq T }[/math];
(4) [math]\displaystyle{ \,b }[/math] — пустой символ, [math]\displaystyle{ b\in T \setminus \Sigma }[/math];
(5) [math]\displaystyle{ \,q_0 }[/math] — начальное состояние, [math]\displaystyle{ q_0\in Q }[/math];
(6) [math]\displaystyle{ \,q_f }[/math] — заключительное (или допускающее) состояние, [math]\displaystyle{ q_f\in Q }[/math];
(7) [math]\displaystyle{ \,\delta }[/math] — так называемая функция перехода — отображение множества [math]\displaystyle{ Q\times T }[/math] в множество подмножеств в [math]\displaystyle{ Q\times T\times \{L, R, S\} }[/math], где [math]\displaystyle{ \,L }[/math] означает сдвиг головки по ленте влево, [math]\displaystyle{ \,R }[/math] — вправо, [math]\displaystyle{ \,S }[/math] — головка остается на месте.
Машина Тьюринга работает на неограниченной с обеих сторон ленте, разделяемой на ячейки, одну из которых обозревает головка. В любой момент времени все ячейки, кроме конечного числа, заняты пустыми символами. Конфигурацией (или мгновенным описанием) машины Тьюринга [math]\displaystyle{ \,M }[/math] называется слово вида [math]\displaystyle{ \,xqy }[/math], где [math]\displaystyle{ \,xy }[/math] — непустая часть ленты, а [math]\displaystyle{ \,q }[/math] — текущее состояние управляющего устройства (головка на ленте обозревает символ, стоящий справа от [math]\displaystyle{ \,q }[/math]).
Начальной конфигурацией [math]\displaystyle{ \,M }[/math] называется конфигурация вида [math]\displaystyle{ \,q_0\omega }[/math], где [math]\displaystyle{ \omega\in\Sigma^* }[/math]. Заключительная конфигурация — это конфигурация вида [math]\displaystyle{ \,xq_f y }[/math].
Tакт работы машины Тьюринга [math]\displaystyle{ \,M }[/math] представляется в виде бинарного отношения [math]\displaystyle{ \vdash_M }[/math], определенного на конфигурациях, для которого [math]\displaystyle{ \alpha \vdash_M\beta }[/math] в одном из трех следующих случаев:
(1) [math]\displaystyle{ \alpha=\gamma qX\omega, \beta=\gamma pY\omega, (p,Y,S) \in \delta(q,X) }[/math] для некоторых [math]\displaystyle{ \gamma, \omega\in T^* }[/math];
(2) [math]\displaystyle{ \alpha=\gamma qX\omega, \beta=\gamma Yp\omega, (p,Y,R) \in \delta(q,X) }[/math] для некоторых [math]\displaystyle{ \gamma,\omega\in T^* }[/math];
(3) [math]\displaystyle{ \alpha=\gamma ZqX\omega, \beta=\gamma pZY\omega, (p,Y,L) \in \delta(q,X) }[/math] для некоторых [math]\displaystyle{ \gamma,\omega\in T^* }[/math] .
[math]\displaystyle{ \,M }[/math] допускает цепочку [math]\displaystyle{ \omega\in\Sigma^* }[/math], если [math]\displaystyle{ \,q_0\omega\vdash^*_M\alpha }[/math], где [math]\displaystyle{ \,\alpha }[/math] - некоторая заключительная конфигурация с пустой лентой, так называемая допускающая конфигурация. Языком, допускаемым [math]\displaystyle{ \,M }[/math] (обозначается [math]\displaystyle{ \,L(M) }[/math]), называют множество всех цепочек, допускаемых [math]\displaystyle{ \,M }[/math].
Таким образом, подобно конечному автомату машина Тьюринга состоит из ленты, головки и управляющего устройства с конечным числом состояний.
Однако в машине Тьюринга лента неограниченно простирается вправо и влево, а головка не только читает, но и пишет. В силу этого лента в машине Тьюринга играет роль не только входной ленты в конечном и магазинном автоматах, но и бесконечной вспомогательной памяти последнего, причем без присущих МП-автомату ограничений на "магазинный" характер ее использования.
Поэтому не случайно, что машины Тьюринга обладают большей вычислительной мощностью, чем МП- автоматы, определяющие класс КС-языков. Известно, что язык порождается грамматикой составляющих тогда и только тогда, когда он допускается машиной Тьюринга.
В дополнение к естественной интерпретации машины Тьюринга как распознавателя, допускающего тот или иной язык, ее можно рассматривать как устройство, которое вычисляет некоторую функцию [math]\displaystyle{ \,f }[/math]. Аргументы этой функции кодируются на ленте в виде слова [math]\displaystyle{ \,X }[/math] со специальным символом (маркером), отделяющим их друг от друга. Если машина Тьюринга останавливается с заключительной конфигурацией [math]\displaystyle{ \,vq_fw }[/math], то слово [math]\displaystyle{ \,Y=vw }[/math] рассматривается как код значения функции [math]\displaystyle{ \,f }[/math], т.е. [math]\displaystyle{ \,f(X)=Y }[/math].
Машина Тьюринга [math]\displaystyle{ \,M }[/math] называется детерминированной (сокращенно ДМT), если для любых [math]\displaystyle{ q\in Q }[/math] и [math]\displaystyle{ X\in T }[/math] множество [math]\displaystyle{ \,\delta(q,X) }[/math] содержит не более одного элемента.
Литература
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
- Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.