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

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

Авторизация

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

Красота

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

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

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

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

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

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

Аннотация:

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

Язык:

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

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

ed2k: ed2k stats

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

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

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

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

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

Лемма о рекурсии (recursion lemma)      278 510 573
Лерман      380
Ли      245
Логика (logic)      60 68 69 70 127—133 260—263 408—415 426—428 498
Логика предикатов (quantificational logic)      394 400 426 433 447 483
Логика предикатов, выводимость (доказуемость) (deducibility in quantificational logic)      38 222
Логические обозначения (logical notation) (Введение)      11 14—15
Лоэв      320
Мазур      467—469
Майхилл      72 105 116 135 136 137 158 163 206 236 253 254 280 286 294 296 317 346 362 384 460 518
Мак-Лохлин      206 311 317 318 321—323
Мак-Нотн      105
Максимальное множество (maximal set)      165 183 203 204 207 300—307 311 314 320 323 325 379 425
Максимальное множество его подмножества (subsets of maximal set)      303—307
Мальцев      5 401
Манастер      163
Марквальд      272 421
Маркеры (markers)      213 226—230 373
Марков, A.A.      36 57 67
Мартин      294 304—307 314 321 322 324 331 378 383 384 386 426
Массовая проблема (mass problem)      364 385
Массовая проблема 1-сведения (mass problem of one-one reduction)      370
Массовая проблема отделения (mass problem of separability)      370
Массовая проблема перечисления (mass problem of enumerability)      368
Массовая проблема разрешения (mass problem of solvability)      368; см. также «Степени трудности»
Матиясевич, Ю.В.      56 401 410
Медведев, Ю.Т.      181 182 360 363 364 366—369 371 372
Медведева решетка (Medvedev lattice)      363—372 385 440
Медведева решетка, релятивизация (Medvedev lattice, relativization)      371; см. также «Степени трудности»
Мезоичное множество (mesoic set)      158
Методы приоритета (priority methods)      216 226—230 326 373
Минимальные степени (minimal degrees)      355—359 363 379 383 384
Минский      63 72
Много-однозначная сводимость, полное множество и степень (many-one reducibility, complete set and degree)      см. «m-сводимость»
Московакис      72 285 476 521 532 563 583 585
Мостовский      72 263 428
Мостовского пример      387 419
Мучник, А.А.      62 164 188 212—218
Мучника — Фридберга теорема (Friedberg — Muchnik Theorem)      212—218 329 330
Натуральное число (integer)      11
Неотделимые множества (inseparable sets)      220—221
Непересекающиеся рекурсивно перечислимые множества (disjoint recursively enumerable sets)      126—127
Неподвижная точка (fixed-point value)      233
Непротиворечивость (consistency)      133 139 241—243 262
Неразрешимая п.п.ф. (undecidable wff)      132
Неразрешимости структуры (unsolvability structures)      68—69
Неразрешимые проблемы (unsolvable problems)      68
Нероуд      163 187 201
Несравнимые множества и гиперстепени (incomparable sets and hyperdegrees)      528 576
Несравнимые множества и степени (incomparable sets and degrees)      111—112 209—216 328 334 335 338 381
Новиков, П.С.      57
Область значений (Val)      13
Область определения (Arg)      12
Область полного определения функционала (strong domain of a functional)      459
Область слабого определения функционала (weak domain of a functional)      459
Обобщенная вычислимость (generalized computability)      515—523 532 574—576
Обобщенная машина (generalized machine)      519 520
Обобщенная машина, дерево-диаграмма (generalized machine, tree diagram)      520
Обобщенно сжатые множества (generalised cohesive sets)      308 318 321 324
Общерекурсивность (general recursiveness)      46
Общерекурсивные функции (recursive functions)      17—43 51 60—61
Общерекурсивные функции относительно (recursive functions relativized)      173
Общерекурсивные функции, определение (recursive functions, definition)      36
Общерекурсивные функции, основные результаты (recursive functions, basic results on)      36—37
Общерекурсивные функции, расширенная клиниева формализация (recursive functions, Kleene characterization extended)      170; см. также «Рекурсивно относительно» «Релятивизация»
Общерекурсивные функции, теорема о нормальной форме (recursive functions, normal-form theorem)      50
Общерекурсивные функции, теория (recursive functions, theory)      51—52
Общерекурсивные функции, формализация (recursive functions, formal characterization)      28—38
Общерекурсивные функции, формализация по Клини (recursive functions, formal characterization Kleene)      34—35
Общерекурсивные функции, формализация по Тьюрингу (recursive functions, formal characterization Turing)      30
Общерекурсивный оператор (general recursive operator)      195 201—202 208
Общерекурсивный функционал (general recursive functional)      460 462
Объемность (extensionality)      см. «Экстенсиональность»
Ограничение числа шагов (bound on the length of a computation)      21—22 51
Ограниченнотабличная сводимость, полные множества и степени (bounded truth-table reducibility, complete sets and degrees)      см. «btt-сводимость»
Одно-односводимость (1-сводимость), полное множество и степень (one-one reducibility (1-reducibility) complete set, and degree)      110—122 202 216 217
Одно-односводимость, полные множества (complete sets for one-one reducibility)      118—120 236—238
Одно-односводимость, степени (degrees for one-one reducibility)      111 142 150 155—158 160 203 216 223 328
Одно-односводимость, эквивалентность (equivalence for one-one reducibility)      116—118
Однозначное множество (single-valued set)      99
Однозначность (single-valuedness)      12 99—101
Однозначность, теорема (single-valuedness, theorem)      99—101 515 535
Операторы перечисления (enumeration operators)      192—193 208 249 279—280
Операция A (operation A)      491
Операция скачка (jump operation)      326—346 380 381 403 408 519
Операция скачка, итерация (iteration of jump operation)      329
Определимость в логике предикатов (definability within quantificational logic)      395 396 433 434 447 448 484
Определимость неявная (implicit definability)      440 441 455 456 498 543—545 552—555 570 571 579
Определимость явная (explicit)      440 455 498
Определимость, автоморфизмы (definability, and automorphisms)      291
Определимость, автоморфизмы в элементарной арифметике (definability, and automorphisms in elementary arithmetic)      400
Определимость, автоморфизмы в элементарном анализе (definability, and automorphisms in elementary analysis)      494
Оракулы и машины с оракулами (oracles and oracle machine)      169—171 173—174 429 444
Ординальные числа второго числового класса (ordinal numbers in second number class)      273 282
Ординальные числа, $\Delta^1_2$       534—535 551 577
Ординальные числа, обозначения (ordinal numbers, notations)      124 263—271;
Ординальные числа, ординалы (ordinal numbers)      281—285; см. также «Конструктивный ординал» «Рекурсивный
Ординальные числа, теорема о нормальной форме (normal-form theorem for ordinal numbers)      284
Основная лемма о деревьях (basic tree lemma)      505
Основная теорема об операторах (fundamental operator theorem)      195
Открыто-замкнутые множества и классы (open-and-closed sets and classes)      435 449 451 474
Отросток дерева (branch tree)      505 529
Охаши      317
Парикх      273 278 285
Патнам      56 57 63 569
Паульсен      371
Пеано аксиомы (Peano’s axioms)      131 243 263 410 412 471
Пеано аксиомы, пример      497
Пеано арифметика (Peano arithmetic)      131 132 139 281 410 413 414 428
Перемены кванторов (alternations of quantifier)      389 414 491
Пересечение (meet)      286 316
Петер      25
Пирс      60
Платек      371
Плотная структура (dense structure)      219 229
Плотно упорядоченное множество (densely ordered)      293
Подветвь дерева (subbranch of a tree)      450 502
Поддерево (subtree)      205 449 502
Позитивное исчисление высказываний (positive propositional calculus)      372
Полиномиальное отношение (polynomial relation)      400
Полное метрическое пространство (complete metric space)      347 382 435 449
Полное множество $\Sigma^1_n$ , $\Pi^1_n$       486 508
Полное множество $\Sigma_n$ , $\Pi_n$       405; 423
Полное множество (complete set)      108 109 113—114 118—120
Полнота (логическая) (logical completeness)      222 224
Полные степени (complete degrees)      341—348 350;
Полукреативное множество (semicreative set)      164 165
Полупродуктивное множество (semiproductive set)      126 165
Пополнение множества (completion of a set)      327 328
Пост      7 8 36 48 61 62 67 115 125 132 140 141 185 188—189 203 207 210 212 323 330 333 334 337 338 351—354 381 383
Поста проблема (Post’s problem)      188—189 209—216 217 220 424 519 526
Поста теорема (Post’s theorem)      404
Почти-конечность (almost-finiteness)      294 296 308
Правила преобразования кванторов (quantifier rule)      392 480 484 489 512 518 521 582
Правильно построенные формулы (well-formed formulas)      127
Предваренная форма (prenex form)      396
Предельный функционал (limit functional)      467—469
Предикатная форма (predicate form)      389
Представимость, представление (representation)      402 434 448 490 492—498 569 571—572
Представление цепными дробями (continued fraction representation)      449 473 495
Представляющая функция (representing function)      13
Префикс $\Sigma^1_n$ , $\Pi^1_n$       479 480
Префикс $\Sigma_n$ , $\Pi_n$       390 431
Префикс (prefix)      389
Префикс приведенный (prefix reduced)      479
Примитивно рекурсивная функция (primitive recursive function)      22—25
Примитивно рекурсивная функция, схема (derivation for primitive recursive function)      23
Принцип отделимости (separation principle)      105
Принцип редукции (reduction principle)      100
Приоритета методы (priority methods)      216 226—230 326 373

