Машина Тьюринга, как модель автоматных программ

[@lws0954]

Спору нет, безусловно, МТ не эквивалентны КА. Но, замечу, статья-то о том, что эквивалентны МТ и автоматные программы (подчеркиваю, что КА это только лишь часть АП — ее управление). Более того, МТ — это модель АП. Следовательно, все, что может МТ (а она может все!), может и АП.
А «чтобы убедиться в этом», замените в примере рис.5, рис.6 символ «a» на «0», а символ «b» на 1 и Вы получите в точности тот язык, который предлагаете распознать. Получилось?

[@Zenitchik]

Машина Тьюринга — сильно избыточна для автоматных программ.

[@lws0954]

Мысль, конечно, интересная, но бездоказательная. Да и зачем умалять достоинства АП. Но пусть даже избыточна, как Вы утверждаете. Ну, и что? АП тогда тоже «избыточны» поскольку их моделью является как раз МТ? И в чем заключена эта самая «избыточность»? И что значит «сильно»? И что надо у МТ убрать, чтобы лишить ее «избыточности»?

[@Zenitchik]

Простите, что значит «бездоказательная»?
Под автоматными языками понимаются языки, трансляция которых возможна с помощью КА.
Чем отличается КА от МТ, Вы и без меня знаете.

[@lws0954]

Я не рассматриваю чистый КА. Я рассматриваю автоматные программы (АП), в которые КА входят составной частью. Т.е. чистый КА и АП — это качественно разные вещи. В АП, кроме КА, входит еще множество операторов и множество переменных. Роль КА, как управления автоматной программы, запускать операторы автоматной программы, которые уже делают с переменными автоматной программы все, что угодно.

[@lws0954]

Могу только повторить (см. статью), что автоматная программа — это программа, имеющая управление в форме модели конечного автомата. Но это общее определение. Дальше нужно, конечно, конкретизировать модель автомата, т.к. подобных моделей достаточно много. Предлагается модель структурного конечного автомата с абстрактным состоянием, сокращенно — СКА.
Текст программ дает представление уже о форме описания СКА. Это таблица переходов в текстовой форме. И уже она интерпретируется программным ядром, реализующим работу управления АП.
Интерпретатор необходим, т.к. не существует аппаратной поддержки. Например, для обычных программ такой «поддержкой» являются операторы управления программ — do, while, go to, for, switch и т.д. и т.п.

[@lolikandr]

Было бы неплохо посмотреть на примеры автоматных программ, а особенно с комментариями, что в них нельзя менять, чтобы они не перестали быть автоматными.

[@lws0954]

Большое спасибо за интересный вопрос.
Отвечая, можно сказать просто — не менять управление. Остальное к АП уже фактически не имеет отношения (см. определение АП).
Как это будет выглядеть в нашем случае?
Введем в автоматный класс «неавтоматную» функцию/метод increment:

void FTIncrement::increment() {
    while (!x1()) {
        y15();
    }
    y16();
    while (x2()||(!x2()&&!x1()&&!x3())) {
        if (x2()) {
            y2(); y16();
        }
    }
    if (x1()||x3()) {
        y1();
    }
}

Теперь класс может быть и неавтоматным. К нему можно будет обращаться, ну, например, уже так:

FTIncrement *p = new FTIncrement(«inc», nullptr);
p->increment();

И, что интересно, будет даже работать.
Но для проверки пришлось проделать следующее.
Поскольку я работаю в рамках среды ВКПа и с автоматами, то пришлось немного извратиться.
Так, я привел управление класса FTIncrement к совсем простому автомату (остальные строки таблицы переходов убрал):
LArc(«Прямой проход», «Конец», "--", «y3»), // функция инкремента
LArc(«Конец», «Прямой проход», «x16», «y17»), // Перезапуск машины

Одновременно это значит, что для сигнала y3 нужно создать одноименное действие y3().

void FTIncrement::y3() { increment(); }

Ну и все. Не так уж сложно. Мне уж точно.
Запускаем. Теперь функция increment за один так делает то, на что исходному автомату требовалось много больше [дискретного] времени. Я даже посчитал: для заданной строки 11011110011111, чтобы получить в результате 11011110100000 нужен 21 такт. Но для исследования «идеи» это нормально.
Интереснее другое. Приглядимся к автомату. Что будет, если среди символов 0, 1 попадется другой, например, 2. Автомат, как и МТ, зависнет в состоянии «Обратный проход», т.к. не знает, что ему в такой ситуации делать. Эквивалентная ему функция зависнет на операторе while (x2()||(!x2()&&!x1()&&!x3())). При этом она, в отличие от автомата, подвесит и приложение. А это уже совсем плохо. Т.е. подобные ошибки в случае неавтоматных программ ведут фактически к краху приложения.
Для автомата разрешить проблему просто. Достаточно в таблицу переходов добавить, например, такой переход:
LArc(«Обратный проход», «Конец», "^x1^x2^x3","--"), // неопознанный символ
Для функции increment нужно изменить ее код, который учитывал бы и эту ситуацию.
Чем хороши в данной ситуации автоматы. Если бы мы делали формальный анализ автомата на рис. 4, то сразу бы подобную ошибку обнаружили, т.к. анализ на полноту и непротиворечивость переходов это выявляет сразу. Не надо даже вникать в работу автомата — все делает теория автоматов. Для функцией increment подобный анализ — это уже другая история. Т.е. то, что обычно для автоматов, для обычных программ необычно :).
Ну вот как-то так…