авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |
-- [ Страница 1 ] --

Л. Ф. МАРАХОВСКИЙ

ОСНОВЫ НОВОЙ ИНФОРМАЦИОННОЙ

ТЕХНОЛОГИИ

Фундаментальные основы построения реконфигурируемых

устройств компьютерных систем и

искусственного нейрона

Киев 2012

УДК 004.274

ББК 32.973.2-02

М25

Мараховский Л. Ф.

Основы новой информационной технологии. Фундаментальные

основы проектирования реконфигурируемых устройств компью-

терных систем и искусственного нейрона: монография.

Л. Ф. Мараховский, Н. Л. Михно – Germany: Saarbrcken, LAP LAMBERT, 2012. – 347 с.

Монография рассматривает новое научное междисциплинарное направление, состоящее из четырех новых научных направлений в обработки информации, пред ложенных автором. Это теорию многофункциональных автоматов 1-го, 2-го, 3-го ро да, разработка элементарных схем автоматной памяти, построение реконфигурируе мых устройств компьютерной техники на схемах автоматной памяти и теория по строения цифрового искусственного нейрона. Теория многофункциональных автома тов расширяет классическую теорию автоматов Мили и Мура и позволяет создавать новый тип автомата 4-го рода, контролирующего катастрофические отказы в базовых схемах памяти. Элементарные схемы автоматной памяти расширяют элементную ба зу компьютерных устройств, обладают повышенной надежностью и позволяют в процессе работы изменять структуру запоминаемых состояний. В целом такого сис темного подхода новая информационная технология позволяет проектировать конку рентоспособные реконфигурируемые устройства компьютерной техники и устройст ва искусственного интеллекта © Мараховский Л. Ф., © Михно Н. Л., © ГЭТУТ, Рецензенты:

Стахов А.П. – доктор технических наук, профессор, академик Ака демии инженерных наук Украины, Почетный профессор Таганрогского радиотехнического университета, Президент Международного Клуба Зо лотого Сечения.

Борисенко А.П. – доктор технических наук, профессор, заведую щий кафедрой электроники и компьютерной техники Сумского государ ственного университета МОН молодежи и спорта Украины.

Вербицький В.Г. – доктор технических наук, профессор, директор ІМП НАНУ СОДЕРЖАНИЕ Предисловие……………………………………………….. Список сокращений………………………......................... Введение…………………………………………... Часть І. ОСНОВЫ ТЕОРИИ АВТОМАТОВ МИЛИ, МУРА И МАРАХОВСКОГО……………………………….. 1. Особенности автоматов ………………………………….. 1.1. Развитие теории автоматов..………………………………..… 1.2. Понятия автомата: термины и определения ….......................... 1.2.1. Алфавитный способ преобразования информации.…..… 1.2.2. Понятие об алгоритме 1.2.3. Понятие о дискретном автомате Заключение 2. Абстрактная теория автоматов 2.1. Понятие об абстрактном автомате 2.2. Понятие об абстрактных автоматах Мили и Мура....

2.3. Понятие об многофункциональных абстрактных автоматах Мили и Мура 2.4. Некоторые понятия об изменениях в функционировании и само организации в автоматах ……….…………… 2.5. Некоторые модификации абстрактных конечных автоматов 2.6. Понятие об абстрактных многофункциональных автоматах Ма раховского 2.7. Понятие об абстрактных автоматах, с перестраиваемой структу рой запоминания состояний 2.8. Понятие об абстрактных вероятностных автоматах 3-го рода 2.9. Понятие об абстрактных нечетких автоматах 3-го рода 2.10. Классификация детерминированных абстрактных автоматов 2.11. Классификация недетерминированных абстрактных автоматов 2.12 Понятие об автоматах четвертого рода, контролирующих рабо тоспособность базовых схем памяти Заключение 3. Способы задания автоматов …. 3.1. Некоторые понятия в теории абстрактных автоматов.

3.2. Табличные и графические способы задания классических авто матов Мили и Мура 3.3. Табличные способы задания многофункциональных абстрактных детерминированных автоматов 3.4. Табличные способы задания абстрактных вероятностных авто матов 3-го рода 3.5. Табличный способ задания абстрактных нечетких автоматов 3-го рода.. 3.6. Графические способы задания переходов в многофункциональ ных абстрактных автоматах 3.7. Математическая модель иерархического абстрактного автомата с многофункциональной системой организации памяти 3.8. Способ задания иерархического абстрактного автомата с много функциональной системой организации памяти с помощью поли граммы 3.9. Формулирование полиграммы Заключение Часть 2. ОСНОВЫ ПОСТРОЕНИЯ СХЕМ АВТОМАТ НОЙ ПАМЯТИ………………………………………….…. Введение 4. Монофункциональные элементарные схемы памяти 4.1. Основные понятия 4.2. Основы моделирование компьютерных схем 4.3. Элементарные схемы памяти 4.4. Триггер RS-типа на элементах потенциальной системы 4.5. Триггер RS-типа на элементах динамической системы 4.6. Проблемы обеспечения надежности работы автоматов 4.7. Методы проектирования монофункциональных схем памяти с учетом ограничения элементной базы Заключение 5. Структурная организация многофункциональных схем памяти 5.1. Многофункциональные элементарные автоматы с памятью. Ос новные понятия. 5.2. Метод микроструктурного синтеза элементарных МФСП 5.3. Символьный язык описания элементарных многофункциональ ных схем памяти 5.4. Исследование возможных вариантов многофункциональных схем памяти в символьном числе 5.5. Синтез многофункциональных схем памяти по символьному описанию 5.6. Определение входных слов схем автоматной памяти 5.6.1. Определение однозначных элементарных входных слов 5.6.2. Определение укрупненных элементарных входных слов 5.7. Вопросы надежности многофункциональных схем памяти 5.7.1. Вопросы повышения надежности многофункциональных схем памяти. 5.7.2. Вопросы повышения живучести многоуровневых схем па мяти 5.7.3. Вопросы контроля работоспособности базовых схем памя- ти 5.8. Характеристики параметров многофункциональных схем памя ти Заключение 6. Структурная организация многоуровневых схем памяти 6.1. Основные понятия 6.2. Разработка символьного языка описания многоуровневых схем памяти 6.3. Определение параметров многоуровневых схем памяти посим вольному описанию 6.4. Разработка метода синтеза многоуровневых схем памяти по символьному описанию 6.5. Разработка принципа структурной организации элементарных многоуровневых схем памяти 6.6. Разработка метода проектирования общего автомата стратегии для всей многоуровневой схемы памяти 6.7. Метод логического проектирования многоуровневой схемы па M мяти класса L с одним автоматом стратегии 6.8. Метод логического проектирования многоуровневой схемы па B мяти класса LN с автоматом стратегии для каждой группы много уровневых схем памяти 6.9. Классификация базовых элементарных схем памяти 6.10. Сравнение параметров базовых схем памяти 6.10.1. Определение количества логических элементов, необхо димых для построения схем памяти 6.10.2. Определение максимально возможной нагрузочной спо собности по выходам схем памяти 6.10.3. Определение количества внутренних связей схем памяти 6.10.4. Определение количества внешних связей схем памяти 6.10.5. Определение количества элементов на одно состояние схем памяти 6.10.6. Сравнение рабочей частоты переключения и функцио нальных возможностей схем памяти 6.11. Вопросы построения надежных устройств на многоуровневых схемах памяти 6.11.1. Вопросы надежности многоуровневых схемах памяти 6.11.2. Вопросы живучести многоуровневых схем памяти 6.11.3. Контроль работоспособности МУСП 6.11.4. Повышение надежности устройств, использующих МФСП в МУСП Заключение ЧАСТЬ 3. СИСТЕМНЫЙ ПОДХОД К ПОСТРОЕНИЮ РЕ КОНФИГУРИРУЕМЫХ КОМПЬЮТЕРНЫХ УСТРОЙСТВ Введение 7.1. Развитие реконфигурированных систем с памятью на триггерах 7.2. Разработка методов построения реконфигурированных регист ров на многоуровневых схемах памяти 7.3. Анализ параметров реконфигурированных параллельных реги стров на многоуровневых схемах памяти 7.4. Разработка методов построения реконфигурированных регист ров сдвига на многоуровневых схемах памяти 7.5. Методы построения реконфигурированных счетчиков на мно гоуровневых схемах памяти 7.5.1. Основные понятия 7.5.2. Методы построения реконфигурировананых счетчиков на многоуровневых схемах памяти 7.6. Методы построения реконфигурированного устройства управ ления на многоуровневых схемах памяти 7.7. Методы построения реконфигурированных процессоров и ком пьютеров на схемах автоматной памяти 7.7.1. Введение 7.7.2. Методы построения реконфигурированной архитектуры структуры процессоров на МФСП и МУСП 7.7.3. Исследование последовательной и параллельной обработки иерархической информации в современных процессорах 8. Способов задания иерархических автоматов на многоуровневых схемах памяти 9. Принципы построения реконфигурированных процессоров и компьютеров, одновременно обрабатывающих общую и частную информацию 10. Методы построения реконфигурированного компьютера с уче том «элементного» уровня. 11. Ускорения выполнения алгоритмов в реконфигурированных компьютерных системах на многоуровневых схемах памяти Заключение ЧАСТЬ 4. МОДЕЛЬ ЦИФРОВОГО ИСКУССТВЕННОГО НЕЙРОНА НА СХЕМАХ АВТОМАТНОЙ ПАМЯТИ. Введение 12.1. Предварительные понятия о модели нейрона 12.2. Свойства человеческого мышления 12.3. Основы кратковременной памяти человеческого мозга 12.4. Проблемы создания модели человеческого мозга 12.5. Информационные характеристики нейрона человеческого мозга 12.6. Методы проектирования модели искусственного нейрона на схемах автоматной памяти 12.7. Структурная модель цифрового искусственного нейрона Заключение ВЫВОДЫ Литература ПРЕДИСЛОВИЕ В последнее время многие ученые выражают обеспокоенность по поводу низкой информационной надежностью современных микропроцессоров с памятью на триггерах, используемых в системах управления. Иногда доста точно сбоя одного электронного элемента в микропроцессоре, чтобы система начала выполнять ложную команду, которая может стать причиной аварии.

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

