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

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


''Недетерминированной машиной Тьюринга''
''Недетерминированной машиной Тьюринга'' (сокращенно ''НМT'') <math>M</math> называется семерка
(сокращенно ''НМ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>, где


Строка 20: Строка 19:
состояние, <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>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>M</math> называется конфигурация вида <math>q_0\omega</math>, где <math>\omega\in\Sigma^*</math>. Заключительная конфигурация --- это конфигурация вида <math>xq_f y</math>.
вида <math>q_0\omega</math>, где <math>\omega\in\Sigma^*</math>. Заключительная конфигурация --- это конфигурация вида <math>xq_f
y</math>.


''Tакт'' работы машины Тьюринга <math>M</math> представляется в виде
''Tакт'' работы машины Тьюринга <math>M</math> представляется в виде
Строка 53: Строка 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>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>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> называется ''детерминированной''
Машина Тьюринга <math>M</math> называется ''детерминированной'' (сокращенно ''ДМT''), если для любых <math>q\in Q</math> и <math>X\in T</math> множество <math>\delta(q,X)</math> содержит не более одного элемента.
(сокращенно ''ДМT''), если для любых <math>q\in Q</math> и <math>X\in T</math>
множество <math>\delta(q,X)</math> содержит не более одного элемента.
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],  
[Ахо-Хопкрофт-Ульман],  

Версия от 16:51, 25 мая 2009

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

Недетерминированной машиной Тьюринга (сокращенно НМ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] содержит не более одного элемента.

Литература

[Ахо-Хопкрофт-Ульман],

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