Шенфилд Дж. — Степени неразрешимости :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Шенфилд Дж. — Степени неразрешимости

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

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

Название: Степени неразрешимости

Автор: Шенфилд Дж.

Аннотация:

Предлагаемая вниманию читателей книга Дж. Шенфилда посвящена изложению основных результатов о степенях неразрешимости (тьюринговых степенях). Эти результаты традиционно считаются трудными, так как в их доказательствах используются различные формы так называемого «метода приоритета». Автор книги поставил перед собой цель изложить материал в максимально простой и интуитивно оправданной форме. И нужно сказать, что это ему в основном удалось.

Язык:

Рубрика: Математика/Алгебра/Математическая логика/

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

ed2k: ed2k stats

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

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

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

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

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

$\exists\forall\exists$ -булева алгебра ( $\exists\forall\exists$ -Boolean algebra)      112 138 178
$\exists\forall\exists$ -отношение ( $\exists\forall\exists$ -relation)      111
$\exists\forall\exists$ -решетка ( $\exists\forall\exists$ -lattice)      138
$\exists\forall\exists$ -решетка дистрибутивная (distributive)      159
(I, J)-строка ((I, J)-row)      91
A-отношение (A-relatlon)      115
A-часть (A-part)      87
A-число (A-number)      62
AB-отношение (AB-relation)      116
B-отношение (B-relation)      115
B-отношение, соответствующее A-отношению (corresponding in the A-relation)      116
B-часть (B-part)      87
B-число (B-number)      62
e-высота (e-state)      104
He (not)      11 110
I-расщепление (I-splitting)      47
I-расщепление на дереве (on a tree)      47
m-сводимость (many-one reducibility)      36
n-высота на шаге (n-state of step)      142
n-держит (n-hold)      70
n-ка упорядоченная (ordered n-tuple)      11
n-требование (n-requirement)      57
n-требование с аргументом (with argument)      62
n-цепочка (n-string)      69
T-степень (T-degree)      161 180
U-квантор (U-quantifier)      172
U-форма (U-form)      172
Алгебра булева (Boolean algebra)      163
Алгебра булева подмножеств (of subsets)      164
Алгебра булева, образованная главным идеалом (formed by the principal ideal)      165
Алгебра булева, образованная главным фильтром (filter)      165
Алгебра Линденбаума (Lindenbaum algebra)      164 176 177
Алгоритм (algorithm)      18
Алгоритм для функции (for function)      19 21
Алгоритм из … в … (from … to…)      18
Алгоритм Крайзела (Kreisel)      172
Алгоритм обобщенный (extended)      21
Алгоритм Тарского — Куратовского (Tarski — Kuratowski)      168 170 181 182
Аппроксимация (appoximation)      20 22
Аргумент требования (argument of requirement)      86
Базис упорядоченный (ordered basis)      165
Влечет (implies)      11
Вход (input)      18
Выход (output)      18
Вычисление (computation)      19 22 166
Вычисление с оракулом (using an oracle)      21 22 167
Вычисление согласно алгоритму (according to algorithm)      19
Гипотеза сильной однородности (the strong homogeneity conjecture)      180
Гипотеза Ханфа (Hanf conjecture)      164 177
Грань наибольшая нижняя (greatest lower bound)      30
Грань наименьшая верхняя (least upper bound)      30
График (graph)      26
Девис      109 162 166 179
Деккер      54 98 100—102 108
Дерево (tree)      47
Дерево I-расщепленное (I-splitting)      48
Дерево числовое (number)      132
Джокуш      162 180
Диаграмма коммутативная (commutative diaerani)      16
Дизъюнкция (disjunction)      110 165
Доминанта (dominant)      65
Доминирование (dominantion)      65 103
Дополнение (complement)      15 109 163 164
Ейтс      6 10 65 80 85 97 108 НО 111 122 126 162 183
Ершов, ЮЛ.      6 162
Захватчик (holder)      71
Значение последовательности (value of sequence)      12
Значение требования (requirement)      86
И (and)      11 110
Идеал простой (prime ideal)      164
Иерархия предикатов (predicate hierarchy)      170
Изоморфизм (isomorphism)      15 180
Изоморфизм алгебраический (algebraic)      164
Или (or)      11 110
Индекс (index)      26
Индекс в... (in...)      28
Интервал (interval)      164
Иптерпретация семантическая (semantic interpretation)      113
Исчисление высказываний (ргороsitional calculus)      177
Исчисление предикатов узкое (lower predicate calculus)      109
Квантор (quantifier)      11 110 165
Квантор общности (universal)      11 110 165
Квантор существования (existential)      11 110 165
Класс (class)      11
Класс алгоритмов (of algorithms)      18
Класс конечных подклассов (of finite subclasses)      13
Класс конечных последовательностей (of finite sequences)      13
Класс натуральных чисел (of natural numbers)      11
Класс пустой (empty)      11
Клини      7 39 42 84 108
Композиция функций (composition of functions)      14
Конструкция F-поддерживающаяся (F-supported)      68
Конструкция F-сдерживающаяся (F-restricted)      68
Конструкция бесконечных нарушений (infinite injury construction)      75
Конъюнкция (conjuction)      110 165
Крайзел      172
Куратовский      168 170 181 182
Лахлан      6 9 10 90 94 109 164 178 179
Лемма о модуле (modulus lemma)      27
Лемма о пределе (limit)      31
Лемма Шенфилда (Shoenfield)      74
Линденбаум      164 176 177
Майхилл      110 111 125 132 162
Манастер      162
Мартин      65 103 107 108 112 148 155 162
Матрица бесконечная (infinite square array)      18
Матрица рекурсивная (recursive matrix)      166 170
Машина вычислительная (computing machine)      18
Машина Тьюринга (Turing)      166 168
Метод вычислений (method of computation)      18
Метод приоритета (priority method)      55
Множество (set)      11 13
Множество I-минимальное (I-minimal)      47
Множество r-максимальное (r-maximal)      112 156
Множество X-рекурсивно перечислимое (X-recursively enumerable)      164
Множество арифметическое (arithmetic)      161
Множество в … (in …)      13
Множество гипергипериммунное (hyperhyperimmune)      128
Множество гипергиперпростое (hyperhypersimple)      102 107 122
Множество гиперпростое (hypersimple)      100 107
Множество дискретное (successor-chain)      181
Множество замкнутое (closed)      77
Множество индексное (Index)      80
Множество квазикреативное (quasicrelative)      98 99
Множество кобесконечное (coinfinlte)      39 109
Множество коконечное (cofinite)      38 109
Множество креативное (creative)      98
Множество кусочно рекурсивное (plecewise recursive)      74
Множество максимальное (maximal)      64 102 122
Множество натуральных чисел (of natural numbers)      109 164
Множество одноэлементное (singleton)      178
Множество описаний (set of descriptions)      17
Множество основное булевой алгебры (universe of Boolean algebra)      163
Множество полное рекурсивно перечислимое (complete recursively enumerable set)      36
Множество полное типа $\Sigma_n, \Pi_n$ (complete $\Sigma_n, \Pi_n$ )      36
Множество полукреативное (semlcreative)      98
Множество полупродуктивное (semlproductive)      98
Множество простое (simple)      53 100
Множество пустое (empty)      109 164
Множество рекурсивно перечислимое (recursively enumerable)      24 97
Множество рекурсивно перечислимое в... (in …)      28 30
Множество рекурсивно перечислимое с ретрассируемым дополнением (whose complement is retraceable)      107
Множество рекурсивное (recursive)      14
Множество сильно простое (strongly simple)      55
Множество типа $\Sigma_n [a], \Pi_n [a]$ ( $\Sigma_n [a], \Pi_n [a]$ )      80
Множество типа $\Sigma_n, \Pi_n$ ( $\Sigma_n, \Pi_n$ )      32
Множество типа $\Sigma_n, \Pi_n$ в ...(in…)      39
Множество «большое» («large»)      53 64 73
Множество, имеющее мало рекурсивно перечислимых надмножеств (having few recursively enumerable supersets)      64
Множество, расположенное на дереве (on a tree)      47