В монографии с системных позиций теории автоматов, рассмотрены многофункциональные автоматы 1-го, 2-го и 3-го рода, которые имеют по два множества входных сигналов: устанавливающих и сохраняющих. Пред ложенные многофункциональные автоматы способны одновременно обраба тывать общую и частную информацию за один машинный такт Т, что очень важно при увеличении быстродействия в реконфигурированных устройствах во время перехода с одного режима на другой. Отдельным случаем рассмот рен автомат 4-го рода, который способен определять катастрофические отка зы в базовых схемах памяти, таких, как: триггер, многостабильная схема па мяти и многофункциональная схема памяти.

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

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

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

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

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

Авторы будут благодарны за замечания данные читателями.

Контактные данные: Леонид Федорович Мараховский, д.т.н., профес сор, основатель научной школы, член-корреспондент РАЕ: (044) 525-77-39, e-mail: marachovsky@ukr.net, Киев-28, Проспект Науки 35, корп. 4, кв. 23.

СПИСОК СОКРАЩЕНИЙ ВТ – вычислительная техника;

ИИ – искусственный интеллект;

МСП – многостабильная схема памяти;

МФСП – многофункциональные схемы памяти;

МУСП – многоуровневые схемы памяти;

ЭА – элементарный автомат;

x(t) – устанавливающий входной сигнал;

e() – сохраняющий входной сигнал;

р (Т) – входное слово;

М – число устойчивых запоминаемых состояний схемы памяти;

rх – число устанавливающих x(t) входных сигналов в схеме памяти;

rе – число сохраняющих e() входных сигналов в схеме памяти;

Fp – предельная рабочая частота переключения;

РQ – нагрузочная способность по выходам;

Scв – число внутренних связей;

Sвc – число внешних связей;

L –·число элементов на одно состояние;

МЭА – многофункциональный элементарный автомат;

БА – базовый автомат;

у1(t) – выходной сигнал автомата 1-го рода;

у2(Т) – выходной сигнал автомата 2-го рода;

у3() – выходной сигнал автомата 3-го рода;

р0(Т) – однозначное входное слово;

ру(Т) – укрупненное входное слово;

СБИС – сверхбольшие интегральные схемы;

ЦИН – цифровой искусственный нейрон.

ВВЕДЕНИЕ Парадигма основы новой информационной технологии на схемах ав томатной памяти – новое междисциплинарное направление, объединяю щее теорию автоматов, теорию построения схем памяти, принципы анализа базовых схем памяти при их катастрофических отказах, методы логического проектирования реконфигурируемых устройств компьютерной техники и принципы построения цифрового искусственного нейрона. Автор надеется, что основы новой информационной технологии на схемах автоматной памяти будут способствовать построению конкурентоспособных устройств. Она по зволит расширить функциональные возможности, повысить надежность и живучесть, позволит выявлению катастрофических отказов в базовых схемах памяти реконфигурируемых устройств вычислительной техники (ВТ), реали зованных с памятью на триггерах, с начала их промышленного использова ния [3–53;

86–95;

97–122;

124–138;

140–143].

Исторически работы по ВТ пошли сразу по двум направления [109]:

попытки смоделировать деятельность мозга, его психофизиологические свойства воспроизвести на логической машине или на электронной вы числительной машине (ЭВМ), или с помощью специальных технических устройств: искусственный интеллект или искусственный разум;

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

В 1981 году Япония предложила программу создания ЭВМ пятого поко ления, которая позволила бы компьютерам частично владеть искусственным интеллектом (ИИ), т. е. самостоятельно составлять программы для решения конкретных задач, принимать самостоятельные решения и т.д. [99]. В году в США была принята стратегическая компьютерная программа, преду сматривающая опережение японских разработок по машинам пятого поколе ния. Соответствующие программы были приняты в Англии, Франции, ФРГ, а также в странах членов СЭВ до 2000 года [109]. К сожалению и эти проекты не дали ожидаемых результатов по ИИ [100–102].

Формально, в 70-80 гг. прошлого века было окончательно установлено, что уровень развития вычислительной техники не позволяет говорить даже о возможности приближения к Искусственному Разуму. «Разумность» автома тических систем была снята с рассмотрения [101].

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

Рис.1. Динамика развития цифровых технологий Прогнозирование эволюционного развития цифровых микросхем и тех нологий с использованием математических формул, предложенных В. И. Акуновым, продемонстрировало совпадение прогнозов с реальными достижениями в этой области: линейная зависимость (закон Мура) по дан ным всемирно известной фирмы Интел (рис. 1) перестанет действовать к 2010 – 2015 г.г. [139].

В ноябре 2011 г. в Портленде (штат Орегон) Supercomputing Conferen ce'09 фирма IBM заявила о существенном прогрессе в создании вычисли тельной системы, которая симулирует и эмулирует способность мозга чувст вовать, воспринимать, действовать, взаимодействовать, познавать, и при этом сравнима с мозгом по низкому энергопотреблению и размерам.

