Comments 10
UFO just landed and posted this here
Спору нет, безусловно, МТ не эквивалентны КА. Но, замечу, статья-то о том, что эквивалентны МТ и автоматные программы (подчеркиваю, что КА это только лишь часть АП — ее управление). Более того, МТ — это модель АП. Следовательно, все, что может МТ (а она может все!), может и АП.
А «чтобы убедиться в этом», замените в примере рис.5, рис.6 символ «a» на «0», а символ «b» на 1 и Вы получите в точности тот язык, который предлагаете распознать. Получилось?
А «чтобы убедиться в этом», замените в примере рис.5, рис.6 символ «a» на «0», а символ «b» на 1 и Вы получите в точности тот язык, который предлагаете распознать. Получилось?
Машина Тьюринга — сильно избыточна для автоматных программ.
Мысль, конечно, интересная, но бездоказательная. Да и зачем умалять достоинства АП. Но пусть даже избыточна, как Вы утверждаете. Ну, и что? АП тогда тоже «избыточны» поскольку их моделью является как раз МТ? И в чем заключена эта самая «избыточность»? И что значит «сильно»? И что надо у МТ убрать, чтобы лишить ее «избыточности»?
Я не рассматриваю чистый КА. Я рассматриваю автоматные программы (АП), в которые КА входят составной частью. Т.е. чистый КА и АП — это качественно разные вещи. В АП, кроме КА, входит еще множество операторов и множество переменных. Роль КА, как управления автоматной программы, запускать операторы автоматной программы, которые уже делают с переменными автоматной программы все, что угодно.
Могу только повторить (см. статью), что автоматная программа — это программа, имеющая управление в форме модели конечного автомата. Но это общее определение. Дальше нужно, конечно, конкретизировать модель автомата, т.к. подобных моделей достаточно много. Предлагается модель структурного конечного автомата с абстрактным состоянием, сокращенно — СКА.
Текст программ дает представление уже о форме описания СКА. Это таблица переходов в текстовой форме. И уже она интерпретируется программным ядром, реализующим работу управления АП.
Интерпретатор необходим, т.к. не существует аппаратной поддержки. Например, для обычных программ такой «поддержкой» являются операторы управления программ — do, while, go to, for, switch и т.д. и т.п.
Текст программ дает представление уже о форме описания СКА. Это таблица переходов в текстовой форме. И уже она интерпретируется программным ядром, реализующим работу управления АП.
Интерпретатор необходим, т.к. не существует аппаратной поддержки. Например, для обычных программ такой «поддержкой» являются операторы управления программ — do, while, go to, for, switch и т.д. и т.п.
Было бы неплохо посмотреть на примеры автоматных программ, а особенно с комментариями, что в них нельзя менять, чтобы они не перестали быть автоматными.
Большое спасибо за интересный вопрос.
Отвечая, можно сказать просто — не менять управление. Остальное к АП уже фактически не имеет отношения (см. определение АП).
Как это будет выглядеть в нашем случае?
Введем в автоматный класс «неавтоматную» функцию/метод increment:
Теперь класс может быть и неавтоматным. К нему можно будет обращаться, ну, например, уже так:
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 подобный анализ — это уже другая история. Т.е. то, что обычно для автоматов, для обычных программ необычно :).
Ну вот как-то так…
Отвечая, можно сказать просто — не менять управление. Остальное к АП уже фактически не имеет отношения (см. определение АП).
Как это будет выглядеть в нашем случае?
Введем в автоматный класс «неавтоматную» функцию/метод 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 подобный анализ — это уже другая история. Т.е. то, что обычно для автоматов, для обычных программ необычно :).
Ну вот как-то так…
Sign up to leave a comment.
Машина Тьюринга, как модель автоматных программ