Модель нестандартная (nonstandard model)      163
Модель теории множеств (model of set theory)      163
Модуль (modulus)      27
Мостовский      163 179
Мучник, А.А.      55 61 100 408
Нероуд      179
Номер гёделев (Godel number)      114 116 166
Нуль булевой алгебры (zero of Boolean algebra)      170
Нумерация гёделева (Godel numbering)      113
Нумерация стандартная (standard)      161
Обеспечение условия (insuring of a condition)      40
Область значений (range)      11
Область определения (domain)      11
Обращение отображения (inverse mapping)      11
Объединение (union)      14 163 164
Объект конечный (finite object)      12
Овингс      160
Описание конечного объекта (description of finite object)      17
Оракул (oracle)      21 22
Ординал (ordinal)      148
Ординал, вложимый в решетку (imbeddable in lattice)      148
Отношение истинности (satisfaction relation)      166
Отношение от n аргументов (of n arguments)      13
Отношение элементарное (elementary)      113
Отображение (mapping)      11
Отображение 1—1 (one-one mapping)      11
Отрицание (negation)      165
Пара рекурсивно перечислимых рекурсивно неотделимых множеств (pair of recursively enumerable recursively Inseparable sets)      163
ПЕРЕСЕЧЕНИЕ (INTERSECTION)      14 163 164
Перечисление $N\times N$ (of $N\times N$ )      18
Перечисление (listing)      16
Перечисление рекурсивной всех рекурсивно перечислимых множеств (recursive enumeration of all recursively enumerable sets)      132 138 141
Повреждение (injure)      57
Поддерево (subtree)      47
Поддерево I-расщепленное (I-splitting)      49
Подкласс конечный (finite subclass)      13
Подмножество главное (major subset)      152
Подмножество густое (thick)      74
Подпредикат (subpredicate)      120
Полурешетка верхняя (upper semilattice)      180
Порядок n-ки (order of n-tuple)      128
Порядок лексикографический (lexicographical order)      166
Порядок линейный (linear ordering)      164 180
Порядок частичный (partial ordering)      180
Последовательность (sequence)      11
Последовательность бесконечная (infinite)      11
Последовательность конечная (finite)      12
Последовательность рекурсивная (recursive)      27
Последовательность рекурсивно перечислимая (recursively enumerable)      97
Последовательность рекурсивно перечислимая сильно (strongly)      97
Последовательность степеней возрастающая (ascending sequence of degrees)      42
Пост      35 36 39 42 53—55 64 73 97 100 102 108 162
Предел (limit)      27
Предикат (predicate)      113
Предикат, определяющий отношение (defining a relation)      113
Предложение (sentence)      113
Принцип использования (the Use Principle)      23
Проблема Поста (Post’s problem)      53 55 73 100
Проблема разрешения (decision)      114
Проблема разрешения разрешимая (solvable)      114
Проблема разрешения сводимая (reducible)      114
Проекция (projection)      14
Произведение прямое (direct product)      164
Производная (derivative)      169 178
Пространства изоморфные (isomorphic spaces)      15
Пространство (space)      12
Пространство цепочек (of strings)      47
Процедура разрешающая (decision procedure)      109
Рабин      163 179
Равенство частичных выражений (equality between partial expressions)      19
Разбиение (splitting)      128
Разложение каноническое (factorization)      17 98
Разность (difference)      14
Райс      108
Расширение (extension)      23
Расщепление (splitting)      47
Результат иычислсиин (output of computation)      167
Рекурсивность относительная (relative recursiveness)      20 166
Релятивизация (relativization)      22 41
Решение вопроса (decision of a question)      45
Решетка X-рекурсивно перечислимых множеств (of X-rccursivcly enumerable sets)      164
Решетка замкнутая (closed lattice)      115
Решетка классов эквивалентности (of equavalence classes)      111 115
Решетка подмножеств (of subsets)      115
Решетка рекурсивно перечислимых множеств (of recursively enumerable sets)      113
Решетка рекурсивно перечислимых множеств по модулю простых множеств (modulo simple sets)      161
Решетка рекурсивно перечислимых надмножеств (supersets)      111
Решетка рекурсивных множеств (of recurvise sets)      121
Решето Эратосфена (sieve of Eratosthanes)      14
Робинсон, А.      109 113 162
Робинсон, Р.      112 128 148 156
Роджерс      10 82 109 166 179 180 184
Ряд бесконечный (infinite series)      14
Сакс      10 50 60 74 85 103 107 108
Сводимость (reducibility)      36 37
Связка (connective)      11
Сегмент (segment)      140 180
Сегмент начальный (initial)      180
Сегмент начальный степеней (of degrees)      161
Селектор (selector)      25
Сикорский      163 179
Символ индивидуальный (object symbol)      113
Скачок степени (jump of degree)      31 164 180
Скачок функции (of function)      28
Следует (Implies)      110
Сложение (addition function)      14
Соответствие (correspondence)      146
Союзник (associate)      139
Спектор, С.      42 47 161
Степени несравнимые (incomparable degrees)      39
Степень (degree)      29 180
Степень аналитическая (analytic)      180
Степень ветвящаяся (branching)      85
Степень гипергиперпростого множества (of hyperhypersimple set)      103 148
Степень максимального множества (of maximal set)      103
Степень минимальная (minimal)      46
Степень наименьшая (smallest)      30
Степень рекурсивно перечислимая (recursively enumerable)      31 98
Степень рекурсивно перечислимая в ... (in …)      30
Столбец (column)      18
Строка (row)      18
Структура (structure)      163 164
Структура X-рекурсивная (X-recursive)      176
Структура рекурсивная (recursive)      163 180
Структура рекурсивно перечислимая (recursively enumerable)      176 180
Структура, представимая X-рекурсивно (X-recursively presentable)      176 181
Структура, представимая рекурсивно (recursively presentable)      163 180
Структура, представимая рекурсивно перечислимая (recursively enumerable presentable)      176 180
Тарский      163 168 170 179 181 182
Тенненбаум      103 107 108 163 179
Теорема Деккера (Dekker theorem)      54
Теорема Ейтса (Yates)      85 110 126
Теорема Клини — Поста (Kleene — lost)      39
Теорема Клини — Поста — Спектора (Kleene — Post — Spector)      42
Теорема Лахлана (Lachlan)      90 139 178
Теорема Мартина (Martin)      65
Теорема Мучника (Muchnik)      61
Теорема о графике (graph)      26
Теорема о дополнении (complementation)      26
Теорема о неподвижной точке (fixed point)      84
Теорема о перечислении (listing)      26
Теорема о разложении (splitting)      66
Теорема о рекурсии (recursion)      84 124
Теорема о селекторе (selection)      25
Теорема об иерархии сильная (strong hierarchy)      167
Теорема об изоморфизме (isomorphism)      16
Теорема об индексном множестве (Index set)      80
Теорема основная Лахлана (main of I achlan)      122
Теорема параметризации (parameter)      26
Теорема плотности (density)      85

1 2

О проекте