Роджерс Х. — Теория рекурсивных функций и эффективная вычислимость :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Красота

Роджерс Х. — Теория рекурсивных функций и эффективная вычислимость

Роджерс Х. — Теория рекурсивных функций и эффективная вычислимость

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

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

Название: Теория рекурсивных функций и эффективная вычислимость

Автор: Роджерс Х.

Аннотация:

Книга содержит изложение современного состояния теории рекурсивных функций и обзор основных приложений этой теории. В ней прослежено развитие теории рекурсивных функций, начиная с ее зарождения в тридцатых годах и кончая результатами исследований самых последних лет. Не предполагающая в основной своей части никаких предварительных знаний, кроме знакомства с теоретико-множественной терминологией, книга Роджерса написана хорошим, ясным языком; при этом формальному изложению предпосылаются содержательные рассуждения, разъясняющие природу вводимых понятий или идей построений и доказательств; в ней содержится очень много упражнений.
Книга рассчитана на читателей, интересующихся современными проблемами математической логики и теории алгоритмов. Она доступна аспирантам и студентам старших курсов университетов и пединститутов.

Язык:

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

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

ed2k: ed2k stats

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

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

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

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

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

$\aleph_0$ -мышление ( $\aleph_0$ -mind)      520
$\Delta^1_1$ -индекс      509
$\Delta^1_2$ -индекс      533
$\Delta^1_2$ -множество ( $\Delta^1_2$ -set)      490 532—535 577
$\lambda$ -обозначение (lambda notation)      13
$\mu$ -оператор (mu operator)      48 51
$\omega$ -модель ( $\omega$ -model)      502 572
$\omega$ -непротиворечивость ( $\omega$ -consistency)      133 139
$\omega$ -скачок ( $\omega$ -jump)      330
$\Pi^1_1$ -множество ( $\Pi^1_1$ -set)      490 508—514
$\Pi^1_1$ -функции (partial $\Pi^1_1$ -functions)      516 520
$\Sigma^1_2$ -множество ( $\Sigma^1_2$ -set)      532—535 577
$\Sigma^1_n$ -, $\Pi^1_n$ -высказывание      497
$\Sigma^1_n$ -, $\Pi^1_n$ -индекс      482 580
$\Sigma^A_n$ -, $\Pi^A_n$ -индекс      394
$\Sigma^{(S)}_{n}$ -, $\Pi^{(S)}_{n}$ -формы      446
$\Sigma^{1A}_n$ -, $\Pi^{1A}_n$ -индекс      524
$\Sigma^{n}_{n}$ -, $\Pi^{1}_{n}$ -формы      480
$\Sigma_n$ -, $\Pi_n$ -высказывание      409
$\Sigma_n$ -, $\Pi_n4$ -индекс      393
$\Sigma_{n}$ -, $\Pi_{n}$ -, $\Sigma^{A}_{n}$ -, $\Pi^{A}_{n}$ -формы      390
$\Sigma_{n}$ -, $\Pi_{n}$ -формы      431
btt-сводимость (btt-reducibility)      150—155 157 161—162 407 408
btt-сводимость, полные множества (complete sets for btt-reducibility)      151 154 161
btt-сводимость, степени (degrees for btt-reducibility)      151 154—155 157 223 230
c-сводимость (c-reducibility)      162
c-эквивалентность (c-equivalence)      297—300 308—310 318 320 321 323
calculus ratiocinator      60
characteristica universalis      60
e-сводимость и e-степени (e-reducilibity and e-degrees)      189—193 198 200—201 208 359—363
L-P-уточнение (L-P-specifications)      19
m-сводимость (m-reducibility)      110—121 142 147 149 216 293 307 406
m-сводимость, полные множества (complete sets for m-reducibility)      118—122 140—142 148—149 155 236—237
m-сводимость, степени (degrees for m-reducibility)      111—112 142 147 149 155—157 203 209 223 231
p-сводимость (p-reducibility)      162
P-символизм (P-symbolism)      19
Poccep      133 139
q-креативное множество (q-creative set)      162 276
q-сводимость (q-reducibility)      162
q-сводимость, полные множества (complete sets for)      162
q-творческое множество (q-creative set)      см. «q-креативное множество»
r-максимальное множество (r-maximal set)      313 323—325
r-система (г-system)      264
s-m-n-теорема (s-m-n-theorem)      42—43 64
T-сводимость (T-reducibility)      168 179—181 184—189 201—204 207 208 216—220 406 408 471 519
T-сводимость полные множества (complete sets for T-reducibility)      180 181 187—189 207 323 425
T-сводимость степени (degrees for T-reducibility)      180—185 203 209 216—220 295 307 326—386 359 369 403 426 487 556—558
tt-сводимость (tt-reducibility)      145—155 180—181 184—188 201 202 207 216 406 471
tt-сводимость, полные множества (complete sets for tt-reducibility)      147—151 154 185 187 204
tt-сводимость, степени (degrees for tt-reducibility)      147 149—150 155 157—158 161 181 185 203 209 223 426
tt-сводимость, степени рекурсивно перечислимые (recursively enumerable tt-reducibility)      147 181
tt-сводимость, цилиндры (cylinders for tt-reducibility)      149—150 161
tt-условие (tt-condition)      146
tt-условие дизъюнктивное (disjunctive tt-condition)      162
tt-условие, ассоциированное множество (associated set of tt-condition)      146
tt-условие, порядок (norm of tt-condition)      146
y-индекс      568
y-формы      567 568
Абсолютно неопределенный функционал (strongly undefined functional)      459
Абсолютные понятия, (absolute concepts)      38
Аддисон      456 484 491 518 520 528 529 535 545 574 579
Аккермана функция (Ackermann generalized exponential)      25
Аксиоматизация (axiomatization)      410
Аксиоматизация семантически непротиворечивая (sound axiomatization)      410 413
Аксиоматизируемая теория (axiomatizable theory)      129 188 223 277
Акст      72
Алгоритм нечисловой (non-numerical algorithm)      46—49
Алгоритм относительный (relative algorithm)      168—169
Алгоритм, неформальное понятие (algorithm, informal notion)      17—22 36—39 47
Алгоритмическая всюду определенная функция (algorithmic function)      18 25—26 36—39
Алгоритмическая функция (algorithmic partial function)      29
Аналитическая иерархия (analytical hierarchy)      478—586
Аналитическая иерархия, нормальная форма и теорема о перечислимости (analytical hierarchy, normal form and enumeration theorem)      481—483
Аналитическая иерархия, теорема о нормальной форме (analytical hierarchy, alternative normal-form theorem)      48
Аналитическая иерархия, теорема о полноте (analytical hierarchy, completeness theorem)      486
Аналитические множества и отношения (analytical sets and relations)      474 478—494;
Аналитическое в (относительно) (analytical in)      523—524 526
Аналитическое множество (analytical set)      491
Аналоги классических теорий (analogue structures)      68 70 470 475—477 521
Аналогии между иерархиями (analogies between hierarchies)      491 515—523 568
Аппель      206
Арифметика 2-го порядка (second-order arithmetic)      492 493 496 501 502
Арифметика 2-го порядка, пример      498
Арифметика изолей (isolic arithmetic)      163
Арифметическая всюду определенная функция (arithmetical function)      455
Арифметическая иерархия (arithmetical hierarchy)      387—428
Арифметическая иерархия классов множеств (arithmetical hierarchy of sets of sets)      429—444 454 455 471 472
Арифметическая иерархия классов функций (arithmetical hierarchy of sets of functions)      444—458 472—474
Арифметическая иерархия, нижние грани (arithmetical hierarchy, lower bounds)      416
Арифметическая иерархия, нормальные формы (arithmetical hierarchy, normal forms)      391—394
Арифметическая иерархия, теорема о полноте (arithmetical hierarchy, completeness theorem)      405
Арифметическая иерархия, теоремы о нормальной форме и перечислимости (arithmetical hierarchy, normal form and enumeration theorems)      394 432 443 446 447 457
Арифметическая представимость (arithmetical representation)      400—403
Арифметическая функция (arithmetical partial function)      474
Арифметическая эквивалентность (arithmetical equivalence)      331
Арифметически выразимые предложения теории множеств (arithmetically expressible sentences of set theory)      412—415
Арифметически продуктивное множество (arithmetically productive set)      281
Арифметические интуитивно простые определения (arithmetically intuitively simple definitions)      424; см. также «Арифметическая иерархия»
Арифметические множества и отношения (arithmetical sets and relations)      331 387—391 406 430 433 434 446-448 513
Арифметический анализ (arithmetical analysis)      477
Арифметическое в (относительно) (arithmetical in)      331 381 406
Арифметическое действительное число (arithmetical real)      477
Арсланов, М.М.      307 313
Ассер      48
Аффинная геометрия (affine geometry)      73
Базис, определение (basis, definition)      536
Базис, результаты (results)      536—539 551 578
Базисные окрестности (basic neighborhoods)      435 449 473
Банаха — Мазура функционал (Banach — Mazur functional)      467—469
Бенсон      544
Бернайс      276 372 440 472
Бинарное дерево (binary tree)      204—206
Биркгоф      286
Блюм      78 80 172 202 246
Больцано — Вейерштрасса теорема (Bolzano — Weierstrass Theorem)      205 477
Борелевские множества (Borel sets)      398 491 568
Борелевские множества, иерархия на множестве Кантора (Borel sets, hierarchy on the Cantor set)      438
Борелевские множества, классическая иерархия (classical hierarchy of Borel sets)      438 453 456—458
Борелевские множества, пример      387
Булев полином (boolean polynomial)      145
Булева алгебра (boolean algebra)      288 316 317
Булева функция (boolean function)      145
Буль      60
Бун      57
Бурали — Форти парадокс (Burali — Forti paradox)      124 281
Бэра теорема (Bair’s theorem)      347 382—384
Бэровская метрика (Baire metric)      435 449 473
Бэровское пространство (Baire space)      355 449 491
Бэровское пространство, топология (Baire space, topology)      463
Бюхи      138
Ван Хао      422
Ван Хао, пример      472
Веблен      284
Вероятность (probability)      349
Вершина дерева (vertex of a tree)      502
Ветвь дерева (branch of a tree)      205 449 502
Взятие дополнения (complementation)      388 425
Вольпин      275
Вполне продуктивное множество (completely productive set)      125 137 236—238
Вполне рекурсивно перечислимый класс (completely recursively enumerable class)      105
Вполне упорядоченное множество (completely well-ordered set)      281
Всюду определенный функционал (total functional)      467
Вынуждение (forcing)      578
Высказывание (sentence)      128 222
Высказывание первого порядка (first-order sentience)      222
Вычислимые операции, пример      192
Вычислимые уровни иерархии и степени неразрешимости (computing hierarchy levels and degress of unsolvability)      415—424 442 456
Вычислитель, вычислительная машина (computer)      18—22
Ганди      538 551 578
Ганф      225

