Оглавление 3
Предисловие 7
Введение. Сигнифика 9
1. Буква 9
2. Алфавит 11
3. Слово 12
4. Конструктивный объект 19
Глава I. Общая теория алгоритмов 23
§ 1. Предписания 24
§ 2. Перечислимые множества 30
1. Перечислимое множество 30
2. Операции над перечислимыми множествами 31
3. Существование не перечислимого множества натуральных чисел 33
4*. Относительная перечислимость 36
§ 3. Алгоритмы 38
1. Алгоритм 38
2. Алгоритмы и перечислимые множества 42
3. Каноническое задание (разложение) программы алгоритма 43
§ 4. Вычислимые функции 46
1. Вычислимая функция 46
2. Существование не вычислимой всюду определенной функции типа N ( N 49
3. Вычислимые функции и алгоритмы 50
4. Вычислимые функции и перечислимые множества 51
§ 5. Разрешимые множества 54
1. Разрешимое множество 54
2. Операции над разрешимыми множествами 56
3. Вычислимые функции и разрешимые множества 58
4. Множество, разрешимое относительно перечислимого надмножества 60
5. Разрешимые и перечислимые множества 61
6*. Разрешимые и относительно перечислимые множества 62
Глава II. Машины Тьюринга 65
§ 1. Тьюринговы алгоритмы 65
1. Тьюрингов алгоритм 65
2. Вычисление «арифметических» функций на машинах Тьюринга 76
3. Принцип тьюрингизации 78
§ 2. Кодирование тьюринговых алгоритмов 81
1. Кодирование тьюринговых алгоритмов 81
2. Пример не перечислимого множества натуральных чисел 83
3. Универсальная машина Тьюринга 84
§ 3. Алгоритмически неразрешимые проблемы 87
1. Алгоритмически неразрешимые проблемы 87
2. Существование перечислимого не разрешимого множества 91
3. Нераспознаваемые свойства 92
ДОПОЛНЕНИЯ 99
Глава III. Нормальные алгорифмы 101
Глава IV. Рекурсивные функции 105
Глава V. Универсальная функция 113
Глава VI. Нумерационная теория алгоритмов 117
§ 1. Основные понятия 117
§ 2. Нумерации класса и наследственные нумерации 122
ПРИЛОЖЕНИЯ 129
1. Две теоремы о натуральных числах 131
2. Три определения 133
3. Программа 135
Примечания 143
Упомянутая литература 145
Указатель терминов 146
Указатель обозначений 150 152