Машина Тьюринга: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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> содержит не более одного элемента. | ||
==Литература== | ==Литература== | ||
[Ахо-Хопкрофт-Ульман], | [Ахо-Хопкрофт-Ульман], | ||