Теория вычислений для программистов

Предисловие
Для кого предназначена эта книга
Графические выделения
О примерах кода
Как с нами связаться
Благодарности
Глава 1. Все, что нужно знать о Ruby
Интерактивная оболочка Ruby
Значения
Простые данные
Структуры данных
Процедуры
Поток управления
Объекты и методы
Классы и модули
Прочее
Локальные переменные и присваивание
Строковая интерполяция
Инспектирование объектов
Печать строк
Методы с переменным числом аргументов
Блоки
Модуль Enumerable
Класс Struct
Партизанское латание
Определение констант
Удаление констант
Часть I. ПРОГРАММЫ И МАШИНЫ
Глава 2. Семантика программ
В чем смысл слова "смысл"?
Синтаксис
Операционная семантика
Семантика мелких шагов
Выражения
Предложения
Корректность
Приложения
Семантика крупных шагов
Выражения
Предложения
Приложения
Денотационная семантика
Выражения
Предложения
Сравнение способов определения семантики
Приложения
Формальная семантика на практике
Формализм
Поиск смысла
Альтернативы
Реализация синтаксических анализаторов
Глава 3. Простейшие компьютеры
Детерминированные конечные автоматы
Состояния, правила и входной поток
Вывод
Детерминированность
Моделирование
Недетерминированные конечные автоматы
Недетерминированность
Свободные переходы
Регулярные выражения
Синтаксис
Семантика
Синтаксический анализ
Эквивалентность
Минимизация ДКА
Глава 4. Кое-что помощнее
Детерминированные автоматы с магазинной
памятью
Память
Правила
Детерминированность
Моделирование
Недетерминированные автоматы с магазинной
памятью
Моделирование
Неэквивалентность
Разбор с помощью автоматов с магазинной
памятью
Лексический анализ
Синтаксический анализ
Применение на практике
Насколько мощнее?
Глава 5. Окончательная машина
Детерминированные машины Тьюринга
Память
Правила
Детерминированность
Моделирование
Недетерминированные машины Тьюринга
Максимальная мощность
Внутренняя память
Подпрограммы
Несколько лент
Многомерная лента
Машины общего назначения
Кодирование
Моделирование
Часть II. ВЫЧИСЛЕНИЯ И ВЫЧИСЛИМОСТЬ
Глава 6. Программирование на пустом месте
Имитация лямбда-исчисления
Работа с процедурами
Задача
Числа
Булевы значения
Предикаты
Пары
Операции над числами
Списки
Строки
Решение
Более сложные приемы программирования
Реализация лямбда-исчисления
Синтаксис
Семантика
Синтаксический разбор
Глава 7. Универсальность повсюду
Лямбда-исчисление
Частично рекурсивные функции
SKI-исчисление
Iota
Таг-системы
Циклические таг-системы
Игра "Жизнь" Конвея
Правило 110
Вольфрамова 2,3 машина Тьюринга
Глава 8. Невозможные программы
Факты как они есть
Универсальные системы могут выполнять
алгоритмы
Программы могут замещать машины Тьюринга
Код - это данные
Универсальные системы могут зацикливаться
Программы могут ссылаться сами на себя
Разрешимость
Проблема остановки
Построение анализатора остановки
Это никогда работать не будет
Другие неразрешимые проблемы
Печальные следствия
Почему так происходит?
Жизнь в условиях невычислимости
Глава 9. Программирование в игрушечной
стране
Абстрактная интерпретация
Планирование маршрута
Абстракция: умножение знаков
Аппроксимация и безопасность: сложение знаков
Статическая семантика
Реализация
Достоинства и ограничения
Приложения
Послесловие
Предметный указатель