Я читаю книгу о языках и автоматах, и я не понимаю машины Тьюринга. Я без проблем научился использовать DFA NFA и Pushdown Automata. Может кто-нибудь объяснить, что это делает?
B = {w#w|w ∈ {0, 1}*}
Следующий рисунок содержит несколько снимков ленты M1 во время вычислений на этапах 2 и 3 при запуске на входе 011000#011000.
Большое спасибо!
Машина Тьюринга — это гипотетическая машина с лентой, на которой хранятся символы. Он может иметь несколько головок, которые могут считывать символы с ленты или записывать символы на ленту.
Теперь ваша грамматика говорит, что B = {w#w|w ∈ {0, 1}*}, то есть любая строка вида «w#w», где w — любая комбинация нулей и единиц или вообще ни одной. Итак, скажем, w = 011000 для этого конкретного примера. Результирующая строка будет иметь вид 011000#011000, и ваша машина Тьюринга будет проверять, следует ли она этой грамматике.
В этом случае у вашей машины Тьюринга одна голова. Он начинается в начале строки. Читает первый символ, который равен 0. Отметьте его "x": это означает, что я прочитал это. Затем идет сразу после # и проверяет, соответствует ли только что прочитанное. В этом случае это также 0, поэтому он помечает его как соответствующий «x». Затем он возвращается к предыдущей позиции и делает то же самое для следующего символа. Он продолжает делать это, пока не достигнет #. Когда он читает решетку или #, он проверяет конец строки, и если это конец строки, он принимает эту строку, говоря, что да, это соответствует заданной грамматике.
«Представьте себе бесконечный ряд гостиничных номеров, и в каждом номере есть лампочка и выключатель, который ею управляет. Изначально во всех номерах темно. Робот стартует в одном из номеров и имеет возможность управлять выключателями и перемещаться в соседние. номера.
У робота есть несколько состояний, в которых он может находиться, и каждое состояние определяет, что он должен делать, в зависимости от того, светлая текущая комната или темная. Например, правила робота могут включать следующие состояния:
«Испуганное» состояние:
Если в комнате темно, включите свет и идите в комнату слева.
Если в комнате светло, ничего не делать и перейти в «нормальное» состояние. «Нормальное» состояние:
Если в комнате светло, выключите свет и идите в комнату справа.
В противном случае перейдите в «испуганное» состояние.
Одним особым состоянием является состояние «стоп». Когда робот оказывается в этом состоянии, процесс завершен.
Предположим, у робота есть n состояний (не считая состояния «стоп»), и он останавливается. Какое максимальное количество светлых комнат на данный момент?
Эта система является прямой аллегорией машин Тьюринга. Отель — это лента, робот — это машина Тьюринга, а темные и светлые комнаты — это ячейки 0 и 1».
Это из гугологической вики. Идею подал я, но, конечно, этот текст со времени меня улучшился.
