Объяснение вычисления машины Тьюринга

Question

У меня возникли проблемы с интерпретацией того, что на самом деле делает эта машина Тьюринга (т.е. я не знаю, как объяснить это на простом английском языке).

Я полагаю, что правильно создал диаграмму состояний, используя таблицу переходов, которую мне дали (хотя и не на 100%).

Из того, что я вижу, эта ТМ остановится в состоянии принятия (q2) всякий раз, когда вход имеет форму

(a || b || B)*Ba*c(a || b || c || B)*,

это любое количество a"S, bи бланки (но нет cs), за которым следует хотя бы один пробел, любое количество aи ровно один c, Все может прийти после того, как мы пойдем налево, найдя первым c,

Я полагаю, мой вопрос

а) Правильна ли моя работа до этого момента? а также

б) Есть ли более значимое объяснение этой машины Тьюринга (то есть более полное описание, чем я написал о вводе, который останавливается в (q2)).

Answer 1

Некоторые наблюдения:

1. q0 читает слева направо, не меняет ленту и останавливается при нажатии c.
2. q1 читает слева направо, меняет местами a и b, останавливается, когда видит B, и оборачивается, когда ударяет a.
3. Единственный способ остановить ТМ - это если
   • Где-то на ленте есть переменная справа от начальной позиции ленты
   • В q1 последний проход справа налево видит только b и оставляет только a между первым c и самым правым B слева от c.
4. q1 меняет все между первым c и самым правым b слева от этого c на ab, в конце концов

Исходная конфигурация ленты>BxBycz, машина всегда будет останавливаться в конфигурации>BxB(a^|y|)cz. Он принимает любую строку, содержащую c.

Ваша диаграмма состояний не согласуется с таблицей в том смысле, что в таблице определена функция перехода, так что f(q1, a) = (q0, b, L) и f(q1, b) = (q1, a, L), но ваша диаграмма показывает f(q1, a) = (q1, a, L) и f(q1, b) = (q0, b, L).