BlueMatter – новый алгоритм, созданный IBM Research в сотрудничестве Рис. 2. Суперкомпьютер BlueGene/Р, на котором симулировалась кора головного мозга со Стэнфордским университетом, использует суперкомпьютерную архитек туру BlueGene/Р (рис. 2) для измерения и отображения связей между всеми локусами коры и подкорки в мозге человека с помощью диффузной спек тральной томографии [1–2;

96].

Специалисты компании IBM разработали передовой процессор, имитирующий работу человеческого мозга. «Это наше первое когнитивное компьютерное ядро, которое сочетает в себе вычисления в виде нейронов, память в виде синапсов, а связи - в виде аксонов», - рассказал в интервью CNET руководитель исследования Дхармендра Модха.

«Биологический» процессор основывается на алгоритме BlueMatter, который был разработан 2009 г. при попытке выявить связь между корковыми и подкорковыми структурами головного мозга. Разработка этого алгоритма была необходима для того, чтобы понять, как этот орган обрабатывает и обменивается информацией, отметил Модха [1–2].

В статье [96] указывается, что «современные вычисления базируются на модели хранимой программы, традиционно реализуемой в цифровых синхронных последовательных централизованных схемах общего назначения с явной адресацией памяти, которая без разбора перезаписывает данные и создает границу между вычислениями и данными. В отличие от этого когнитивные вычисления, подобные тем, что выполняет мозг, будут использовать повторяемые вычислительные блоки, нейроны и синапсы, реализуемые в смешанных аналого-цифровых асинхронных параллельных распределенных реконфигурируемых специализированных и отказоустой чивых биологических субстратах с неявной адресацией памяти, которая обновляется только при изменении информации, размывая границы между вычислениями и данными».

По мнению Модха, такие процессоры могут прийти на смену архитекту ре фон Неймана, на которой построено большинство современных компью теров. Когда появятся первые коммерческие приложения для «биологиче ских» чипов, Модха не сообщил. Как считает аналитик Рик Доэрти, глава En visioneering Group, такие программы могут быть готовы к 2015 или 2016 году [1–2;

96].

Для создания подобных чипов в IBM объединили достижения в области нанотехнологий, нейробиологии и суперкомпьютеров. Начальный этап ис следований в области нейросинаптических чипов профинансировало амери канское агентство передовых научных разработок DARPA, выделив на про ект 21 млн. долларов. Исследования велись в рамках научного проекта Sys tems of Neuromorphic Adaptive Plastic Scalable Electronics (SyNAPSE). Сейчас исследователи говорят, что созданные чипы пока способны анализировать данные, но не способны самоперестраиваться, а также память еще нахо дится не в нейронах. Данные способности, как надеются исследователи, у них появятся в будущем.

Будущие приложения будут предъявлять повышенные требования к компьютерам и нам либо придется значительно наращивать вычислительные возможности чипов, либо делать их более интеллектуальными, - говорит Дхармендра Модха, руководитель данного проекта в IBM Research.

Исследуя неудачи и трудности создания ИИ на современном этапе автор приходит к выводу, что фундаментальные исследования в области человеческого мозга, его нейрона еще не привели к созданию соот ветствующей модели клетки нейрона, его модели связей, характеризующих реальный объект. В связи с этим и используются супер-компьютеры (рис.2), которые по внешним характеристикам создают пока только модель «действия кошки».

Крупномасштабная симуляция деятельности коры головного мозга – но вое междисциплинарное направление, объединяющее вычислительную неврологию, методологию симуляции и суперкомпьютеры, которое пред ложили американцы. В области создания когнитивного компьютера, рабо тающего аналогично мозгу, симуляция коры является крайне важной техно логией для проверки гипотез о структуре, динамике и функциях мозга [96].

В данной монографии рассматривается фундаментальные основы реконфигурируемых устройств компьютеров, которые являються новым научным направлением, объединяющее теорию автоматов, схемы памяти, реконфигурируемые устройства компьютеров и искусственного нейрона на схемах автоматной памяти [54–55;

60–64;

66–68;

70–85].

Доктор технических наук, профессор Стахов А.П. пишет в статье [129], что недавно пришло сообщение об очередном аварийном запуске космиче ского аппарата связи «Меридиан». Считается, что потери от аварийного за пуска этого космического аппарата могут составить до 2 млрд. рублей. До этого подобные аварийные запуски происходили и ранее (при запуске спут ников «Глобалстар»). Одной из возможных причин такого «сбоя» могут быть «сбои» в цифровой системе управления двигателями. По странному совпаде нию, аварии начались после усовершенствования системы управления и ее переводе на цифровую технику. И вот в этом, возможно, и «зарыта собака».

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

На низкую информационную надежность современных микропроцессо ров (особенно иностранного производства) обращает внимание выдающийся российский ученый академик Ярослав Хетагуров, который пишет, что при менение микропроцессоров, контроллеров и программного обеспечения вы числительных средств (ВС) иностранного производства для решения задач в системах реального времени (СРВ) военного, административного и финансо вого назначения таит в себе большие проблемы. Это своего рода «троянский конь», роль которого только стала проявляться. Потери и вред от их исполь зования могут существенно повлиять на национальную безопасность России, Украины и многих других стран [137].

Стахов А.П. в своих работах [128–130], развивая мысли академика Хета гурова Я.А., сделал следующее, на первый взгляд парадоксальное утвержде ние: «Таким образом, человечество становится заложником классической двоичной системы счисления, которая лежит в основе современных микро процессоров и информационных технологий. Поэтому дальнейшее развитие микропроцессорной техники и основанной на ней информационной техноло гии и классической двоичной системы счисления следует признать тупико вым направлением. Двоичная система не может служить информационной и арифметической основой специализированных компьютерных и измеритель ных систем (космос, управление транспортом и сложными технологическими объектами, нанотехнологии), а также наноэлектроннных систем, где пробле мы надежности, помехоустойчивости, контролеспособности, стабильности, живучести систем выходят на передний план».

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

На взгляд авторов, одной из проблем в создании нового класса перестраиваемых компьютеров и создания модели исскуственного нейрона лежит широко используемая двоичная память, которая представляет собой закрытую структуру, «нулевую» избыточность и обладает жестким алгоритмом работы, не надежна при работе компьютерных систем и, как пишут авторитетные ученые: Я.А. Хетагуров [137], А.П. Стахов [128–130], не способна к перестройки структуры своих запоминаемых состояний.

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

60;

64;

70], делается попытка представить базовую перестраиваемую автоматную схему памяти, которая имеет ряд преимуществ перед базовой двоичной схемой памяти (RS триггера). Это позволит по иному взглянуть на создание реконфигурируемых типовых устройств ВТ и самих суперкопьютеров и принципы построения цифрового искусственного нейрона.

Часть І.

ОСНОВЫ ТЕОРИИ АВТОМАТОВ МИЛИ, МУРА И МАРАХОВСКОГО 1. Особенности автоматов 1.1. Развитие теории автоматов Теория конечных автоматов характеризуется широким использованием в различных областях применения дискретной техники. Эта теория получила первоначальное развитие на базе булевой алгебры и модели дискретного уст ройства в виде так называемого конечного автомата. На ней основано раз витие методов логического проектирования дискретных устройств и методов построения тестов для проверки последних, обеспечение надежности и ус тойчивости их работы, решения задач «конструирования» дискретных уст ройств. Возникли отдельные ответвления теории конечных автоматов в виде теории вероятностных и нечетких автоматов, коллективного поведения авто матов, экспериментов и т. д. [14;

18–21;

24–26;

34–35;

90;

119;

125;

140], Теория автоматов представляет собой раздел теории управляющих ма шин, изучающий математические модели преобразователей дискретной ин формации, называемые автоматами (от греч. аutmatos – самодействующий).

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

