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

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

Авторизация

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

Красота

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

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

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

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

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

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

Аннотация:

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

Язык:

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

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

ed2k: ed2k stats

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

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

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

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

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

Степени трудности проблемы разрешения (degrees of difficulty of solvability)      368 385
Степени трудности проблемы сведения (degrees of difficulty of reducibility)      372
Стоуна теорема о представлении (Stone representation theorem)      288 316
Строгая гипергипериммунность (strong hyperhyperimmunity)      312 321 322
Строгая гипериммунность (strong hyperimmunity)      312 322
Строго гиперпростое множество (strongly hypersimple set)      322 324]
Строго определенный функционал (strongly defined functional)      459
Стургис      36
Субрекурсивность (subrecursiveness)      68 69 75
Судзуки      532 552 553 555
Суслин, М.      581
Сходство (resemblance)      77 80
Счетная модель (denumerable model)      501 502
Табличная сводимость, полные множества и степени (truth-table reducibility, complete sets, and degrees)      см. «tt-сводимость»
Табличное условие (truth-table condition)      см. «tt-условие»
Танака      576
Тарский      56 72 130 249 263 281 284 398
Тарского — Куратовского алгоритм (Tarski — Kuratowski algorithm)      394—400 415 417 425 433 447 483 484
Тарского — Куратовского алгоритм, пример      419
Творческие множества (creative sets)      114—116 132 140—143 158—161 293 317 425 428;
Тенненбаум (Tennenbaum, S.)      164 204 206 207 227 323
Теорема выбора (selection theorem)      101 517 521
Теорема о веере (fan theorem)      205
Теорема о неподвижной точке (fixed-point theorem)      232
Теорема о нумерации (enumeration theorem)      41 94
Теорема о парной рекурсии (double recursion theorem)      246
Теорема о простых числах (prime-number theorem)      414
Теорема о рекурсии (recursion theorem)      232—236 509 518
Теорема о рекурсии вторая (second recursion theorem)      252
Теорема о рекурсии первая (first recursion theorem)      252
Теорема о рекурсии сильная (strong recursion theorem)      253
Теорема о рекурсии слабая (weak recursion theorem)      253
Теорема о рекурсии, аспекты самовыразимости или обращения к самому себе (selfreferential aspects of recursion theorem)      256—263
Теорема о рекурсии, другие формы (other forms of recursion theorem)      249—256
Теорема о рекурсии, применение (applications recursion theorem)      236—248
Теорема об ограниченности (boundedness theorem)      511 534
Теоремы о неполноте (incompleteness theorems)      29 48 60—61 124;
Теоремы об иерархии (hierarchy theorems)      391 405 425 435 439 453 456 472 485
Теоремы об иерархии обобщенные (generalized hierarchy theorems)      456—458
Теоретико-множественная арифметика (set-theory arithmetic)      131—133 139 412
Теоретико-множественный анализ (set-theory analysis)      500
Теоретико-порядковое свойство (order-theoretic property)      335
Теоретико-решеточное свойство (lattice-theoretic property)      291—293 308 315 317 319
Теоретико-решеточное свойство элементарное (elementary lattice-theoretic property)      292
Теории множеств высказывания, выразимые аналитически (analytically expressible sentences of set theory)      500
Теория (theory)      128—129
Теория конечно аксиоматизируемая (finitely axiomatizable theory)      225
Теория меры, вероятностная интерпретация (measure theory, probabilistic interpretation)      349
Теория меры, методы (measure theory, methods of theory)      348—350 382 383
Теория множеств (set theory)      412—415
Теория множеств Гёделя — Бернайса (set theory of Godel — Bernays), пример      515
Теория множеств Цермело — Френкеля (set theory of Zermelo — Fraenkel)      239—240 276—277 412—415
Теория первого порядка (first-order theory)      222
Теория первого порядка произвольной рекурсивно перечислимой степени (first-order theory of any recursively enumerable degree)      222—226
Теория первого порядка существенно неразрешимая (essentially undecidable first-order theory)      226
Теория первого порядка, пример      292
Титгемейер      379
Томасон      380
Топология (topology)      279 382 434 448 449
Топология и иерархии (topology and hierarchies), пример      417
Топология и операторы (topology and operators)      202
Трансфинитная индукция (transfinite induction)      278 283
Трахтенброт, Б.А.      440
Тьюринг      7 29 36—37 45 48 56
Тьюринга машина (Turing machine)      30—34 48 63 64 65 66 243—245 401
Тьюринга машина лента (Turing machine, tape)      30
Тьюринга машина с вспомогательными лентами (Turing machine with auxiliary tapes)      170
Тьюринга машина с оракулом (Turing machine with oracle)      169—170
Тьюринга машина условие совместимости (Turing machine, consistency restriction)      31
Тьюрингова сводимость, полные множества и степени (Turing reducibility, complete set, and degree)      см. «T-сводимость»
Уайтхед      60 144
Уиман      166
Универсальная машина (universal machine)      42
Универсальная функция (universal function)      41 63 77—79 246—247
Униформизация (uniformization)      100 550
Условная вероятность (conditional probability)      349
Успенский, В.А.      67 158 192
Факторрешетка (quotient lattice)      161 288—291 371 385

