Эббинхауз Г.-Д., Якобе К., Ман Ф.-К., Хермес Г. Машины Тьюринга и рекурсивные функции

Перевод с немецкого Э. Г. Белаги. — Москва: Мир, 1972. — 264 с. — (Современная математика).В соответствии с принципом «Selecta Mathematica» в этом томике все существенные результаты сопровождаются полными доказательствами. Тем самым мы надеемся дать читателям основательное представление о мире абстрактных автоматов и побудить их познакомиться и с практическими аспектами теории. Колумбус, январь 1970 г. Конрад Якобе, редактор.От переводчика
Предисловие
Машины Тьюринга и вычислимые функции Уточнение понятия алгоритма.
Нестрогие предварительные соображения
Наглядное описание и определение машины Тьюринга
Машины Тьюриига и вычислимые функции
Примеры машин Тьюринга. Диаграммы Тьюринга
Нормированная вычислимость по Тьюрингу
Простые примеры неразрешимых множеств
Машины Тьюриига и вычислимые функции
Универсальная машина Тьюринга и теорема Клини о перечислимости
Перечислимость. Г. -Д. Эббинхауз
Введение
Простые теоремы о перечислимых множествах
Перечислимость по Тьюрингу
Перечислимость по Шмульяну
Перечислимость по Шмульяну и Тьюрингу
Неперечислимость множества истинных арифметических высказываний и неразрешимость арифметики
Проблема разрешимости и игра "домино"
К проблеме разрешимости логики предикатов. Часть первая
Выражения, префиксы, типы префиксов. Классы выражений, определяемые такими типами
Выполнимость выражений
К проблеме разрешимости логики предикатов. Часть вторая
Проблемы домино
Сопоставление таблице Тьюринга угловой игры «домино»
Лемма. Если М (Т) после применения к пустой ленте не останавливается, то угловая игра «домино» правильная
Лемма. Если угловая игра «домино» правильная, то машина М (Т после применения к пустой лепте никогда не останавливается
Определение выражения а соответствующего угловой игре «домино»
Лемма. Если угловая игра «домино» правильная, то а выполнимо
Лемма. Угловая игра «домино» правильна, если a выполнимо
Переход к узкой логике предикатов
Обзор проблемы разрешимости для класса выражений AVA и диагональной игры «домино»
Машины Тьюринга и случайные 0-1-последовательности.
Сложность конечных 0-1-слов по Колмогорову
Одни неудавшийся подход
Пространство бесконечных 0-1-последовательностей
Случайные бесконечные 0-1-последовательности
Машинно-порожденные 0-1-последовательности
Один алгоритм порождения 0-1-последовательностей 219
Апериодичность
Почти-периодичность
Средние значения
Периодичность
Задачи
Литература
Указатель обозначений
Именной указатель
Предметный указатель