Предметный указатель

а-вычислимая функция 81, 159

а-перечислимое

множество 82 /3-функция Гёделя 136, 144 О'-вычислимая функция 85 О, О', ..., 0(п> 104 Т[а] 159 Disjoint (Л) 106 Зх, Ух 98 Г(Г) 42 T(t) 41 Л, V, -1 98

59

77

ju-оператор 155 Subset (А) 105 тг 10 П2 109

П„ 98-100, 138, 143

Proof (х, у) 142

£„ 98-100, 104, 138, 143

Л-вычислимая функция 103

Л-перечислимое

множество 103 Л-разрешимое

множество 103 Dx 105 е 10

то-полное множество 61, 65,

66, 74, 75, 103 то-сводимость 59, 74, 100, 139 пар 73 то-сводящая функция 59 то-степень 103 т-эквивалентные

множества 103 Г-сводимость 77 Г-степень 103 Г- эквивалентные

множества 103

Ехес^еРго§гат, процедура 51

GetPгogгamText, процедура 51

Адекватность 140 Аккермана функция 163 Алгоритм (алгорифм)

Маркова 158 Алфавит 113, 118, 126

сокращение 116 Арифме тиче екая

иерархия 98, 138, 142,

143

Арифме тиче екая

формула 134 Арифме тиче екая

функция 134 Арифметическое

множество 129, 134,

135, 138, 139, 143 Ассоциативное

исчисление 118 двустороннее 124, 127 неразрешимое 119, 123,

158

Базисная функция 146 Бейсик 50 Буква 118

Взаимно простые числа 136

Возвратная рекурсия 151 Время вычисления 153 Вход машины Тьюринга 114 Выигрышное условие 94 Вычислимая нумерация 24, 30

Вычислимая

перестановка 66 Вычислимая функция 8, 11,

129, 157 Вычислимо изоморфные

множества 56 Вычислимое действительное

число 16, 21 Вычислимость

на машине с конечным

числом регистров 131 на машине Тьюринга 115,

132

относительно а 81 с оракулом 76, 159 Вычитание усечённое,

рекурсивное

определение 147

Гёделя теорема 140, 141 Главная (гёделева)

нумерация 24, 26, 32 Главная универсальная

функция 25, 28 относительно а 84 Главное универсальное

множество 29, 30, 61 Головка 113 Гомоморфизм 126 График функции 14

Двустороннее ассоциативное исчисление 124, 127

Декартово произведение множеств 13

Десятая проблема Гильберта 143 Диагональная функция 47 Диагональное сечение 21,

61, 73 Дизъюнкция 98, 100 Диофантово уравнение 15 Доказательство 141 Дополнение 12, 99

Заключительное состояние 114

Изоморфизм

га-полных множеств 66

то-полных пар 75

главных нумераций 39

универсальных множеств 56 Иммунное множество 22, 23,

62, 65 Исчисление 140

ассоциативное 118 неразрешимое 119, 123, 158

Кванторы 98, 142

ограниченные 148 Китайская теорема об

остатках 137 Композиция функций 24, 27 Конечно порождённая

полугруппа 126 Конечное множество

номер 105 Конкатенация 126 Конструктивный объект 8 Конфигурация машины

Тьюринга 114, 120, 132 Конъюнкция 98, 100 Коперечислимость 99

Корректное множество 79, 160

Креативное множество 71 Лента 113

Массивы, моделирование 131 Машина Поста 157 с конечным числом

регистров 129 с оракулом 76 Тьюринга 6, 112, 113, 115, 117, 125, 132, 153, 156, 157

Минимизации оператор 149,

155 Множества

га-эквивалентные 103 Т- эквивалентные 103 неотделимость 21, 72 эффективная

неотделимость 73, 74 Множество

Л-перечислимое 103 Л-разрешимое 103 то-полное 61, 65, 103 арифметическое 129, 134,

135, 138, 139, 143 иммунное 22, 23, 62, 65 креативное 71 неразрешимое 10 перечислимое 10, 12, 13,

15, 98, 138, 143 перечислимое

неразрешимое 20, 104,

123 примитивно

рекурсивное 147 продуктивное 69

простое 22, 66 разрешимое 9, 13, 15, 98, 138

универсальное 18 универсальное в

2„/П„ 101 эффективно

неперечислимое 63 Множество номеров 36, 109 нигде не определённой функции 32 Моделирование 120

Натуральная нумерация 24 Начальное состояние 113 Недетерминированный

алгоритм 13 Неотделимые множества 22,

72

Неподвижная точка 45, 142 Неразрешимое

ассоциативное исчисление 119, 123, 158 Неразрешимое множество 10 Несравнимые по Тьюрингу

множества 89 Нигде не определённая

функция 109 Нижняя точка 21 Номер 24 пары 26 функции 109 Нормализации принцип 158 Нормальный алгорифм 158 Нумерация 24

вычислимая 24, 30 главная (гёделева) 24, 26, 32

конечных множеств 105конечных последователь­ностей 152 натуральная 24 однозначная 35

Область значений 11 Область определения 11 Образ множества 15 Образец 41, 79, 107, 160 Образующие

полугруппы 125, 127 Общерекурсивная

функция 156, 157 Объединение множеств 12 Ограниченный квантор 148 Ограниченный оператор

минимизации 149 Однозначная нумерация 35 Оператор минимизации 149,

155

Операция скачка 102, 103 Оракул 76

Отделяющее множество 22 Относительная

вычислимость 77, 159 Отрицание 98, 99

Пар нумерация 26 Парадокс лжеца 142 Паскаль 40, 112, 117 Пересечение множеств 12 Пересечение перечислимых

множеств 31 Перечислимое множество 10,

12, 13, 15, 98, 138, 143 универсальное 101 Перечислимое неразрешимое

множество 20, 104, 123 Перечислимое снизу/сверху

число 16, 21

Перечислимость 14 Перечислимость

относительно а 82 Перечислимые неотделимые

множества 21, 37 Перечислимые свойства

функций 41 Подслово 119 Подстановка 145 Полнота 140 Полугруппа 125, 127 Полухарактеристическая

функция 11, 59 Поста машина 157 Поста проблема 91 Поста тезис 157 Поста теорема 108 Правило 118

Представление множества

формулой 135 Преобразование слов 119 Примитивно рекурсивная

функция 145, 146, 153,

157

Примитивно рекурсивное

множество 147 Принцип нормализации 158 Пробела символ 113 Проблема

остановки 112

Поста 91

равенства слов 112 самоприменимости 20 Программа с конечным

числом переменных 132 Программа, печатающая

свой текст 47 Продолжение образца 41 Продуктивное множество 69 Проекция 14, 99

Прообраз 15, 60

Простое множество 22, 66

Простое число 131, 149, 150

Противоречивые тройки 79

Псевдообратная функция 16

Пустое слово 126

Пустой символ 113

Разрешимое множество 9,

13, 15, 98, 138 Разрешимость 14 Результат работы 114 Рекурсивная функция 145 Рекурсия 145, 150

возвратная 151

примитивная 145

совместная 150 Релятивизация 81 Роджерса теорема 39, 58

Сведение 32

Свободная полугруппа 126 Сводимость нумераций 32 Сводимость по

Тьюрингу 77, 88 Сечение

диагональное 21

множества 18

функции 17 Си 40

Сильно главная

нумерация 84 Символ 113, 118 Скачок 103 Слово 118, 126 Сложение, рекурсивное

определение 146 Совместная рекурсия 150 Совместные образцы 79 Соотношения в

полугруппе 125-127

Состояние 113, 118 заключительное 114 начальное 113

Стек 132

Степень

неразрешимости 103

Счётчик команд 135

Таблица переходов 113, 114, 121

Тарского теорема 139, 140 Тезис Тьюринга 117 Теорема

Гёделя о неполноте 140, 141

Клини о неподвижной

точке (о рекурсии) 45 Клини о нормальной

форме 158 Мучника - Фридберга 92 о неподвижной точке для

множеств 55 о неподвижной точке с

параметром 54 об униформизации 15 Поста 13, 33, 108 Роджерса 39, 58 Тарского 139, 140 Успенского-Райса 33, 109 Транслятор 40 Тьюринга машина 6, 112, 113, 115, 117, 125, 132, 138, 153, 156, 157 Тьюринга тезис 117, 138, 157 Тьюрингова степень 103

Удвоение слова 115 Указание в методе

приоритета 92 Умножение, рекурсивное

определение 146

Универсальная вычислимая

функция 17, 19 Универсальная функция 17,

158, 162 неглавная 35 Универсальная функция

трёх аргументов 25 Универсальное в 2П/ПП

множество 101 Универсальное множество 18 Универсальное

перечислимое

множество 18, 101 Успенского - Раиса

теорема 33, 109

Формула

арифметики 129, 134 представляющая множество 135 Фрагмент 89 Функция

а-вычислимая 81 О'-вычислимая 85 Л-вычислимая 103 то-сводящая 59 Аккермана 150, 163 арифметическая 134 вычислимая 8, 11, 129, 157 вычислимая на машине

Тьюринга 115, 156 диагональная 47 нигде не определённая 109 общерекурсивная 156, 157 полухарактеристиче­ская 11, 59

примитивно

рекурсивная 145, 146, 153, 157

рекурсивная 145 универсальная 17, 158, 162 универсальная

вычислимая 17, 19 характеристическая 9, 59 частично

рекурсивная 155, 156

Характеристическая функция 9, 59

Частично рекурсивная функция 155, 156 Чёрча тезис 157 Число

вычислимое 16, 21 перечислимое

снизу/сверху 16, 21

Эквивалентность по

Тьюрингу 103 Элемент 92

Эффективно неотделимые множества 73, 74

Эффективно

неперечислимое множество 63

Язык программирования 25

Указатель имён

Аккерман В. (W. Ackermaim) 150, 163 Гёдель К. (K.Godel, 1906-1978) 136, 144, 157 Гильберт Д. (D. Hilbert, 1862-1943) 143 Евклид (III век до Р.Х.) 150 Клини С. К. (S. С. Kleene) 157, 158 Марков А. А. (младший, 1903-1979) 128 Матиясевич Ю.В. 15, 143 Мучнйк Альберт А. 91 Новиков П. С. (1901-1975) 128

Пост Э. (Emil L. Post, 1897-1954) 6, 13, 22, 91, 128, 157

Райе (Rice H.G.) 109

Роджерс X. (H.Rogers, Jr.) 39, 58

Сипсер M. (Michael Sipser) 60

Тарский A. (A. Tarski, 1902-1983) 139, 140

Тьюринг A. M. (Alan Matison Turing, 1912-1954) 6, 77, 112,

153, 156, 157 Успенский В. A. 109 Ферма П. (P. Fermat (1601-1665) 15 Фридберг P. (R. M. Friedberg) 91 Чёрч A. (A. Church) 157

КНИГИ ИЗДАТЕЛЬСТВА МЦНМО

Программирование: теоремы и задачи (А.Шонь)

В этой книге объясняются приёмы, помогающие на­писать правильно и быстро работающую программу вме­сте с доказательством её правильности. Книга написана в форме задач с решениями.

Названия глав: 1. Переменные, выражения присваива­ния; 2. Порождение комбинаторных объектов; 3. Обход дерева. Перебор с возвратами; 4. Сортировка; 5. Конеч­ные автоматы и обработка текстов; 6. Типы данных; 7. Рекурсия; 8. Как обойтись без рекурсии; 9. Разные алгоритмы на графах; 10. Сопоставление с образцом; 11. Представление множеств. Хеширование; 12. Предста­вление множеств. Деревья. Сбалансированные деревья; 13. Контекстно-свободные грамматики; 14. Синтаксиче­ский разбор слева направо.

Издана в 1995 году. 264 с. Свободно распространяе­мый текст (ASCII, TfrjX, PostScript) находится по адресу

ftp://ftp.mccme.ru/pub/users/shen/progbook

Начала теории множеств (Н.К.Верещагин, А.Шонь)

Основные понятия теории множеств (мощности, ор­диналы, трансфинитная индукция) входят в число вещей, которые хорошо бы знать каждому грамотному матема­тику.

Книга представляет собой популярный рассказ об этих понятиях и основана на материалах лекций для младшекурсников, которые авторы читали на мехмате МГУ в разные годы.

Исходные тексты книги (TfrjX, PostScript) свободно распространяются и доступны по адресу

ftp://ftp.mccme.ru/pub/users/shen/logic/sets

Квантовые вычисления (М.Вялый, А.Китасв, А.Шонь)

В 1997/8 учебном году А.Китасв прочёл в Независи­мом Московском университете спецкурс про квантовые вычисления, предварённый несколькими вводными лек­циями про основы классической теории сложности вычи­слений (их прочёл А. Шень). На основе записей этого кур­са М. Вялый написал текст книги, которая представляет собой одно из первых в России и в мире систематических изложений основ теории квантовых вычислений.

Исходные тексты книги (TfrjX, PostScript) свободно распространяются и доступны по адресу

ftp://ftp.mccme.ru/pub/users/shen/quantum

Алгоритмы: построение и анализ

Книга представляет собой стандартный американ­ский учебник по методам построения и анализа эффек­тивных алгоритмов, написанный на основе одноимён­ного курса в Массачусетском технологическом инсти­туте и выдержавший более 15 изданий в США (пер­вое — в 1990 году). Её авторы — Thomas И. Gormen, Charles Е. Leiserson, Ronald L.Rivest.

В ней разбираются важнейшие классы эффективных алгоритмов и методы их построения (как классические, так и современные). Изложение подробное (в ней около тысячи страниц, более 200 рисунков), понятное и матема­тически строгое. Книгу можно использовать в качестве учебника или справочника, она будет полезна и студен­там, и работающим программистам. Очень рекомендуем!

Из-за своего размера книга получилась доволь­но дорогой, но издательство обещает скидку в 10% всем читателям, предъявившим этот ку­пон! Адрес: Москва, 121002, Большой Власьев-ский, 11.

Как писал американский математик Эмиль Пост, понятие вычислимости может сыграть в истории дискретной математики роль, уступающую по значению лишь понятию натурального числа.

Теория вычислимых функций представляет интерес не только в связи с компьютерами; она является одной из центральных областей математической логики.

Многое из этой теории вполне доступно начинающим; мы пытались рассказать о ней, имея в виду самых разных читателей — от подготовленных школьников до профессиональных математиков.

Книга основана на материалах лекций для младшекурсников, которые авторы читали на мехмате МГУ в разные годы. В этой серии уже вышла книга «Начала теории множеств»; готовится к печати книга «Языки и исчисления».