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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
Строка 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>.

Навигация