Фейнер      335
Ферма большая теорема (Fermat’s last theorem)      414
Феферман      72 223 262 428 521 544 578
Фибоначчи ряд (Fibonacci sequence)      22 215
Фильтр (filter)      288
Фишер      72 104 154 157 160 162
фон Нейман      243
Формы (forms)      390
Фреге      60
Френкель      276
Фридберг      62 188 189 207 212 232 293 294 300 333 341 373 464 469
Функционал (functional)      444 459—471
Функционал, приложения (applications of functional)      470
Функционал, пример      429 479
Функциональное дерево (function tree)      205 449 502
Функциональный оператор (functional operator)      193—202
Функция (partial function)      12
Функция k множественных и l числовых переменных (function of k set variables and l number variables)      429
Функция k функциональных и l числовых переменных (function of k function variables and l number variables)      444
Функция всюду определенная (total function)      13
Функция композиция (function, composition)      14
Функция не определена (function undefined)      13
Функция определена (function defined)      13
Функция пересчета пар (pairing function)      89
Функция расходится (divergent function)      13
Функция рекурсивная по Эрбрану (Herbrand-recursive function)      60 280
Функция сходится (convergent function)      13
Халмош      349
Характеристическая функция (characteristic function)      13
Характеристический индекс (characteristic index)      97—98 394
Хенкин      426
Хоудз      477 517
Хупер      205
Центр множества (center of a set)      159 165
Цермело      276
Цилиндр и цилиндрификация (cylinder and cylindrification)      121—122 141 142 158 159 163 165 166
Цорна лемма (Zorn’s lemma)      317
Частичное упорядочение (partial ordering)      286
Частичное упорядочение с условием минимальности (partial ordering well-founded)      509
Частичнорекурсивна в (partial recursive in)      193
Частичнорекурсивные функции (partial recursive functions)      36—37 46 58—60
Частичнорекурсивные функции k множественных и l числовых переменных (partial recursive functions of k set variables and l number variables)      429
Частичнорекурсивные функции k функциональных и l числовых переменных (partial recursive functions of k function variables and l number variables)      444 462
Частичнорекурсивные функции и $\mu$ -оператор (partial recursive functions and the mu operator)      см. « $\mu$ -оператор»
Частичнорекурсивные функции релятивизованные (partial recursive functions relativized)      173
Частичнорекурсивные функции, продолжение (extension of partial recursive functions)      58
Частичнорекурсивные функционалы (partial recursive functionals)      459 463 474
Частичнорекурсивный оператор (partial recursive operator)      194—202 208 279—280 460
Частичные степени (partial degrees)      193 359—363 369
Частичные степени тотальные (total partial degrees)      360 361;
Человеческое мышление, его границы (human mind, limitations of)      414 491
Чёрч      7 13 29 36 56 61 263 426
Чёрча тезис (Church’s thesis)      38—39 40 42 43 71 101 520 521
Чёрча тезис относительный (Church’s thesis relativized)      171
Чёрча теорема (Church’s theorem)      129
Число (number)      11
Шапиро      105 208 416 423
Шепердсон      36 253 254 280 362 460
Шёнфильд      126 165 166 219 220 225 276 330 334 342 344 345 378 379 422 428 442 443 464 475 528 569 582
Шёнфильд гипотеза (Shoenfield’s conjecture)      219—220 229 307
Шифр (encoder)      247
Шмульян      48 127 246 277
Экстенсиональность (extensionality)      25—27
Элементарная арифметика (elementary arithmetic)      129 222 261—263 400 408 434 448 498
Элементарная теория действительных чисел (elementary real number theory)      497
Элементарная теория чисел (elementary number theory)      130
Элементарный анализ (elementary analysis)      490 493—498
Элиминирование описаний (eliminating descriptions), пример      496
Эндертон      509 559 565 569 581 583
Эратосфена решето (Eratosthenes’ sieve)      18
Эрбран      60 280
Эталонное множество (reference set)      417 418
Эффективная операция (effective operation)      253 460 463—465
Эффективно неотделимые множества (effectively inseparable sets)      114 126—127
Эффективно простые множества (effectively simple sets)      166
Юллиан      136 319
Юллиана пример      296
Янг      136 155 157 159 166 230 309 321 322 324
Ячейка машинной ленты (cell on machine tape)      30

1 2 3

Реклама

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

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

Valid HTML 4.01!

|

Valid CSS!

О проекте