ОГЛАВЛЕНИЕ
Предисловие ......................... 7
Введение ........................... 9
Глава I. Элементы математической логики..........И
§ 1.1. Вводные замечания................... Ч
§ 1.2. Основные понятия................... '-
§ 1.3. Исчисление высказываний................ 20
§ 1.4. Об исчислении предикатов (двузначных)......... 41
Глава II. Технические приложения исчисления высказываний 46
§ 2.1. Однотактные релейно-контактные схемы......... 46
§ 2.2. Анализ однотактных релейно-конт;нктных схем...... 53
§ 2.3. Синтез однотактных релейно-контэктнык схем...... 59
§ 2.4. Иные методы технической реализации логических функций 63 § 2.5. Проблема минимизации устройств, реализующих логические функции...................... 77
Глава III. Общие понятия о конечных автоматах и последова-
тельностных машинах.................86
§ 3.1. Дискретное время и такты................86
§ 3,2. О динамических системах ...............89
§ 3.3. Конечные автоматы...................91
§ 3.4. Последовательностные машины.............97
§ 3.5. Методы задания конечного автомата и последовательност-
ной машины......................100
§ 3.6. Методы записи работы автомата.............НО
• §3.7. Замечание об ограничении входных последовательностей 119
Глава IV. Абстрактная структура и сеть..........122
§ 4.1. Общие понятия о замещении последовательнбстных машин 122
§ 4.2. Абстрактная структура автомата.............130
§ 4.3. Сеть..........................137
§ 4.4. Абстрактная агрегатизация автоматов и последователь-костных машин ....................149
§ 4.5. Абстрактный нейрон и абстрактные модели нейронных
сетей .........................151
4 ОГЛАВЛЕНИЕ
Глава V. Техническая реализация конечных автоматов и по-
следовательностных машин...............160
§ 5.1. Два метода технической реализации конечных автоматов
и последовательностных машин ............160
§ 5.2. Агрегатное построение конечных автоматов и последовательностных машин ..................161
§ 5.3. Построение конечных автоматов и последовательностных машин с использованием естественных задержек и обратных связей ......................172
§ 5.4. Метод и реализация Хафмана.............180
Глава VI. Автономный конечный автомат и автономная по-
следовательностная машина ..............197
§ 6.1. Что «могут делать» автономный конечный автомат и
автономная последовательностная машина.......197
§ 6.2. Синтез двоичной структуры автономной последователь-
ностной машины ...................205
Глава VII. Представление событий в конечном автомате
и последовательностной машине ............?17
§ 7.1. Постановка задачи ..................217
§ 7.2. Событие. Представление событий.......... . . 219
§ 7.3. Действия над множествами входных последовательностей. Регулярные события...............224
§ 7.4. Представимость регулярных событий .........234
§ 7.5 Регулярность представимых событий ..........241
§ 7.6. Существуют ли нерегулярные (непредставимые) события? 247
§ 7.7. Что «может делать» конечный автомат.........253
Глава VIII. Распознавание реализуемости задания и абстрактный синтез конечных автоматов и последовательностных машин.................... 255
§ 8.1. Постановка задачи ..................255
§ 8.2. Случай, когда задание перечисляет требуемые соответствия между входными и выходными последовательностями .........................258
§ 8.3. Алгоритмическая неразрешимость проблемы распознавания представимости рекурсивных событий ....... 279
§ 8.4. Синтез конечных автоматов и последовательностных машин при задании, сформулированном на языке регулярных выражений ....................285
Глава IX. Эквивалентность и минимизация последователь-
ностных машин ...................301
§ 9.1. Постановка задачи о распознавании эквивалентных состояний ........................301
§ 9.2. Алгоритмическая неразрешимость проблемы распознавания эквивалентных состояний в общем случае.....305
ОГЛАВЛЕНИЕ 5
S 9.3. Распознавание эквивалентности состояний в случае, когда
множество входных последовательностей не ограничено . 308
§ 9.4. Распознавание эквивалентности состояний в случае, когда ограничения наложены на длину входных последовательностей .........................319
§ 9.5. Понятия об эквивалентности, отображении и минимизации последовательностных машин............326
§ 9.6. Минимизация последовательностной машины в случае, когда множество входных последовательностей не ограничено ........................329
§ 9.7. Минимизация последовательностной машины в случае,
когда она работает как конечный автомат.......333
§ 9.8. Минимизация последовательностных машин в случае
ограничений типа Ауфенкампа.............340
§ 9.9. Об ином определении эквивалентности последовательностных машин.....................353
Глава X. Преобразование тактности последовательностных
машин ........................361
§ 10.1. Общие соображения о преобразовании тактности. Определение понятий изображения и воспроизведения . . . 361
§ 10.2. Примеры изображения и воспроизведения ......370
§ 10.3. Воспроизведение медленной последовательностной машины быстрой машиной в случае, когда тактность медленной машины определяется сменой состояний на входе........................376
§ 10.4. Минимизация воспроизводящей последовательностной
машины, построенной в предыдущем параграфе .... 383
Глава XI. Определение свойств последовательностных машин по их реакции на входные последовательности конечной - длины ....................... 397
§ 11.1. Основные определения и постановка задачи ..... .397
§ 11.2. Определение эквивалентности состояний последовательностных машин по реакции машины на входные последовательности конечной длины.............400
§ 12.3. Изучение последовательностных машин с помощью кратных экспериментов .................. 407
§ 11.4. Изучение последовательностных машин с помощью
простых экспериментов ................ 411
Глава XII. Алгоритмы ...................425
§ 12.1. Примеры алгоритмов.................425
§ 12.2. Общие свойства алгоритмов..............432
§ 12.3. Проблема слов в ассоциативном исчислении......435
§ 12.4. Алгоритм в некотором алфавите А. Нормальный алгоритм Маркова ....................441
S 12.5. Сведение любого алгоритма к численному алгоритму.
Гёделизация .............•.......451
6 ОГЛАВЛЕНИЕ
§ 12.6. Элементарные и примитивно-рекурсивные функции . . 455 § 12.7. Предикаты. Ограниченный оператор наименьшего числа 466 § 12.8. Пример построения вычислимой, но не примитивно-рекурсивной функции .................. 473
§ 12.9. Общерекурсивные функции. Определение Эрбрана — Гё-
деля .........................475
§ 12.10. Явная форма общерекурсивных функций.......481
§ 12.11. Тезис Чёрча.....................487
§ 12.12. Рекурсивные действительные числа..........490
§ 12.13. Рекурсивно-перечислимые и рекурсивные множества . 492
Глава XIII. Машины Тьюринга ..............496
§ 13.1. Описание и примеры машин Тьюринга........496
§ 13.2. Композиция машин Тьюринга.............506
§ 13.3. Вычисления на машинах Тьюринга..........512
Заключение .........................524
§ 1. Что может «делать» конечный автомат и последователь-костная машина.....................524
§ 2. Последовательность синтеза технического устройства, реализующего конечный автомат или последовательностную
машину .........................527
Библиография ........................536
Именной указатель......................550
Предметный указатель........
. 551
ПРЕДИСЛОВИЕ
Для инженеров, работающих в области релейно-кон-тактной техники или техники цифровых машин, изучение общей теории конечных автоматов и последователь-ностных машин не связано с большими трудностями, так как им злаком уже необходимый математический аппарат: исчисление высказываний, общие понятия об исчислении предикатов, основы теории алгоритмов (теории рекурсивных функций).
В значительно худшем положении оказываются инженеры других специальностей, в том числе и инженеры, знакомые с теорией автоматического управления. Основой их математического образования является обычно анализ, математическая физика, дифференциальные уравнения. Как показал опыт, изучение проблем, в основе которых лежит математическая логика и теория алгоритмов, представляет для них известные трудности.
Настоящая книга рассчитана «а широкий круг читателей, работающих в области автоматики, телемеханики и вычислительной техники и впервые знакомящихся с теорией конечных автоматов и последователь-ностных машин. Авторы имели в виду также, что книга должна быть полезна для математика (не логика), стремящегося познакомиться с этими проблемами, а также для физиолога и биолога, интересующихся теорией конечных автоматов и последовательностных машин применительно к созданию идеализированных моделей нервных тканей. Цель книги — ввести указанный круг читателей в эту новую область, познакомить с основными понятиями, с постановкой некоторых задач и результатами их решения. При этом результаты, полученные авторами, тесно переплетаются с результатами,
8 ПРЕДИСЛОВИЕ
заимствованными из литературы. Все же в основном книга рассчитана на инженеров. Поэтому авторы при рассмотрении некоторых вопросов логики и теории алгоритмов вынуждены были пренебрегать строгостью изложения.
Для каждого из упомянутых читателей была бы удобнее своя архитектура книги, свой порядок размещения материалов. Вынужденные рассчитывать на разных читателей, авторы старались разместить материал так, чтобы встречающиеся трудности последовательно нарастали. Естественно поэтому, что каждый читатель может избрать свой порядок чтения глав, руководствуясь следующими общими советами:
1. Для инженера, не знакомого с предметом, но стремящегося детально изучить его, рекомендуется изучение материала в той последовательности, в какой он приведен в книге.
2. Для инженера, интересующегося предметом лишь в общих чертах, рекомендуется прочесть последовательно первые семь глав, а затем главу XII. После этого можно бегло просмотреть главу XIII и, наконец, прочесть главы VIII, IX, X и XI.
3. Для инженера, знакомого с основами математической логики и ее техническими приложениями (например, для специалиста по релейно-контактной технике или вычислительным машинам), рекомендуется начать чтение книги с главы III.
4. Наконец, математику, интересующемуся техническими приложениями, можно смело опустить при чтении книги, главы I, XII и XIII.
Параграфы 2.5 и 8.4, в которых затрагиваются специальные вопросы минимизации булевых функций и реализации конечных автоматов, заданных на языке регулярных выражений (выходящие за рамки основ общей теории конечных автоматов и последовательност-ных машин), были по просьбе авторов написаны соответственно В. Д. Казаковым и О. П. Кузнецовым.
Авторы с благодарностью ждут замечаний и предложений от читателей.
Авторы
ВВЕДЕНИЕ
«Конечный автомат» и «последовательностная машина» — исторически сложившиеся и широко применяемые, хотя и очень неудачные наименования некоторого, в известном смысле простейшего класса динамических систем. Выделение этого класса и построение его теории связано со следующими двумя обстоятельствами:
1. Динамические системы этого класса часто используются в технике, в особенности в автоматике, телемеханике, вычислительной технике. Электронные цифровые вычислительные машины и многотактные релейно-контактные схемы являются примерами динамических систем этого класса. Рассмотрение всего этого класса динамических систем позволяет поэтому изучать их общие закономерности и разрабатывать методы их анализа и оптимального синтеза.
2. С развитием техники, в особенности в связи с созданием быстродействующих универсальных вычислительных машин, все чаще ставятся вопросы такого рода: Что может и что не может «делать» машина? Может ли машина выполнять любой алгоритм? Может ли машина принципиально делать что-либо большее, чем выполнять алгоритм? В какой мере машина может и в какой не может выполнять функции, свойственные живому мозгу? Попытки в точных терминах сформулировать подобные вопросы и тем более изыскать ответы на них до сих пор оставались безрезультатными, если термином «машина» обозначается очень широкий класс динамических систем. Между тем для более узкого класса динамических систем, называемых «конечными автоматами» и «последовательностными машинами», постановка вопросов такого рода имеет смысл. Они
Цена: 300руб.
