|
ОГЛАВЛЕНИЕ
От переводчика...................... 5 Предисловие........................ 7 Машины Тьюринга и вычислимые функции I. Уточнение понятия алгоритма. Г.-Д. Эббинхауз............ 9 § 1. Нестрогие предварительные соображения...... 9 § 2. Наглядное описание и определение машины Тьюринга 20 Машины Тьюринга и вычислимые функции П. Ф.-К. Ман 34 § 3. Примеры машин Тьюринга. Диаграммы Тьюринга.. 34 § 4. Нормированная вычислимость по Тьюрингу.... 55 § 5. Простые примеры неразрешимых множеств..... 68 Машины Тьюринга и вычислимые функции III. Г.-Д. Эббинхауз.......................... 74 § 6. Универсальная машина Тьюринга и теорема Клини о перечислимости................. 74 Литература.................... 84 Перечислимость. Г.-Д. Эббинхауз.............. 86 § 1. Введение..................... 86 § 2. Простые теоремы о перечислимых множествах... 91 § 3. Перечислимость по Тьюрингу........... 95 § 4. Перечислимость по Шмульяну.......... 107 § 5. Перечислимость по Шмульяну и Тьюрингу..... 118 § 6. Неперечислимость множества истинных арифметических высказываний и неразрешимость арифметики.. 126 Литература.................... 149 Проблема разрешимости и игра «домино». Г. Хермес..... 150 § 1. К проблеме разрешимости логики предикатов. Часть 1 150 § 2. Выражения, префиксы, типы префиксов. Классы выражений, определяемые такими типами...... 153 § 3. Выполнимость выражений............. 155 § 4. К проблеме разрешимости логики предикатов. Часть 2..................... 158 § 5. Проблемы домино................. 160
§ 6. Сопоставление таблице Тьюринга угловой игры
«домино», Х?................ 163
§ 7. Лемма. Если м (т) после применения к пустой ленте не останавливается, то угловая игра «домино» ?т,
Xj- правильная.................. 165
§ 8. Лемма. Если угловая игра «домино» х т, правильная, то машина м (т) после применения к пустой ленте никогда не останавливается....... 167
§ 9. Определение выражения а-, (-.<,, соответствующего
угловой игре «домино» 2), Х°............ 171
§ 10. Лемма. Если угловая игра «домино» ЛГ, ?° правильная, то СС , ?0 выполнимо............. 173
§11. Лемма. Угловая игра «домино» D° правильна, если
ео выполнимо................. 175
§ 12. Переход к узкой логике предикатов........ 176
§ 13. Обзор проблемы разрешимости для класса выраже-
жений л V Л и диагональной игры «домино».... 179
Литература.................... 182
Машины Тьюринга и случайные 0-1-последовательности.
К- Якобе....................... 183
§ 1. Сложность конечных 0-1-слов по Колмогорову... 190
§ 2. Один неудавшийся подход............ 196
§ 3. Пространство бесконечных 0-1-последовательностей 201
§ 4. Случайные бесконечные 0-1-последовательности... 207
Литература......,............ 214
Машинно-порожденные 0-1-последовательности. К- Якобе.. 216
§ 1. Один алгоритм порождения 0-1-последовательностей 219
§ 2. Апериодичность................. 226
§ 3. Почти-периодичность............... 232
§ 4. Средние значения................ 234
§ 5. Периодичность.................. 242
§ 6. Задачи...................... 245
Литература................... 247
Указатель обозначений................... 248
Именной указатель.................... 249
Предметный указатель................... 251
|