| ПРЕДИСЛОВИЕ | 3 |
| 1. ПОРОЖДЕНИЕ СЛОВ | |
| 1.1. Пороэдение слов в исчислении высказываний | 5 |
| 1.2. Канонические системы Поста | 6 |
| 1.3. Соответствия Поста | 7 |
| | |
| 1.3.1. Проблема соответствий Поста | 8 |
| 1.3.2. Видоизмененная проблема соответствий Поста | 8 |
| 2. ОСНОВНЫЕ АЛГОРИТМЫ | |
| 2.1. Машины Тьюринга | 10 |
| 2.1.1. Определение машины Тьюринга | 10 |
| 2.1.2. Функции, вычислимые по Тьюрингу. Тезис Тьюринга | 13 |
| 2.2. Вычислимые арифметические функции | 16 |
| 2.2.1. Определение класса Ч | 16 |
| 2.2.2. Одна просто определяемая невычислимая функция | 21 |
| 2.3. Универсальные машины Тьюринга | 23 |
| 2.3.1. Коды машин Тьюринга | 23 |
| 2.3.2. Универсальные машины и функции | 24 |
| 2.4. ft- Ленточные машины Тьюринга (детерминированные и недетерминированные) | 26 |
| 2.5. Нормальные алгоритмы Маркова | 31 |
| 3. ДРУГИЕ АЛГОРИТМЫ | |
| 3.1. Варианты машин Тьюринга | 36 |
| 3.1.1. Машины Тьюринга с ^-этажной лентой (к>1) | 36 |
| 3.1.2. Машины Тьюринга с односторонней лентой | 37 |
| 3.1.3. Машины Тьюринга со входом | 38 |
| 3.1.4. Оракульные машины Тьюринга | 38 |
| 3.1.5. Машины Тьюринга с двумя символами на ленте | 40 |
| | |
| 3.2. Вероятностные машины | 42 |
| 3.3. Альтернирующие машины | 43 |
| 3.4. Равнодоступные адресные машины | 44 |
| 3.5. Модели параллельных вычислений | 47 |
| 3.6. Семейства схем | 49 |
| 3.7. Конечные автоматы | 53 |
| 3.7.1. Автоматы Мура и Мили | 53 |
| 3.7.2. Эквивалентность автоматов Мура и Мили | 54 |
| 3.7.3. Множества слов, вычислимые в реальное время | 56 |
| 3.8. Приближенные (эвристические) алгоритмы | 58 |
| 3.8.1. Оценки качества приближенных алгоритмов | 59 |
| 3.8.2. Примеры приближенных алгоритмов | 60 |
| 3.8.3. Задача fc -разбиения | 62 |
| 4. ОСНОВНЫЕ КЛАССЫ СЛОЖНОСТЕЙ ВЫЧИСЛЕНИЙ | |
| 4.1. Временная и емкостная сложности вычислений | 66 |
| 4.1.1. Соотношение между временной и емкостной сложностями вычислений | 66 |
| 4.1.2. Одно свойство емкостной сложности вычислений | 67 |
| 4.2. Некоторые классы сложностей вычислений | 73 |
| 4.3. Классы Р и NP . Проблема P =? NP -полные и NP -трудные проблемы | 75 |
| 4.3.1. Классы Р и NP . Проблема P =? NP | 76 |
| 4.3.2. Некоторые NP -полные и NP -трудные проблемы | 77 |
| 4.4. Р-полные проблемы | 83 |
| 4.5. Вероятностные классы сложности вычислений | 87 |
| 4.5.1. Два вероятностных класса | 88 |
| 4.6. О машинно-независимой теории сложности вычислений | 88 |
| 5. АНОМАЛИИ В ТЕОРИИ ВЫЧИСЛЕНИЙ | |
| 5.1. Теорема о пробелах | 93 |
| 5.2. Одноместные предикаты и бесконечные последовательности булевых функций | 95 |
| 5.3. Задача о камнях при различных способах задания их весов | 98 |
| 5.4. Перечисление рекурсивно-перечислимых множеств | 99 |
| 6. АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ | |
| 6.1. Проблемы самоприменимости, применимости и переводимости | 101 |
| 6.2. Эквивалентность слов в ассоциативных исчислениях | 103 |
| 6.3. Проблема соответствий Поста | 106 |
| 6.4. Теорема Раиса | 109 |
| ЛИТЕРАТУРА | 112 |