В Библии сказано, что в начале было слово… Когда-то язык был слабым преобразованием вещей в сознании человека, прозрачной зыбкой моделью, отделяющий человека от неживой материи. За прошедшие тысячелетия язык развился до такой степени, что сам проявляет тенденцию к независимому движению и управляет развитием разума. Он сконцентрировал в себе все тайны Вселенной, в нем, возможно, скрыты ответы на извечные вопросы бы тия.

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

Наши модели вначале нечеткие. Это наглядно видно на примере изуче ния счета ребенком с 2 до 5 лет [65]. Ему необходимо повторить от 6-ти до раз, чтобы он мог вначале различать один палец от двух. Наши мысли, сфор мированные на основе независимых моделей тоже нечеткие. Этим мы суще ственно отличаемся от дискретного компьютера!

Человек, помимо способности рассуждать и логически мыслить, облада ет, как все живые существа, способностью принимать в расчет параллельно соображения, как общего, так и сопутствующего характера. Не рискуя сильно ошибиться, как писал французский профессор Арнольд Кофман, – «можно предсказать, что технология будет развиваться по пути, сближающем идеи компьютерного и обычного человеческого мышления в ожидании того дня, когда компьютеры начнут обрабатывать общую информацию принципиально параллельно с частной, без предварительной последовательной обработки»

[49].

Понятие вероятности развивалось с XVII века. Идея вероятности появи лась в процессе развития квантовых представлений в физике в начале ХХ столетия. Возник вопрос о соотношения динамических и статических зако нов. Известна дискуссия между Нильсом Бором и Альбертом Эйнштейном. В этой дискуссии Бор отстаивал вероятностный характер микропроцессов, а Эйнштейн отстаивал классическое представление, утверждая, что «Бог не иг рает в кости». К сожалению, эта дискуссия не завершилась и до сих пор.

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

Теория автоматов возникла в середине ХХ столетия в связи с изучением свойств конечных автоматов. Исторически наиболее рано начала развиваться теория комбинационного синтеза релейно-контактных схем с использовани ем булевой алгебры [3–6;

15;

21;

36;

87;

93].

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

В работах академика В.М. Глушкова и его школы была решена задача сопряжения этапов абстрактного и структурного синтеза и представление всей структурной теории автоматов в виде, пригодном для решения проблем синтеза цифровых автоматов с запоминающими двоичными элементами лю бой природы. Эта объединенная математическая теория цифровых автоматов была доведена до практического применения при разработке автоматизиро ванной системы логического проектирования дискретных устройств [24–26].

В основу этой теории были положены автоматы Мили (автоматы 1-го рода) и Мура (автоматы 2-го рода) с памятью на двоичных триггерах [24].

В настоящее время вся теория автоматов делится на теорию абстрактных и структурных автоматов Мили и Мура, функционирующих в дискретные моменты времени ti (i = 1, 2, 3 …,n,…).

Настоящий раздел посвящен изложению существующей классической теории автоматов Мили и Мура с памятью на двоичных триггерах и функ ционирующих в дискретные моменты времени ti, выявлению их ограничений.

В этом разделе также предлагается более общая теория многофункциональ ных автоматов Мараховского 1-го и 2-го рода, частным случаем которой яв ляются автоматы Мили и Мура, и теория автоматов 3-го рода [55;

59;

64].

