Универсальность конечных автоматов

• Автор: Сытник, Александр Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Саратов
• Количество страниц: 117 c. : ил

Глава I. Универсальные автоматы
1.1. Универсальность в классах конечных автоматов
1.2. Полнота и анализ универсальных автоматов
Глава 2. Характеризация универсальных автоматов
отношением 8
2.1. 8- эквивалентность в симметрической
полугруппе преобразований
2.2. Эквивалентность графов преобразований
2.3. Рекуррентный синтез о 8-различных преобразований симметрической.1 полугруппы
2.4. Приближенные оценки индекса отношения
- симметрической полугруппы преобразований
2.5. Характеризация универсальных автоматов отношением 8
Глава 3. Применение модели универсального автомата
для решения задач технической диагностики
3.1. Структурно-функциональный метод построения квазиуниверсальных тестов
3.2. Использование модели универсального автомата и метода квазиуниверсальных тестов для построения схем встроенного контроля
Заключение III
Литература

В настоящее время интенсивно развивается теория управляющих систем и, в частности, один из ее разделов - теория автоматов. Основным вопросом данной теории является изучение автомата как математической модели преобразователя дискретной информации.
Актуальной и классической задачей в теории автоматов, как и во всякой математической теории, является задача нахождения в некотором смысле максимального для заданного класса элемента и определение его свойств.
Максимальность или в терминах теории автоматов универсальность понимается в смысле включения в себя всех элементов класса, то есть возможность выделения в нем в качестве подавтомата любого автомата из заданного множества. Существуют две концепции, два подхода к понятию "универсальность^.
Первый из них связан с понятием функциональной полноты и однородной структуры. В 1956 году Минский в работе [ I ] поставил задачу о построении универсального автомата как базового объекта для создания некой однородной структуры, реализующей поведение любого из заданного множества элементов. В 1960 году в ^ впервые дано формальное определение универсального объекта как математической модели, образующей функционально полную систему, решил задачу построения и определения основных свойств универсальной о-д. функции. Затем [^8 _] строится пример универсальной о-д. функции с двумя входными каналами и двумя состояниями. В этом случае, для моделирования закона функционирования любого автомата необходимо каждый раз построение специальной автоматной схемы.
Возникает вопрос: существует ли конечный детерминированный автомат, моделирующий поведение любого из заданного множества авто-гГ мата только за счет изменения соответствующих входных воздействий?

Ответ на этот вопрос связан с изучением второго подхода к понятию универсальность.
можность создания модели, имитирующей функционирование произвольной машины Тьюринга при помощи настройки этой модели /универсальной машины Тьюринга/ соответствующими входными воздействиями /геделевыми номерами/.
Таким образом, универсальность для классов конечных детерминированных автоматов понимается как возможность универсального элемента "настраиваться" на функционирование любого автомата из заданного класса. Одновременно по предположению Минского универсальный элемент должен обладать свойством "быть базовым при построении однородных схем, реализующих достаточно широкий класс автоматов". Задачу о построении такого элемента будем называть задачей универсализации относительно заданного класса.
Из работ, посвященных решению задачи универсализации необходимо отметить следующее.
В [7] предложил метод построения универсальной и многофункциональной /универсальной для некоторого конечного множества/ булевых функций. Возможность получения всех настроек параллельно с определением универсальной функции является отличительной особенностью и несомненным преимуществом данного метода среди подобных работ
22^ . Для некоторых классов конечных автоматов задача универсализации рассматривалась в работах ^2,3^ . Их исследования были посвящены изучению поведения развивающихся оценок функции роста.
Базовым элементом при построении моделей систем такого рода являлся так называемый автомат локального действия /а.л.д./. Было доказано, что а.л.д. есть универсальный автомат для определенного класса. Универсальность а.л.д. достигалась путем изменения структуры
Одновременно с Минским Шеннон в работе
исследовал воз-

где: 5/ подмножество множества 5 , возможно пустое, которое
образует циклы длины J при перестановке
Sj подмножество элементов множества 5 , возможно пустое,
которые образуют циклы длины [ при перестановке Ь
с* с*
Подмножества 0^- и для произвольного j представимы соответственно как:
^ ^ и... /г.1.21.
5/ ГС'УС(/ ' (,ЬЛ. /2.1.22.
где: 5: подмножество элементов множества Б , образующих К-й

цикл длины j /при произвольной нумерации циклов/; при перестановке к
подмножество элементов множества 5 , образующих К
к /К и
цикл длины J при перестановке р>
Построим взаимно-однозначное отображение у следующим образом: вначале установим произвольное взаимно-однозначное соответствие между множествами правых нижних индексов формул /2.1.21./ и /2.1.22./. Такое соответствие всегда существует, так как к^6 (К-//...) Кп ) и более того, их ровно
Без ограничений на общность рассуждений можно считать, что
выбрано тождественное /для фиксированной нумерации циклов/: р У- р А
чм ч;у
5Д-"У
Ч, к] Ч',/о
Предположим, что:
I- у 5су } и Бк - {Бе<,5/!/' }
2. к ыг...$■<.< Р V $>ег...5е,
Определим отображение как