Проблема остановки (halting problem)      43—46 61—63 66 336
Проблема тождества слов в теории групп (word problem for groups)      57
Проблемы однородности (homogeneity problems)      335
Продуктивная функция (productive partial function)      115
Продуктивная функция всюду определенная      124
Продуктивное множество (productive set)      115 122—126 131 132 158 160 236—238 273 276
Продуктивное множество насыщенное (full)      137 241 277
Проективное множество (projective set)      398 491
Проективное множество, пример      387
Проекция, проектирование, взятие проекции (projection)      92 387 388 425 430 446
Проекция, теорема (projection theorem)      92—94 387 426
Производная истинностная таблица (derived truth table)      186 206
Промежуточное кардинальное число (mediate cardinal)      144
Прослеживаемое множество      см. «Ретрассируемое множество»
Простое множество (simple set)      140—144 148 151 156 158—162 164—166 183 217 288 290 292 424 428 518
Простое множество в дополнении (in a complement)      159 164
Процедуры разрешения (decision procedures)      56
Псевдопростое множество (pseudosimple set)      159
Псевдотворческое множество (pseudocreative set)      159
Пур-Эль      469
Рабин      72 160 362
Равномерность (uniformity)      95—96
Разветвленная аналитическая иерархия (ramified analytical hierarchy)      585
Разрешимая теория (decidable theory)      129
Райс      56 65 67 105 208 416 476 519
Рассел      60 144
Рассела парадокс (Russell’s paradox)      240
Регрессивное множество (regressive set)      206
Рекурсивная инвариантность (recursive invariance)      69 75 76 91—92 293 312
Рекурсивная инвариантность относительная (relative recursive invariance)      176
Рекурсивная неразрешимость (recursive unsolvability)      45 53—58
Рекурсивная перестановка (recursive permutation)      74—75 299
Рекурсивная перестановка, группа (recursive permutation, group)      75
Рекурсивная перестановка, свободная от циклов (recursive permutation, cyclefree)      139
Рекурсивная перечислимость (recursive enumerability)      408
Рекурсивная перечислимость дополнения (recursive enumerability of a complement)      312
Рекурсивная перечислимость класса (recursive enumerability of a class)      102
Рекурсивная перечислимость множества (recursive enumerability of a set)      см. «Рекурсивно перечислимые множества»
Рекурсивная перечислимость отношения (recursive enumerability of a relation)      89—94
Рекурсивная перечислимость проблемы (recursive enumerability of a problem)      62
Рекурсивная перечислимость степени (recursive enumerability of a degree)      111—112 203 326 337 345 346 373 378 379
Рекурсивная степень (recursive degree)      111
Рекурсивная структура (recursive structure)      68
Рекурсивная эквивалентность (recursive equivalence)      226
Рекурсивно аппроксимируемая функция (recursively approximable function)      319
Рекурсивно неразложимое множество (recursively indecomposable set)      308 311 314 321—323
Рекурсивно неразложимое множество, пример      296
Рекурсивно отделимые множества (recursively separable sets)      126
Рекурсивно перечислимое в (относительно) (recursively enumerable set(s) in)      174 193 202 203 328 381
Рекурсивно перечислимое множество (recursively enumerable set(s))      82—94 108 213—231
Рекурсивно перечислимое множество регулярное (regular recursively enumerable set(s))      172
Рекурсивно перечислимое множество, аналогия с теорией множеств (recursively enumerable set(s) as analogy to set theory)      239—241
Рекурсивно перечислимое множество, в порядке возрастания (recursively enumerable set(s) in increasing order)      83
Рекурсивно перечислимое множество, в порядке неубывания (recursively enumerable set(s) in nondecreasing order)      83
Рекурсивно перечислимое множество, индекс (номер) (index of recursively enumerable set(s))      85
Рекурсивно перечислимое множество, решетка (lattice of recursively enumerable set(s))      290—294 299 300 303 306 307 317
Рекурсивно разложимое множество (decomposable set)      см. «Рекурсивно неразложимое множество»
Рекурсивное более чем в одном множестве (recursive in more than one set)      175; см. также «Релятивизация»
Рекурсивное дерево (recursive tree)      505
Рекурсивное дерево строго (strongly recursive tree)      507
Рекурсивное определение (recursive definition)      22
Рекурсивное относительно (в) (recursive in)      174 193 198 202 208 457
Рекурсивные действительные числа (recursive reals)      470 475—477
Рекурсивные комплексные числа (recursive complex numbers)      476
Рекурсивные множества и отношения (recursive sets and relations)      81—84 89—95
Рекурсивные операторы (recursive operators)      193—202 208 279—280 470
Рекурсивные ординалы (recursive ordinals)      272 273
Рекурсивные ординалы, система обозначений W (recursive ordinals, notations W)      285 508 512 572 573
Рекурсивный анализ (recursive analysis)      470 476—477
Рекурсивный изоморфизм (recursive isomorphism)      75 76 116—118
Рекурсивный функционал (recursive functional)      459 462—465 468 469 474
Рекурсия, определения по рекурсии (recursion, definitions by)      255
Релятивизация (relativization)      168—179 330 335 337 338 443 444 456 469 523-525 529 530 567
Релятивизация s-m-n-теоремы (relativization of s-m-n theorem)      177
Релятивизация алгоритма (algorithm relativization)      175
Релятивизация кванторов (relativization of quantifiers)      425 426
Релятивизация основной теоремы о рекурсивно перечислимых множествах (relativization of basic theorem on recursively enumerable sets)      177
Релятивизация теоремы о проекции (relativization of projection theorem)      177
Релятивизация теории (relativization of theory)      176—179
Релятивизация теории полная (full relativization of theory)      176—179
Релятивизация теории частичная (partial relativization of theory)      176—179
Ретрассируемое (прослеживаемое) множество (retraceable set)      189 206 230 312
Решетка (lattice)      286 316
Решетка дистрибутивная (distributive lattice)      287 316 317 385
Решетка множества как (sets as a lattice)      286—291 371 385
Решетка с дополнениями (lattice complemented)      288
Решетка, автоморфизм (automorphism of lattice), пример      291
Решетка, единичный элемент (unit element of lattice)      287
Решетка, нулевой элемент (zero element of lattice)      287
Решетка, подрешетка (lattice, sublattice)      287
Решетка, факторрешетка (quotient lattice)      288—291 371 385
Решетка, цепь (chain in lattice), пример      307
Решето (sieve), пример      491
Римана гипотеза (Riemann hypothesis)      414
Риттер      104 477 521
Рихтер      569
Ричи      72
Робинсон, Дж.      56—57 72
Робинсон, Р.В.      313 323 324
Робинсон, Р.М.      263 402
Роджерс      5 424 428 509 569
Роуз      319
Роуза пример      296
Рыль-Нардзевски      428
Сакс      166 217 218 220 227 229 295 301 307 323 330 331 346 373 378—380 383 385 521 575 576
Самовоспроизводящиеся машины (self-reproducing machines)      243—245
Саппес      15 222
Сводимость (reducibility)      53—56 61—62 68 106-109 180 286 387 417
Сводимость по перечислимости (enumeration reducibility reducibility)      189—193 200—201 208;
Сводимость посредством функции (reducibility via function)      110
Сводимость сильная (strong reducibility)      112 180
Сводимость слабая (weak reducibility)      180 293
Сегмент (segment)      332
Сегмент начальный (initial segment)      332
Семантика (semantics)      69
Семантическая непротиворечивость (soundness)      223
Сжатие (склеивание) кванторов (contraction of quantifiers)      392 432 446;
Сжатые множества (cohesive sets)      294 296—300 308—311 318 320 322—324
Сжатые множества наполненные (cohesive sets completed)      299 300 303 308 311 320 322 323
Сильная теорема об иерархии (strong hierarchy theorem)      403—406
Сильно неотделимые множества (strongly inseparable sets)      165 320
Синглтерри      513
Сингулярность (singularity)      66
Синтаксис (syntax)      69
Система обозначений для ординалов (system of notation for ordinals)      263—264
Система обозначений максимальная (maximal system of notation)      265—266 270 271 285
Система обозначений рекурсивная (recursive system of notation)      284
Система обозначений рекурсивная по упорядочению (system of notation recursively related)      265—266 284
Система обозначений унивалентная (univalent system of notation)      265 271—272 284—285 558
Система обозначений универсальная (universal system of notation)      266—267 270;
Система обозначений, система (system of notation, system )      266—267 571
Система обозначений, система O (system of notation, system O)      268—271 273 284 285 508 512 571
Сколем      67 572
Скордев, Д.      362
Скотт      72
Слабая табличная сводимость (weak truth-table reducibility)      168 206—207
Слабо определенный функционал (weakly defined functional)      459
Случайная функция (random functional)      320
Сочленение (join)      112 217
Сочленение степеней (join of T-degrees)      218
Спектор      272 285 342 343 346 355 379 381 508 520 528 531 540 560 562 569 576
Спектр высказывания (spectrum of a sentence)      223—224
Спектр рекурсивно перечислимых множеств (spectrum of recursively enumerable)      159 160 203 315 321
Сплинтер (splinter)      136 321
Степени неразрешимости (degrees of unsolvability)      107 155—158 180 286 307 326 406—408 440;
Степени трудности (degrees of difficulty)      364 365 370 385
Степени трудности относительные (relative degrees of difficulty)      371
Степени трудности проблемы 1-сведения (degrees of difficulty of one-one reduction)      370
Степени трудности проблемы отделения (degrees of difficulty of separability)      370
Степени трудности проблемы перечисления (degrees of difficulty of enumerability)      368

1 2 3

Реклама

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

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

Valid HTML 4.01!

|

Valid CSS!

О проекте