Этот материал неоднократно излагался автором и его последователями в ряде работ [70–71;

79;

83–84], в учебных пособиях при чтении обязательного раздела по теории автоматов в курсе «Компьютерная схемотехника» [54–55;

66;

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

В настоящее время широко разрабатывается теория построения рекон фигурируемых систем на «автоматном» уровне. Память на триггерах, кото рая применяется в этих устройствах и имеет жесткую (неизменяемую) струк туру, не дает возможность использовать «элементный» уровень в теории по строения реконфигурируемых систем [32;

39;

42;

91;

104–106;

138;

143].

Расширенная автором теория автоматов позволила создать теорию про ектирования реконфигурируемых устройств с учетом «элементного» уровня с памятью на элементарных многофункциональных и многоуровневых схе мах памяти [61–63].

1.2. Понятия автомата: термины и определения 1.2.1. Алфавитный способ преобразования информации Философы и математики, заметив одинаковые законы развития разнооб разных объектов, предложили общее понятие – сложная система.

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

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

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

Существуют два различных подхода с информационной точки зрения:

изучение явлений в непрерывном или дискретном времени. Характерным для непрерывного подхода являются вещественные числа, которые могут изме няться непрерывно. При дискретном подходе временные координаты прини мают дискретные ряды значений. Обычно нулевой момент времени считается начальным, а остальные моменты времени в соответствии с их номерами: 1, 2, …, n,… Чаще всего ограничиваются рассмотрением конечных временных интервалов, начиная с нулевого или с первого момента времени.

Реальные устройства обладают рядом ограничений при приеме инфор мации:

чувствительность воспринимающего устройства дает ему возмож ность различать лишь конечное число градаций значений величин, характе ризующих процесс;

разрешающая способность устройства приводит к тому, что достаточ но малые участки пространства воспринимаются как отдельные точки;

полосы пропускания воспринимающего информацию устройства не по зволяют ему различать очень близкие моменты времени.

С точки зрения воспринимающего устройства можно ограничиться дис кретным временем, деля реальное непрерывное время на столь малые интер валы, чтобы концы этих интервалов воспринимались объектом как один мо мент времени.

С учетом ограничений устройства, воспринимающего информацию, лю бая непрерывная информация сводится, фактически, в дискретную информа цию. Отсюда следует универсальность алфавитного способа задания ин формации.

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

Абстрактным алфавитом называют любую конечную совокупность объектов (букв) данного алфавита. Природа этих объектов в данном случае не существенна. Важно лишь то, чтобы рассматриваемый алфавит был ко нечным, то есть состоял из конечного числа букв [24–26]. В абстрактном ал фавите можно считать целые слова конкретного языка отдельными буквами, если это необходимо при удобстве преобразования информации.

Различие между словами алфавитов разговорных языков и словами абст рактного алфавита состоит в том, что слово в абстрактном алфавите может содержать и простое сочетание букв, которое в обычном языке не имеет ана логов и считается бессмысленным (например, сочетание букв «ккллммнн»).

Количество букв в конкретном слове называют обычно длиною этого слова.

Наряду со словами положительной длины (состоящими не менее чем из од ной буквы) в абстрактном алфавите рассматривается также пустое слово, не содержащее ни одной буквы.

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

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

При рассмотрении многофункциональных автоматов Мараховского (многофункциональных автоматов 1-го, 2-го и 3-го рода) с памятью, которые в процессе функционирования под влиянием пустого слова е могут изменять структуру запоминания в схеме памяти, дискретное автоматное время не подходит. В этом случае вводиться непрерывное автоматное время, в кото ром слову е выделяется длина, как букве абстрактного алфавита [55].

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

Рассмотрим понятие преобразование информации, которая представлена в алфавитной форме. С абстрактной точки зрения преобразование информа ции есть отображение одного класса явлений в другой класс явлений в со ответствии с определенным законом. Например, явление из некоторого класса А явлений влечет за собою некоторое определенное явление из того же самого или из другого класса явлений В, то говорят, что задано преобра зование информации = f( ), (1.1) где стрелка «» – знак преобразования информации, то есть отображение явления в явление.

Если подобное отображение осуществляется определенным объектом, то такой объект называется преобразователем информации.

Алфавитным отображением (оператором) называется всякое соот ветствие (функция), сопоставляющее слово в том или ином алфавите слова в том же самом или в некотором другом фиксированном алфавите.

Первый алфавит при этом называется входным, а второй – выходным ал фавитом другого оператора. В случае совпадения входного и выходного ал фавита говорят, что алфавитный оператор задан в соответствующем алфави те.

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

Под термином алфавитный оператор понимают однозначное, вообще говоря, частично определенное отображение множества слов во входном ал фавите оператора в множество слов в его выходном алфавите. Чтобы вход ной и выходной алфавиты оператора совпадали, достаточно их объединить в один алфавит.

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

Большое значение имеет кодирующее отображение, которое называют просто кодированием. В наиболее простом виде кодирование заключается в сопоставлении каждой букве а1 алфавита А некоторой конечной последова тельности b b... b в алфавите B, называемой кодом соответствующей бук i1 i2 ik вы. Различным буквам алфавита А сопоставляются различные коды. Коди рующее отображение должно быть обратимым, то есть взаимная однознач ность соответствующего кодирующего отображения. Обратимость кодирова ния будет всегда выполняться, если соблюдаются следующие два условия:

1. коды различных букв исходного алфавита А различны;

2. код любой буквы алфавита А не может совпадать ни с каким из отрез ков кодов других букв алфавита В.

С помощью простейших эквивалентных преобразований, информацию, заданную в любом конечном алфавите, можно записать в стандартном дво ичном алфавите, содержащим две цифры (буквы) 0 и 1. Двоичное кодирова ние должно соблюдаться при выполнении следующего соотношения:

2m n, (1.2) где n – число различных букв исходного алфавита А;

m – количество цифр двоичного алфавита, необходимых для кодирования букв алфавита А.

Кодирование информации в двоичном алфавите неоднозначно. Для лю бого исходного алфавита существует бесконечное множество таких преобра зований. Такие преобразования называются двоичным кодированием исход ной информации.

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

Это утверждение очень важно, потому что в реальных дискретных уст ройствах обычно значение сигнала разбивается на два типа: высокое давле ние – низкое давление, высокий потенциал – низкий потенциал и т. д., кото рые условно принимаются в двоичном алфавите за 1 или 0.

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

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

Предложил его автор книги c математики Abu Jafer Mohammed ibn Musa al Khowarizmi. Он определил его как определенный специальный метод разре шения поставленной проблемы.

Любое целенаправленное действие сложной системы связано с понятием алгоритма. Он определяет последовательность действий объекта для дости жения цели. Так первобытные люди придумывали алгоритмы охоты и изо бретали алгоритмы первых кулинарных рецептов. Алгоритмы повседневной жизни человека отличаются неоднозначностью и расплывчивостью выбора принятия решений, не всегда оптимальным исполнением. Это соответствует действию системы в ситуации с неполной информациею. Когда, как говорят, «картина» для человека ясна, то он старается действовать наиболее опти мальным или известным ему способом.

Человечество всегда искало способы описания найденных правил для решения своих задач в виде алгоритмов. Сохранились древние магические рецепты, математические тексты, книги боевого искусства, где описывались приемы действий в тех или иных ситуациях. Сохранились и переиздаются книги духовного содержания, такие как: Библия, Талмуд, Коран, где раскры ваются расплывчатые алгоритмы духовного воспитания человека.

Потребности человечества в обобщении многочисленных подходов к решению разнообразных задач привели к созданию теории алгоритмов.

Понятие алгоритма является одним из фундаментальных понятий со временной математики. В математической теории алгоритмов существует большое разнообразие определений алгоритма, которые ориентированы на различные способы вычислительной реализации. Например, арифметическое исчисление предикатов (К. Гедель, 1931), -определимые (А. Черч, 1936) и частично-рекурсивные (С. Клини, 1936) функции, машины Поста и Тьюринга (Э. Пост, 1936 и А. Тьюринг, 1937), алгоритмы Маркова (А. А. Марков, 1951) и многих других видных ученых. Попытку описать общую теорию алгорит мов предпринял В. М. Глушков в книге «Теория алгоритмов» [25], в которой он с системных позиций описал абстрактную теорию алгоритмов и связал ее с компьютерами, автоматами и самосовершенствующимися системами.

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

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

Алгоритмы могут быть однозначные, вероятностные, нечеткие, само совершенствующиеся и т. д.

Примером однозначного алгоритма может быть система правил сложе ния целых чисел в произвольной позиционной системе счисления (двоичной, восьмеричной, десятичной и т. д.), которая состоит из правил поразрядного сложения и определения поразрядного переноса в старший разряд. Этот ал горитм сложения чисел С = А + В можно задать в формульном виде так [65]:

a b, при ai bi q;

0, при ai bi q, сi i i pi 1 (1.3) ai bi q, при ai bi q, 1, при ai bi q.

где сі — цифра і-го разряда результата;

рі+1 — перенос в і+1 разряд;

q– основание системы счисления.

Этот алгоритм перерабатывает слова а+b в алфавите, состоящим из q цифр и знака сложения, в слова в том же алфавите, но без знака суммы (+).

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

Игру в шахматы можно трактовать как преобразование слов в конечном алфавите. В качестве алфавита здесь применяются символы шахматной но тации. Словами считают конечные последовательности букв алфавита. Одни последовательности представляют собою шахматные позиции, а другие – бессмысленные наборы символов, как например, 3КЛad. Алгоритм задается лишь для слов, представляющих осмысленные позиции в позицию, возни кающую из нее после выполнения очередного хода. Опыт игры в шахматы показывает, что можно составить конечную систему стратегических правил, позволяющих в каждой конкретной ситуации выбрать единственный наи лучший (в некотором смысле) ход. Присоединяя эту систему стратегических правил к правилам движения фигур, получаем алгоритм, который, несмотря на свою неоднозначность, можно назвать алгоритмом шахматной игры. Раз работанный машинный алгоритм шахматной игры позволил компьютеру вы играть у чемпиона мира Каспарова [47].

Нечеткие (размытые, расплывчатые или неопределенные) алгоритмы, допускающие использования нечетких инструкций, широко распространены в различных сферах человеческой деятельности. Они позволяют описывать приближенные рассуждения и, следовательно, являются полезным инстру ментом для приближенного анализа таких систем и процессов принятия ре шений, которые слишком сложны для применения общепринятых количест венных методов [34–35;

49].

Интересными типами алгоритмов являются самосовершенствующиеся (обучающие), которые обычно задаются в виде специальным образом орга низованной системы алгоритмов [25].

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

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

Одно из важнейших фундаментальных понятий теории алгоритмов яв ляется рекурсия. Под рекурсией в общем смысле понимают такой способ ор ганизации системы, при котором она в отдельные моменты своего развития, определяемые ее правилами, может создавать (вызывать) собственные изме нения копий, взаимодействовать с ними и включать их в свою структуру. За коны изменения копий при вызове также включаются в правила системы и могут зависеть от многих параметров: от состояния системы и других под систем в момент вызова копии, от информационного наполнения заданных параметров, от правил самой системы. Частным случаем является чистая ре курсия, в которой отсутствуют изменения при вызове копии. Существует многообразие вариантов поведений копий. Они могут существовать и разви ваться параллельно с главной системой, исчезать после своего этапа функ ционирования, по-разному взаимодействовать между собой. Все определяет ся правилами системы. В теории алгоритмов доказано, что, используя рекур сию, можно из ограниченного количества функциональных единиц получить все многообразие вычислительных функций [10].


При организации цикличных процессов используются рекурсивные вы ражения, которые описывают любой член последовательности чисел. Таким примером могут быть числа Фибоначчи, где первые два члена равны 1, а ос тальные вычисляются с помощью формулы ai = ai-2 + ai-1. Такая формула на зывается рекурсивною. Входными данными для каждого последующего ша га являются результаты предыдущего [128;

130].

Структурная блок схема алгоритма определения ряда чисел Фибоначчи, чтобы последнее число не превышало 100, представляет вычислительный рекурсивный процесс с неизвестным числом повторений (рис. 1.1).

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

В.М.Глушков приводит один из таких способов, принадлежащий А.А. Маркову [25].

Алгоритмы А.А. Маркова, называемые также нормальными алгорит мами, преобразуют слова, заданные в любом конечном алфавите А = А(а1, …, an), в слова в том же самом алфавите, причем, как правило, алгоритм ока зывается определенным лишь для части слов и задает, следовательно, час тичное отображение.

НАЧАЛО A(1) = 1 : A(2) = 1 : I = так A(I) 100 КОНЕЦ ні A(I) = A(I - 2) + A(I - 1) A(I - 2) = A(I - 1) : A(I -1) =A(I) Рис. 1.1. Определение чисел Фибоначчи С достаточной убедительностью В.М. Глушков показал, что любой ал горитм эквивалентен некоторому нормальному алгоритму. Поэтому, не на рушая общности, говоря о произвольном алгоритме, иметь в виду только нормальные алгоритмы.

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

Теория машинных алгоритмов стала важною частью теории алгоритмов и прикладной математики.

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

В данной работе основное внимание будет уделяться цифровым автома там (компьютерам), которые функционируют в автоматном времени. Начи ная с 40-х годов ХХ столетия, вся цифровая вычислительная техника проек тировалась в целом с использованием классической теории автоматов Мили и Мура, память в которых использовалась в основном на триггерах (элемен тарных монофункциональных схемах памяти с закрытой структурой и с «ну левой» избыточностью). Все существующие машинные алгоритмы в той или другой мере использовали только один однозначный тип перехода в автома тах Мили и Мура – детерминированный переход за один машинный такт из одного состояния в другое, который зависел от предыдущего состояния ав томата а(ti-1) и входного сигнала х(ti) в дискретный момент времени ti. Это обстоятельство определило последовательность работы машинных алгорит мов. Для параллельных алгоритмов необходимо было использовать анало гичную дополнительную аппаратуру. Примером может служить использова ния не менее двух сопроцессоров в компьютере и т. д.

С появлением многофункциональных автоматов Мараховского на схе мах автоматной памяти [55;

58–64;

66–67;

70–85], возможности теории алго ритмов расширились в связи с качественно новыми дополнительными пере ходами в устройствах компьютера (hardware) [59]. Автоматная схема памяти, используя меньшее количество аппаратуры на одно запоминаемое состояние по сравнению с триггерами, в тоже время, оказалась в состоянии осуществ лять качественно новые переходы в автоматах.

Автоматная схема памяти способна еще выполнять качественно новые переходы, такие как [64]:

1. детерминированный переход за счет входного «пустого» сигнала е, то есть осуществлять переход за один машинный такт по двум пере менным х и е;

2. вероятностный переход в одно из подмножеств автомата, которые сохраняются под влиянием входных сигналов е;

3. нечеткий переход в одно из четких подмножеств автомата, которое входит в нечеткое множество.

Появление возможности осуществлять качественно новые переходы в схемах памяти позволило Мараховскому и его ученикам расширить теорию автоматов [56–64;

66–85]. Авторы надеются, что это обогатить в дальнейшем и теорию компьютерных алгоритмов, и теорию построения устройств ком пьютеров, а также сможет явиться элементной базой для построения рекон фигурируемых устройств, которой недостает в современных работах по ког нитивному направлению при создании модели человеческого мозга [1–2;

101].

Подводя итоги можно сказать, что рассмотрение многофункциональных автоматов, предложенных Мараховским [55], функционирование которых рассматривается в непрерывное автоматное время, расширяет теорию клас сических автоматов Мили и Мура и создает в ней новое направление, позво ляющее описывать устройства на схемах автоматной памяти, создавать каче ственно новые вычислительные алгоритмы. Построение многоуровневых схем памяти на основе многофункциональных автоматов, которые не только изменяют структуру запоминания состояний, но и определяют направление запоминаемой информации для образования связей с новыми схемами памя ти, необходимых для создания нейронных сетей [1–2;

92;

96;

101].

1.2.3. Понятие о дискретном автомате Дискретными автоматами Мили и Мура называют устройства преобра зующие информацию в дискретные моменты времени, которые в математике отождествляются как точка на числовой оси (рис. 1.2, а) ti (i = 0, 1, 2, …, n, …), а в реальном устройстве как такт t (рис. 1.2, б).

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

ti-1 ti ti+ Рис. 1.2, а. Точки на числовой оси Uв t пустое такт t слово е Такт машинный Рис. 1.2, б. Машинний такт Основным качеством, выделяющим дискретные автоматы из числа всех других преобразователей информации, является наличие дискретного (при этом в реальных устройствах всегда конечного) множества внутренних со стояний и свойства скачкообразного перехода из одного состояния в другое во время такта t машинного такта (рис. 1.2, б), который занимает не более двух-трех задержек э элемента. Скачкообразный переход означает возмож ность трактовать его как мгновенный (на определенной степени абстракции), который совершается непосредственно, минуя какие-либо состояния. Такая абстракция, достаточно хорошо описывает основные свойства реальных цифровых автоматических устройств (прежде всего устройств компьютеров и самих компьютеров) и поэтому принята для построения теории цифровых автоматов.

Второе допущение состоит в том, что переход в следующее состояние оказывается возможным после переходного процесса в схемах памяти авто мата, которые имеют разброс параметров, но для данного автомата составля ет некоторый фиксированный промежуток времени, который обычно выби рается равным четырем задержкам э элемента. Такой интервал дискретности автомата обычно выбирается как такт t машинного такта Т (рис. 1.2. б.).

Промежуток между тактами t в теории автоматов принято называть пустым словом е нулевой длины, т. к. под воздействием слова е автомат не способен переходить из одного состояния в другое, а только, выполняет функцию e сохранения установленного состояния [64]. Такое допущение дает возмож ность рассматривать функционирование цифрового автомата Мили или Му ра в дискретном автоматном времени ti (рис. 1.2, б). При построении такого дискретного автоматного времени различают два основных случая:

1. синхронные автоматы, в которых машинный такт определяется ге нератором синхронизирующих импульсов, и, обычно, имеет одинаковые вре менные промежутки такта t, во время которого поступают устанавливающие х(t) входные сигналы на входы автомата. Промежутки между тактами t, на которые поступают пустые входные слова е, в работе автоматов Мили и Му ра не принимаются во внимание потому, что они не способны участвовать в переходах схемы памяти автоматов на триггерах;

2. в асинхронных автоматах дискретное время определяется исключи тельно лишь в момент переходов в схемах памяти автомата из одного со стояния в другое.

Теория асинхронных автоматов существенно отличается от теории син хронных автоматов тем, что в ней рассматриваются не только моменты фак тически имевших место переходов, но также и такие переходы, которые в данный момент возможны, но не произошли переходы. К числу таких мо ментов причисляют моменты прихода входных сигналов х(t) импульсного типа (мгновенных) и изменения уровня напряжения сигналов потенциально го типа, действующих во временном интервале такта t (рис. 1.2, б). При этом считают, что интервал дискретности автомата ограничивает минимально возможное расстояние между дополнительно вводимыми моментами авто матного времени. При таком допущении теория асинхронных автоматов в ряде случаев может быть сведена к синхронному случаю, поскольку факти чески длины интервалов между последовательными моментами дискретного автоматного времени в идеализированной теории автоматов (без учета пере ходных процессов) не имеет никакого значения, так как на автомат в этот момент поступает пустое слово е нулевой длины. Имея в виду такое обстоя тельство, в функционировании автоматов Мили и Мура используется абст рактное дискретное автоматное время, принимающее целые неотрица тельные значения: t = 0, 1, 2, …, n, …, и строится теория, как теория после довательных синхронных автоматов, хотя в действительности она охватыва ет в значительной мере и теорию асинхронных автоматов.


Переходы из одного аi состояния автомата в другое ak вызываются входными сигналами x(t), возникающими вне автомата и передающимися в автомат по конечному числу входных каналов. В отношении х(t) входных сигналов цифровых автоматов принимаются два допущения: во-первых, для любого цифрового автомата число различных х(t) входных сигналов обяза тельно конечно, а, во-вторых, х(t) входные сигналы рассматриваются как причина перехода автомата из одного состояния в другое и относятся к мо ментам времени, определяемым соответствующими им переходами. Особо следует подчеркнуть, что реальный физический входной сигнал, вызываю щий изменения состояния автомата в момент времени ti, может кончиться до наступления этого момента, однако, тем не менее, он относится именно к моменту времени ti, а не ti-1.

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

В многофункциональных автоматах Мараховского, которые названы по фамилии предложившего их автора, используется автоматная память [61–– 63], вводится и используется автоматное непрерывное время. В автоматном непрерывном времени кроме такта ti используется еще промежуток между тактами ti, интервал которого обозначим символом « ». Это объясняется тем, что в интервале используется сохраняющий входной сигнал е( ), ко торый в автоматах Мили и Мура называется пустым словом нулевой длины и не учитывается при синтезе автоматов, а в многофункциональных автома тах может использоваться для осуществления укрупненных переходов в ав томатной памяти автомата.

Рассмотрим автоматное непрерывное время с учетом синхронных сиг налов j и дадим ряд определений.

Определение 1.1. Тактом t назовем промежуток времени, на протяже i нии которого на автомат можно подавать произвольный синхронизирующий сигнал i.

Определение 1.2. Внутренним тактом назовем меньший открытый j промежуток времени между появлениями синхронизирующих сигналов i.

T j Определение 1.3. Внешним тактом назовем меньший открытый справа промежуток времени, который соответствует периоду синхронизиро ванного сигнала i.

Такты, что определены, можно выразить такой формулой:

(1.4) T j t j j ;

j 0,1, 2,..., n,....

Информационные входные сигналы х(t) подаются на входные каналы сложного автомата и синхронизируются сигналом j. Эти входные сигналы воздействуют на автомат в автоматное непрерывное время такта t.

j Определение 1.4. Внутренним единичным тактом 0 автоматного непре рывного времени назовем меньший открытый промежуток времени между появлением двух произвольных и последовательных синхронизированных сигналов р и р + 1.

Определение 1.5. Внешним единичным тактом Т0 назовем меньший от крытый справа промежуток времени, который соответствует периоду време ни между появлением двух произвольных и последовательных синхронизи рующих сигналов р и р + 1.

Внешний единичный такт Т0 в соответствии со временем равен сумме продолжительности такта t и внутреннего единичного такту 0. Эта зави j симость рассматривается таким равенством:

Т0= t + 0. (1.5) j T j Продолжительность внешнего такта равна продолжительности внешнего такта Та автомата. За один внешний такт Та на автомат воздейст вуют все синхронизирующие сигналы j по одному разу.

Определение 1.6. Внешним тактом Та автомата назовем меньший откры тый справа промежуток времени, который соответствует периоду воздейст вия всех синхронизирующих сигналов j (j = 1, 2,…, C) на входных каналах автомата.

Автомат, что описывает реальное устройство компьютера, должен удовлетворять простейшим требованиям надежности и стабильности со стояний аі и выходных сигналов уі.

Необходимо учитывать, что на входные каналы элементарных автома тов поступают сигналы определенной продолжительности j.

Под влиянием входного сигнала x(t) во время такта t элементарный j автомат с памятью может переходить в определенное состояние при реали зации однозначного перехода. Под воздействием входного сигнала е() во время внутреннего единичного такта 0 элементарный многофункциональ ный автомат с памятью может переходить в новое состояние при реализации функции укрупненного, вероятностного или нечеткого перехода.

Новое установленное состояние элементарного автомата может сохра няться после окончания такта t при однозначном переходе или после j внутреннего единичного такта 0 при реализации функций укрупненного или вероятностного перехода.

Временные соотношения синхронизирующих и входных сигналов ил люстрирует рис. 1.3.

Выходной сигнал уj элементарного автомата фиксирует новое устойчи вое состояние в автомате и сохраняет неизменным это состояние на всем T j. T j определяется временном отрезке Отрезок в соответствии с такой формулою:

T j = – 0. (1.6) j Внешний такт Та автомата своею продолжительностью равный сумме внешних единичных тактов Т0:

C (T Ta ) j. (1.7) j Автоматное непрерывное время дает более полную возможность иссле довать закон функционирования автоматов Мили и Мура, реализованных на триггерах, чем дискретное автоматное время tі. Однако, исследовать много функциональные автоматы Мараховского, реализованные на схемах авто матной памяти, на протяжении внутреннего такта і, необходимо только в автоматном непрерывном времени [64].

U t e1() х1(t) U t t t1 Т Т Рис. 1.3. Временные соотношения синхронизирующих и входных сигналов В автоматах Мили, рассматриваемых в автоматном дискретном време ни, выходной сигнал у1(t) определяется парой (х(t), а(t-1)), а сам автомат на зывается автоматом первого рода.

В автоматах Мура, рассматриваемых в автоматном дискретном времени, сдвинутый выходной сигнал у2(Т) определяется парой одинаковых состоя ний а(t) и а(), где Т = t +. Состояние а(t) устанавливается только после перехода автомата в это состояние под воздействием х(t) входного сигнала.

Состояние а() сохраняется при сохраняющем е() входном сигнале. Сам автомат называется автоматом второго рода.

В многофункциональных автоматах, реализованных на схемах автомат ной памяти и рассматриваемых в автоматном непрерывном времени, выход ной сигнал исследуется как для многофункционального автомата 1-го и 2-го рода с использование входных сигналов х(t) и е(). Автоматы Мараховского являются более общим типом цифровых автоматом, а автоматы Мили и Му ра являются их частным случаем. Кроме этого, в автоматах Мараховского рассматривается и автомат 3-го рода, который дополняет теорию автоматов 1-го и 2-го рода.

Схемы автоматной памяти представляют собою матрицу запоминаемых состояний [64], состоящую из блоков j, представляющих строки матрицы, в которых сохраняются подмножества определенных состояний автоматной схемы памяти под влиянием входного сигнала е(), и блоков µі, представ ляющие столбцы матрицы с определенными подмножествами состояний ав томатной схемы памяти, устанавливаемых входным сигналом х(t).

Обратим внимание, что в триггерах сохраняется одно подмножество со стояний автомата под воздействием только одного сохраняющего входного сигнала е(), которое в работе автоматов Мили и Мура не рассматривается, и, как говорилось ранее, называется пустым словом нулевой длины [25].

В детерминированных автоматах Мараховского дополнительно рас сматривается функция е сохранения состояний а(), которая определяется парой (а(t), е()). Входной сигнал е() сохраняет состояние а(t) автоматов 1 го и 2-го рода после его установки на всем протяжении машинного такта Т в определенном подмножестве j (рис. 1.3). Функции переходов из одного со стояния а(-1) в другое состояние а(t) определяется парой (а(-1), х(t)), а со хранение состояния а() во время промежутка определяется парой (а(t), е()).

В автоматах 3-го рода функция укрупненного перехода из состояния а(t) в состояние а() осуществляется под воздействием входного сигнала е() в определенном подмножестве µi и определяется парою (а(t), е()).

Типы выходных сигналов у определяют род автомата. Выходной сигнал у1 автомата первого рода определяется парой (а(-1), х(t)), выходной сигнал у2 автомата второго рода определяется парой (а(t), а()), а выходной сигнал у3 автомата третьего рода определяется парой (а(t), е()).

Общая теория автоматов при описанных допущениях разбита на абст рактную теорию автоматов и структурную теорию автоматов. В абст рактной теории автоматов отвлекаются от структуры самого автомата и его входных и выходных сигналов. Входные и выходные сигналы рассматрива ются как буквы двух фиксированных алфавитов – входного и выходного.

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

Абстрактная теория автоматов, таким образом, близка к теории алго ритмов, являясь по существу ее дальнейшей детализацией.

Структурная теория автоматов, прежде всего, интересуется структу рой, как самого автомата, так и его входных и выходных сигналов. В струк турной теории рассматриваются, прежде всего, способы построения автома тов из элементарных автоматов, способы кодирования входных и выходных сигналов элементарными сигналами, передаваемыми по реальным входным и выходным каналам и т. п.

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

Частным случаем дискретных автоматов являются автоматы, обладаю щие одним внутренним состоянием, которые называют комбинационными схемами или автоматами без памяти. Работа таких автоматов состоит в том, что они сопоставляют каждому входному сигналу х(t) соответствующий выходной сигнал у(t).

Основная идея методики синтеза автомата состоит в том, чтобы еще на уровне абстрактной теории преодолеть основные затруднения, вызванные наличием памяти, а на уровне структурной теории свести задачу синтеза к задаче синтеза комбинационных схем.

Теория многофункциональных автоматов, кроме детерминированных однозначных и укрупненных переходов, рассматривает еще вероятностные и нечеткие переходы.

Один тип вероятностных переходов определяет переходы из вполне оп ределенного состояния автомата а(-1) подмножества i в состояние а() подмножества k (i k) с определенной вероятностью Р1 под влиянием па ры (хр(t). ek()), в которой входной сигнал хр(t) устанавливает в схеме памяти не запоминаемое состояние ар(t) ни при одном входном сигнале e(). Другой тип вероятностных переходов определяет переходы из вполне определенно го состояния автомата а(-1) подмножества i в состояние а() подмножест ва k (i k) под влиянием пары (х(t). ев()), в которой входной сигнал ев() с определенной вероятностью Р2 определяет подмножество сохраняемых со стояний k. Вероятностный переход второго типа возможен при рассмотре нии трех уровней автоматной схемы памяти в цифровом автомате.

Нечеткие переходы в нечеткие подмножества Qн, состоящие из опреде ленного числа четких подмножеств i, определяют переходы из вполне оп ределенного состояния автомата а(-1) подмножества i в состояние а() подмножества k (i k) с определенной вероятностью Рн под влиянием па ры (хр(t). ев()).

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

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

2. АБСТРАКТНАЯ ТЕОРИЯ АВТОМАТОВ 2.1. Понятие об абстрактном автомате Объектом изучения в абстрактной теории автоматов с точки зрения сис темного подхода вплоть до 90-х годов ХХ столетия являлись абстрактные ав томаты Мили и Мура, функционирующие в дискретном автоматном времени.

В последующие годы, в связи с бурным развитием больших интегральных схем и сверхбольших интегральных схем (СБИС), которые представляют со бою целые функциональные блоки компьютера (процессоры, оперативную память и т. д.), интерес к теории автоматов упал, хотя все они реализуются автоматами Мили и Мура. Даже некоторыми учеными в конце ХХ века вы сказывалась мысль, что теория автоматов себя изжила.

Однако, это совсем не так! Лучшим подтверждением является создание теории многофункциональных автоматов (в том числе и автоматов Марахов ского), которые дали толчок для развития новых направлений в таких облас тях вычислительной техники, как:

1. теории построения схем автоматной памяти, которая в состоянии из менять свои состояния по двум переменным с реконфигурацией струк туры запоминания состояний;

2. теории построения многоуровневых схем памяти, которые в состоя нии обрабатывать одновременно общую информацию (в автомате стра тегии) и частную информацию (в схемах автоматной памяти) без пред варительной обработки;

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

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

Рассмотрим понятия об абстрактных автоматах Мили, Мура и Марахов ского.

2.2. Понятие об абстрактных автоматах Мили и Мура В теории абстрактных автоматов часто отвлекаются от его структуры.

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

С точки зрения последовательных монофункциональных автоматов Ми ли и Мура общая характеристика автомата достаточно полно описана в рабо те [26], в которой комбинационные схемы названы формерами. Известны ка нонические схемы автоматов Мили, Мура или в общем случае С-автомата.

Эти автоматы представляет собой устройства из взаимодействующих регист ра на триггерах и комбинационных схем [26], В частном случае автомат может состоять из одной комбинационной схемы и тогда его рассматривают как автомат с одним состоянием или три виального автомата, либо из одного регистра, запоминающего не менее двух состояний, и тогда его рассматривают как нетривиальный автомат Мура с памятью.

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

А = (Х, Y, ), (2.1) у которого:

Х – конечное множество входных сигналов;

Y – конечное множество выходных сигналов;

: Х Y – функция выходов, реализующая отображение Х на Y.

Комбинационные схемы иногда называют функциональными преобра зователями и изображают следующим образом (рис. 2.1):

Х Y Рис. 2.1. Функциональные преобразователи Определение 2.1. Абстрактный автомат А Мили или Мура задается как совокупность шести объектов:

А = (Х, Y, Q,,, а0), (2.2) где Х – конечное множество входных сигналов, называемых входным алфавитом;

Y – конечное множество выходных сигналов, называемых выходным алфавитом;

Q – произвольное множество, называемое множеством состояний автомата;

а0 – элемент из множества Q, называемым начальным состоянием автомата;

двух функций (а, х) и (а, х), задающих однозначные отображения множества пар (а, х), где а Q и х Х, в множества Q и Х.

Функция (а, х) называется функцией перехода автомата, а функция (а, х) – функцией выходов (для автомата Мили) или сдвинутой (а) функци ей выходов (для автомата Мура). Автомат, заданный функцией выходов, называется автоматом первого рода;

автомат, заданный сдвинутой функ цией выходов, – автоматом второго рода.

Абстрактный автомат Мили или Мура функционирует в дискретном времени, принимая целые неотрицательные значения t = 0, 1, 2, …. В каж дый момент времени t этого времени он находится в определенном состоя нии а(t) из множества Q состояний автомата, причем в начальный момент времени t=0 автомат всегда находится в своем начальном состоянии а0, то есть а(0) = а0. В каждый момент времени t, отличный от начального, автомат способен воспринимать входной сигнал х(t) – произвольную букву входного алфавита Х и выдавать соответствующий выходной сигнал у(t) – некоторую букву выходного алфавита Y.

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

Автомат с начальным состоянием а0 называют инициальным абстракт ным конечным автоматом.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.