Гейзер      583
Гейне — Бореля теорема (Heine — Borel theorem)      476 477
Генерическое множество (generic set)      579
Гензель      569
Гёделева нумерация (Godel numbering)      39—41 47—48 63—64 100 129;
Гёделева функция подстановки (Godel substitution function)      257 260—263 415
Гёделевы номера (р.п. индексы) (r.е. indices)      85 96—98
Гёдель      56 60 129 133 262 263 281 401 402 535
Гёделя теоремы о неполноте (Godel incompleteness theorems)      60 129—133 243 281 410 412 499
Гёделя теоремы о неполноте вторая (Godel incompleteness theorems second)      415 428;
Гёделя теоремы о неполноте первая (Godel incompleteness theorems first)      48 139 263
Гёделя — Россера теорема (Godel — Rosser Theorem)      139 412 428
Гжегорчик      72
Гильберт      56 192 372 440 472
Гильберт, десятая проблема (Hilbert, tenth problem)      56 402 410
Гиперарифметическая вычислимость (hyperarithmetical computability)      519—521 574—576
Гиперарифметическая вычислимость, аналог теории рекурсивных функций (hyperarithmetical computability, analogue to recursive function theory)      518 519 574—576
Гиперарифметическая иерархия (hyperarithmetical hierarchy)      556—570 580—586
Гиперарифметическая иерархия классов множеств и классов функций (hyperarithmetical hierarchy sets of sets and sets of functions)      567 568
Гиперарифметическая иерархия общие соображения (heuristic dicussion)      557—559
Гиперарифметическая иерархия формальное изложение (formal development)      560—566
Гиперарифметическая функция (hyperarithmetical function)      516 520 574 575
Гиперарифметические множества (hyperarithmetical sets)      488—492 508—523 556 564 565 574—576
Гиперарифметические множества, свойство замкнутости (hyperarithmetical sets, closure property)      532 540
Гиперарифметические ординалы (hyperarithmetical ordinals)      531
Гиперарифметический анализ (hyperarithmetical analysis)      521
Гиперарифметическое относительно (hyperarithmetical in)      525
Гипергипериммунное множество (hyperhyperimmune set)      189 300 312—314 318 322
Гипергиперпростое множество (hyperhypersimple set)      189 207 291 306 315 322 325 379 386 425
Гипергиперпростое множество, пример      292
Гипериммунное множество (hyperimmune set)      181—182 203—204 206 296 300 312 318 320 322 384
Гиперпростое множество (hypersimple set)      181—184 189 203—204 291 293 304 306 309 322 425 428
Гиперскачок (hyperjump)      523—532 554 576 577
Гиперстепень (hyperdegree)      523—532 538 539 554 576 577
Главный идеал (principal ideal)      385
Главный идеал, пример      299
Гольдбаха гипотеза (Goldbach’s conjecture)      26
Гомологическая алгебра (homological algebra)      163
Группа преобразований (group of transformations)      73
Густота относительно (density in)      204
Деккер      72 115 116 122 133 136 137 142 156 158 160 161 163 182 204 206 207 217 286 296 318
Дерево (tree)      204—205
Деревья с конечными путями (finite-path trees)      450 473 502—508 572 573
Деревья с конечными путями, ординалы (ordinals of finite-path trees)      503—506
Деревья с конечными путями, сложение и умножение (finite-path trees, addition and multiplication)      504 505
Джокуш      155 158 162 163 184 231 471
Диагонализация (diagonalization)      27—29 51 232
Дизъюнктные элементы (disjoint elements)      225
Допустимая нумерация (acceptable indexing or numbering)      100 233 275 327 380 393 425 575
Дребен      72
Дуальный идеал максимальный (dual ideal maximal)      316
Дуальный идеал простой (dual ideal prime)      316 317
Дуальный идеал решетки (dual ideal in lattice)      143 161 204 288 289 316 317 320 322
Дуальный идеал собственный (dual ideal proper)      316
Дэвис      8 30 37 39 41 42 56 57 58 71 72 78 114 169 261 401 402
Евклида алгоритм (Euclidean algorithm)      18 20
Ейтс      189 206 207 220 230 300 301 307 318 321—323 373 378 379 424
Ершов, Ю.Л.      5
Игры система (gambling system)      320
Идеал решетки (ideal in a lattice)      288 318;
Иерархии (hierarchies)      69; см. также «Аналитическая иерархия» «Арифметическая «Гиперарифметическая
Изолированное множество (isolated set)      142—144
Изолическая сводимость (isolic reducibility)      163
Изоль (isol)      163
Изоморфизм относительно группы преобразований (G-изоморфизм) (isomorphism with respect to a group)      74
Иммунное множество (immune set)      142—144 156 158—161 203 204 206 292 308
Инвариантность относительно обозначений (notational invariance)      558 559
Инвариантов полное множество (invariants, complete set of)      74
Индекс (index)      40
Индексное множество (index set)      416
Интерполяционная теорема Лагранжа (Lagrange interpolation theorem)      145
Интерпретация опровержением контрпримера (no-conterexample interpretation)      470 471 477
Интуитивный смысл степеней (intuitive significance of degrees)      336—340
Интуиционистское исчисление высказываний (intuitionistic propositional calculus)      372 385
Иррациональные числа (irrationals)      449 473
Истинностная таблица (truth table)      145
Истинность в элементарной арифметике (truth in elementary arithmetic)      130—131
Канонически перечислимый класс (canonically enumerable class)      104
Канонический индекс (номер) (canonical index)      97—98
Кантора множество (канторово множество) (Cantor set)      279 347
Кантора теорема (Cantor's theorem)      28 88 240
Кантора — Шредера — Бернштейна теорема (Cantor — Schroder — Bernstein theorem)      116
Канторово пространство (Cantor space)      347 349 382 383
Канторово пространство, топология (Cantor space, topology)      346 347 435—437
Карри      48
Категория (в алгебре) (category)      163
Категория вторая      347
Категория первая (first category)      347
Категорные методы (category methods)      346 361—363 382—384 437 438 449 473
Квазикреативное множество (quasicreative set)      см. «Квазитворческое множество»
Квазимаксимальное множество (quasimaximal set)      303 320 323 325
Квазисжатое множество (quasicohesive set)      300 318 321 324
Квазитворческое множество (quasicreative set)      162
Квантор (quantifier)      14
Квантор бесконечности (infinite quantifier)      421
Квантор общности (universal quantifier)      14
Квантор ограниченный (quantifier bounded)      398 425
Квантор ограниченный рекурсивно (quantifier bounded recursively)      425
Квантор существования (existential quantifier)      14
Квантор, тип (quantifier, type)      479
Кванторы по множествам (set quantifiers)      489 490 571
Кент      75 299
Китайская теорема об остатках (Chinese remainder theorem)      401
Кларк      479
Классы замкнутые (classes closed)      436 450 451
Классы открытые (classes open)      436 450 451
Классы функций и множеств (classes of functions and sets)      435 449
Клауа      477
Клейн      73
Клив      127
Клини      7 8 15 29 30 34 36 37 39 42 45 50 210 212 233 235 236 251 263 264 266 267 269 270 275 330 333 334 337 338 351—354 381 383 394 403 405 425 432 447 478 480—486 519 528 529 536 540 564 565 581 584
Клини пример      387 392 479
Клини — Брауэра упорядочение (Kleene — Brouwer ordering)      506 520 572
Ключевой остов (key array)      105
Кнастера — Тарского теорема (Knaster — Tarski theorem)      249 284
Ко-свойство (complementary property)      142—143
Кодирование (coding)      46—49
Кодовое число кортежа (sequence number)      482
Коиммунное множество (co-immune set)      143
Коконечное множество (co-finite set)      143
Компактность (compactness)      435 449
Компактность для деревьев (compactness for trees)      205 435
Композиция (отношений) (relative product)      103
Кондо — Аддисона теорема об униформизации (Kondo — Addison uniformization theorem)      545—550
Конечные множества (finite sets)      96—99 292
Конечный автомат (finite-state machine)      20 64—65
Конструктивно бесконечное множество (constructively infinite set)      226
Конструктивно нерекурсивная функция (constructively nonrecursive function)      319
Конструктивно нерекурсивное множество (constructively nonrecursive set)      209—210
Конструктивный ординал (constructive ordinal)      265 268 271—274 332 485 506 507 509 511 531 534
Конфигурация (instantaneous description)      33
Конфигурация конечная (instantaneous description finite)      63
Коши последовательность (Cauchy sequence)      382
Коэн      331 545 578
Крайдер      276 569
Креативное множество (creative set)      317 425 428;
Крейсел      280 422 464 468 470 475 520 521 575 576 584—586
Крейсела — Сакса аналог (Kreisel — Sacks analogue)      521—523 575 576
Крейсела — Сакса аналог, пример      526
Кроссли      72
Крэйга теорема (Craig’s theorem)      138
Куайн      222 276
Кузнецов, А.В.      67 182 440
Куратовский      398 576
Куратовского, пример      491
Лакомб      384 464 475
Лакхам      104 517 559 574
Лахлан      155 207 220 313—315 325 331 378 380 386
Лахлана пример      292
Лейбниц      60

1 2 3

Реклама

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

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

Valid HTML 4.01!

|

Valid CSS!

О проекте