Айзерман М.А., Гусев Л.А., Розоноэр Л.И., Смирнова И.М., Таль А.А. Логика, автоматы, алгоритмы

М.: Наука, 1963. — 556 с.Настоящая книга рассчитана на широкий круг читателей, работающих в области автоматики, телемеханики и вычислительной техники и впервые знакомящихся с теорией конечных автоматов и последовательностных машин. Авторы имели в виду также, что книга должна быть полезна для математика (не логика), стремящегося познакомиться с этими проблемами, а также для физиолога и биолога, интересующихся теорией конечных автоматов и последовательностных машин применительно к созданию идеализированных моделей нервных тканей. Цель книги - ввести указанный круг читателей в эту новую область, познакомить с основными понятиями, с постановкой некоторых задач и результатами их решения. Все же, в основном, книга рассчитана на инженеров. Поэтому авторы при рассмотрении некоторых вопросов логики и теории алгоритмов вынуждены были пренебрегать строгостью изложения.Элементы математической логики.
Вводные замечания.
Основные понятия.
Исчисление высказываний.
Об исчислении предикатов (двузначных).
Технические приложения исчисления высказываний.
Однотактные релейно-контактные схемы.
Анализ однотактных релейно-контактных схем.
Синтез однотактных релейно-контактных схем.
Иные методы технической реализации логических функций.
Проблема минимизации устройств, реализующих логические функции.
Общие понятия о конечных автоматах и последовательностных машинах.
Дискретное время и такты.
О динамических системах.
Конечные автоматы.
Последовательностные машины.
Методы задания конечного автомата и последовательностной машины.
Методы записи работы автомата.
Замечание об ограничении входных последовательностей.
Абстрактная структура и сеть.
Общие понятия о замещении последовательностных машин.
Абстрактная структура автомата.
Сеть.
Абстрактная агрегатизация автоматов и последовательностных машин.
Абстрактный нейрон и абстрактные модели нейронных сетей.
Техническая реализация конечных автоматов и последовательностных машин.
Два метода технической реализации конечных автоматов. и последовательностных машин. Агрегатное построение конечных автоматов и последовательностных машин.
Построение конечных автоматов и последовательностных машин с использованием естественных задержек и обратных связей.
Метод и реализация Хафмана.
Автономный конечный автомат и автономная последовательностная машина.
Что «могут делать» автономный конечный автомат и автономная последовательностная машина. Синтез двоичной структуры автономной последовательностной машины.
Представление событий в конечном автомате и последовательностной машине?
Постановка задачи.
Событие. Представление событий.
Действия над множествами входных последовательностей. Регулярные события.
Представимость регулярных событий.
Регулярность представимых событий.
Существуют ли нерегулярные (непредставимые) события?
Что «может делать» конечный автомат.
Распознавание реализуемости задания и абстрактный синтез конечных автоматов и последовательностных машин.
Постановка задачи. Случай, когда задание перечисляет требуемые соответствия между входными и выходными последовательно. последовательностями.
Алгоритмическая неразрешимость проблемы распознавания представимости рекурсивных событий.
Синтез конечных автоматов и последовательностных машин при задании, сформулированном на языке регулярных выражений.
Эквивалентность и минимизация последовательностных машин.
Постановка задачи о распознавании эквивалентных состояний.
Алгоритмическая неразрешимость проблемы распознавания эквивалентных состояний в общем случае.
Распознавание эквивалентности состояний в случае, когда множество входных последовательностей не ограничено.
Распознавание эквивалентности состояний в случае, когда ограничения наложены на длину входных последовательностей.
Понятия об эквивалентности, отображении и. минимизации последовательностных машин. Минимизация последовательностной машины в случае, когда множество входных последовательностей не ограничено.
Минимизация последовательностной машины в случае, когда она работает как конечный автомат.
Минимизация последовательностных машин в случае ограничений типа Ауфенкампа.
Об ином определении эквивалентности последовательностных машин.
Преобразование тактности последовательностных машин.
Общие соображения о преобразовании тактности.
Определение понятий изображения и воспроизведения.
Примеры изображения и воспроизведения.
Воспроизведение медленной последовательностной машины быстрой машиной в случае, когда тактность медленной машины определяется сменой состояний на входе.
Минимизация воспроизводящей последовательностной машины, построенной в предыдущем параграфе.
Определение свойств последовательностных машин по их реакции на входные последовательности конечной длины.
Основные определения и постановка задачи.
Определение эквивалентности состояний последовательностных машин по реакции машины на входные последовательности конечной длины.
Изучение последовательностных машин с помощью кратных экспериментов.
Изучение последовательностных машин с помощью простых экспериментов.
Алгоритмы.
Примеры алгоритмов.
Общие свойства алгоритмов.
Проблема слов в ассоциативном исчислении.
Алгоритм в некотором алфавите А. Нормальный алгоритм Маркова.
Сведение любого алгоритма к численному алгоритму. Гёделизация.
Элементарные и примитивно-рекурсивные функции.
Предикаты. Ограниченный оператор наименьшего числа.
Пример построения вычислимой, но не примитивно-рекурсивной функции.
Общерекурсивные функции. Определение Эрбрана — Гёделя.
Явная форма общерекурсивных функций.
Тезис Чёрча.
Рекурсивные действительные числа.
Рекурсивно-перечислимые и рекурсивные множества.
Машины Тьюринга.
Описание и примеры машин Тьюринга.
Композиция машин Тьюринга.
Вычисления на машинах Тьюринга.
Заключение.
Что может «делать» конечный автомат и последовательностная машина.
Последовательность синтеза технического устройства, реализующего конечный автомат или последовательностную машину.