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

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