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



Главная

Новости
 Новости науки
 Важное
 Почетные доктора
 Инновации
 Культура
 Люди
 Разное
 Скартел-Yota
 Стрим
 Смольный
Учебный процесс
 Образование
 Дипломы
 Курсовые проекты
 Лабораторные работы
 Учебные курсы
 Визуализаторы
 Unimod-проекты
 Семинары
 Стипендии
Наука
 События и факты
 Госконтракты
 Статьи
 Диссертации
 Книги
 Презентации
 Свидетельства
 Сотрудничество
Исследования
 Автоматы
 Верификация
 Биоинформатика
 Искусственный интеллект
 Генетические алгоритмы
 Движение
 UniMod
 Роботы и агенты
 Нейронные сети
 ФЦП ИТМО-Аалто
 Разное

О нас
 Премии
 Сертификаты и дипломы
 Соревнования по программированию
 Прорыв
 Автографы
 Рецензии

Беллетристика
 Мотивация
 Мысли
Медиа
 Видео
 Фотографии
 Аудио
 Интервью

English
 Home

 Articles
 Posters
 Automata-Based Programming
 Initiatives
 Projects
 Presentations
 UniMod
 UniMod Projects
 Visualizers


Поиск по сайту

Яndex



   Главная / Статьи / От тьюрингова программирования к автоматному (версия для печати)


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



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

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

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

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

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

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

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

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

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

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




© 2002—2017 По техническим вопросам сайта: vl.ulyantsev@gmail.com