Аноним

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

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


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


Строка 49: Строка 49:
в конечном и магазинном автоматах, но и бесконечной вспомогательной памяти последнего, причем без присущих [[МП-автомат|''МП-автомату'']] ограничений на "магазинный" характер ее использования.
в конечном и магазинном автоматах, но и бесконечной вспомогательной памяти последнего, причем без присущих [[МП-автомат|''МП-автомату'']] ограничений на "магазинный" характер ее использования.


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


В дополнение к естественной интерпретации машины Тьюринга как распознавателя, допускающего тот или иной язык, ее можно рассматривать как устройство, которое вычисляет некоторую функцию <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> содержит не более одного элемента.
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],  
[Ахо-Хопкрофт-Ульман],