|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Роджерс Х. — Теория рекурсивных функций и эффективная вычислимость |
|
|
|
| Предметный указатель |
Степени трудности проблемы разрешения (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
Частичнорекурсивные функции и  -оператор (partial recursive functions and the mu operator) см. «-оператор»
Частичнорекурсивные функции релятивизованные (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
|
|
|
| Реклама |
|
|
|
|
|
О проекте