Верещагин Н.К., Шень А. — Вычислимые функции :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Красота

Верещагин Н.К., Шень А. — Вычислимые функции

Верещагин Н.К., Шень А. — Вычислимые функции

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Вычислимые функции

Авторы: Верещагин Н.К., Шень А.

Аннотация:

Книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В ней рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции). Изложение рассчитано на учеников математических школ, студентов-математиков и всех интересующихся основами теории алгоритмов. Книга включает в себя около 90 задач различной трудности.

Язык:

Рубрика: Computer science/Вычислимость/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1999

Количество страниц: 173

Добавлена в каталог: 30.09.2004

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

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

-вычислимая функция      85
$0,0',\dots,0^{(n)}$       104
-вычислимая функция      103
-перечислимое множество      103
-разрешимое множество      103
      105
      10
-полное множество      61 65 66 74 75 103
-сводимость      59 74 100 139
-сводимость пар      73
-сводящая функция      59
-степень      103
-эквивалентные множества      103
-сводимость      77
-степень      103
-эквивалентные множества      103
$\alpha$ -вычислимая функция      81 159
$\alpha$ -перечислимое множество      82
$\beta$ -функция Гёделя      136 144
$\exists x$ , $\forall x$       98
$\Gamma(T)$       42
$\leqslant_m$       59
$\leqslant_T$       77
$\mathcal{F}[\alpha]$       159
$\mathrm{Disjoint}(A)$       106
$\mathrm{Proof}(x,y)$       142
$\mathrm{Subset}(A)$       105
$\mu$ -оператор      155
$\pi$       10
$\Pi_2$       109
$\Pi_n$       98—100 138 143
$\Sigma_n$       98—100 104 138 143
$\wedge$ , $\vee$ , $\neg$       98
ExecuteProgram, процедура      51
GetProgramText, процедура      51
Адекватность      140
Аккерман, В.      150 163
Аккермана функция      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
Вычислимость относительно $\alpha$       81
Вычислимость с оракулом      76 159
Вычитание усечённое, рекурсивное, определение      147
Гёдель, К.      136 144 157
Гёделя теорема      140 141
Гильберт, Д.      143
Главная (гёделева) нумерация      24 26 32
Главная универсальная функция      25 28
Главная универсальная функция относительно $\alpha$       84
Главное универсальное множество      29 30 61
Головка      113
Гомоморфизм      126
График функции      14
Двустороннее ассоциативное исчисление      124 127
Декартово произведение множеств      13
Десятая проблема Гильберта      143
Диагональная функция      47
Диагональное сечение      21 61 73
Дизъюнкция      98 100
Диофантово уравнение      15
Доказательство      141
Дополнение      12 99
Евклид      150
Заключительное состояние      114
Изоморфизм -полных множеств      66
Изоморфизм -полных пар      75
Изоморфизм главных нумераций      39
Изоморфизм универсальных множеств      56
Иммунное множество      22 23 62 65
Исчисление      140
Исчисление ассоциативное      118
Исчисление неразрешимое      119 123 158
Кванторы      98 142
Кванторы ограниченные      148
Китайская теорема об остатках      137
Клини, С.К.      157 158
Композиция функций      24 27
Конечно порождённая полугруппа      126
Конечное множество, номер      105
Конкатенация      126
Конструктивный объект      8
Конфигурация машины Тьюринга      114 120 132
Конъюнкция      98 100
Коперечислимость      99
Корректное множество      79 160
Креативное множество      71
Лента      113
Марков, А.А. (младший)      128
Массивы, моделирование      131
Матиясевич, Ю.В.      15 143
Машина Поста      157
Машина с конечным числом регистров      129
Машина с оракулом      76
Машина Тьюринга      6 112 113 115 117 125 132 153 156 157
Минимизации оператор      149 155
Множества -эквивалентные      103
Множества -эквивалентные      103
Множества, неотделимость      21 72
Множества, эффективная неотделимость      21 72
Множество -перечислимое      103
Множество -разрешимое      103
Множество -полное      61 65 103
Множество арифметическое      129 134 135 138 139 143
Множество иммунное      22 23 62 65
Множество креативное      71
Множество неразрешимое      10
Множество номеров      36 109
Множество номеров нигде не определённой функции      32
Множество перечислимое      10 12 13 15 98 138 143
Множество перечислимое неразрешимое      20 104 123
Множество примитивно рекурсивное      147
Множество продуктивное      69
Множество простое      22 66
Множество разрешимое      9 13 15 98 138
Множество универсальное      18
Множество универсальное в $\Sigma_n/\Pi_n$       101
Множество эффективно неперечислимое      63
Моделирование      120
Мучник, Альберт А.      91
Натуральная нумерация      24
Начальное состояние      113
Недетерминированный алгоритм      13
Неотделимые множества      22 72
Неподвижная точка      45 142
Неразрешимое ассоциативное исчисление      119 123 158
Неразрешимое множество      10
Несравнимые по Тьюрингу множества      89

Нигде не определённая функция      109
Нижняя точка      21
Новиков, П.С.      128
Номер      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
Перечислимость относительно $\alpha$       82
Перечислимые неотделимые множества      21 37
Перечислимые свойства функций      41
Подслово      119
Подстановка      145
Полнота      140
Полугруппа      125 127
Полухарактеристическая функция      11 59
Пост, Э.      6 13 22 91 128 157
Поста машина      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
Райс      109
Результат работы      114
Рекурсивная функция      145
Рекурсия      145 150
Рекурсия возвратная      151
Рекурсия примитивная      145
Рекурсия совместная      150
Релятивизация      81
Роджерс, X.      39 58
Роджерса теорема      39 58
Сведение      32
Свободная полугруппа      126
Сводимость нумераций      32
Сводимость по Тьюрингу      77 88
Сечение диагональное      21
Сечение множества      18
Сечение функции      17
Си      40
Сильно главная нумерация      84
Символ      113 118
Сипсер, М.      60
Скачок      103
Слово      118 126
Сложение, рекурсивное определение      146
Совместная рекурсия      150
Совместные образцы      79
Соотношения в полугруппе      125—127
Состояние      113 118
Состояние заключительное      114
Состояние начальное      113
Стек      132
Степень неразрешимости      103
Счётчик команд      135
Таблица переходов      113 114 121
Тарский, А.      139 140
Тарского теорема      139 140
Тезис Тьюринга      117
Теорема Гёделя о неполноте      140 141
Теорема Клини о неподвижной точке (о рекурсии)      45
Теорема Клини о нормальной форме      158
Теорема Мучника — Фридберга      92
Теорема о неподвижной точке для множеств      55
Теорема о неподвижной точке с параметром      54
Теорема об униформизации      15
Теорема Поста      13 33 108
Теорема Роджерса      39 58
Теорема Тарского      139 140
Теорема Успенского — Райса      33 109
Транслятор      40
Тьюринг, А.М.      6 77 112 153 156 157
Тьюринга машина      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
Универсальное в $\Sigma_n/\Pi_n$ множество      101
Универсальное множество      18
Универсальное перечислимое множество      18 101
Успенский, В.А.      109
Успенского — Райса теорема      33 109
Ферма, П.      15
Формула арифметики      129 134
Формула, представляющая множество      135
Фрагмент      89
Фридберг, Р.      91
Функция -вычислимая      85

1 2

Реклама

© Электронная библиотека попечительского совета мехмата МГУ, 2004-2024

Электронная библиотека мехмата МГУ

Valid HTML 4.01!

|

Valid CSS!

О проекте