УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

От тьюрингова программирования к автоматному

Краткая версия статьи опубликована в журнале "Мир ПК", 2002. №2, C.144-149.
Более полная версия статьи доступна на сайте журнала "Мир ПК" (www.pcworld.ru).

(краткая аннотация)

(C) 2001 г. А.А.Шалыто, Н.И.Туккель

Федеральный научно-производственный центр ГУП "НПО "Аврора"",
Санкт-Петербургский государственный институт точной механики и оптики
(технический университет)

Отсюда можно скачать полный текст статьи в формате pdf (225 кб)

Настоящая работа посвящена преобразованию классической модели машины Тьюринга в другую модель, обеспечивающую переход от тьюрингова программирования к автоматному. Последнее весьма эффективно для систем со сложным поведением, характерным для задач управления или сводимым к ним, что демонстрируется на классических задачах распознавания цепочек для:

• скобок произвольной глубины;
• языка {1ⁿ0ⁿ | n >= 0};
• языка {1ⁿ0ⁿ1ⁿ | n >= 0}.

Первые два языка, задаваемые контекстно-свободными грамматиками, требуют использования модели автомата с магазинной памятью, а для третьего языка, определяемого контекстно-зависимой грамматикой, необходим переход к линейно-ограниченным автоматам.

В настоящей работе показано, что при использовании предлагаемого подхода, изменение типа грамматики не приводит к необходимости использования модели другого типа, а вызывает лишь незначительное усложнение графа переходов.

Отмечено, что если Дж. фон Нейман изменил машину Тьюринга для эффективной аппаратной реализации алгоритмов (например, введением арифметическо-логического устройства), то в настоящей работе делается аналогичная попытка преобразования этой машины с целью повышения эффективности программирования. При этом, если в машине Тьюринга автомат решает две задачи (управление и вычисление, не свойственное для него), то в предлагаемом подходе он решает только задачу управления, а вычисления осуществляются в объектах управления, предназначенных для этой цели (например, регистры, счетчики и т.д.).