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

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

Авторизация

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

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

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

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

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

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

Аннотация:

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

Язык:

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

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

ed2k: ed2k stats

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

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

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

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

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

Теорема Поста (Post)      35 55
Теорема релятивизованная (relativi7ed)      42
Теорема Сакса (Sacks)      50 74
Теорема Спектора (Spector)      47
Теорема Фридберга (Friedberg)      44 55
Теорема Фридберга — Мучника (Friedberg — Muchnik)      61
Теория аксиоматизируемая (axiomati7able theory)      164
Теория вычислений (of computations)      12
Теория линейного порядка (of linear order)      181
Теория первого порядка чистая (pure quantification)      177
Теория рекурсия (recursion)      12
Теория слабая второго порядка (weak second-order)      167
Теория следования (of successor)      177
Теория степеней (of degrees)      32
Теория элементарная (elementary)      159
Теория элементарная F (of F)      162
Теория элементарная m-степеней (of m-degrees)      161
Теория элементарная T-степеней (of T-degrees)      161
Теория элементарная дистрибутивных решеток с относительными дополнениями (of relatively complemented distributive lattices)      162
Теория элементарная рекурсивно перечислимых множеств (of recursively enumerable sets)      110 113
Теория элементарная решеток (of lattices)      161
Тип изоморфизма рациональных чисел (type of isomorphism of rational numbers)      164
Тогда и только тогда (if and only if)      11
Требование активного (active requirement)      58 62 86 91
Требование внимания (requirement of attention)      157
Требование временное (temporary)      58 62 87 92
Требование для A (for A)      86
Требование для B (for B)      86
Требование неактивное (inactive)      58 62 86 91
Требование неаффективное (ineffective)      86
Требование несущественное (inessential)      87
Требование постоянное (permanent)      58 62 87 92
Требование с индексом (with index)      91
Требование существенное (essential)      87 92
Требование эффективное (effective)      86 91
Тьюринг      166 168 178
Убивать (kill)      92
Уделение внимания (receiving of altention)      157
Умножение (multiplication function)      14
Условия (conditions)      40 43 45 56 61 85 91
Факторалгебра (quotient algebra)      164
Фейнер      6 163 179 180 183
Фильтр (filter)      164
Фильтр типа $\Pi^1_1$ ( $\Pi^1_1$ )      164
Форма пренексная нормальная (prenex normal form)      120 170
Фридберг      9 44 55 61 100 102 104 108 111 122 151 160 162

Функции несовместные (incompatible functions)      39
Функции совместные (compatible functions)      39
Функция $\oslash^{(\omega)}$ -рекурсивная ( $\oslash^{(\omega)}$ -recursive)      166
Функция (function)      11 13 109
Функция длины (length)      14
Функция из … в … (from … to …)      13
Функция конечная (finite)      23
Функция нерекурсивная (non-recursive)      19
Функция от n аргументов (of n arguments)      13
Функция почти константа (almost constant)      69
Функция рекурсивная (recursive)      13
Функция сдерживающая (restricting)      67
Функция спаривающая стандартная (standard pairing)      177
Функция тождественная (identity)      14
Функция характеристическая (characteristic)      165
Функция частичная (partial)      19
Функция частичная всюду определенная (total)      19
Функция частичная рекурсивная (recursive)      19
Функция частичная рекурсивная X-чэстично рекурсивная (X-partial recursive)      166
Функция частичная рекурсивная в … (in …)      21 24
Функция частичная рекурсивная относительно …(relative to...)      21
Ханф      164 177 179
Хьюджил      161 181 184
ЦЕПОЧКА (STRING)      23 47 132
Цепочка, расположенная на дереве (on tree)      47
Цепочка, расщепляющаяся на дереве (splitting on tree)      47
Число n-задержанное (n-held)      70
Число действительное (real number)      12
Число задержанное (held)      70
Число накрывающее (covering)      110 122
Число натуральное (natural)      11 109
Число последовательностное (sequence number)      165
Число разделяющее (partition)      126
Число рациональное (rational)      183
Число, используемое в вычислении (used in the computation)      23
Число, используемое в вычислении отрицательно (used negative in the computation)      57
Шенфилд      7 74 98—100 108
Эквивалентность (equivalence to)      110
Элемент ключевой (key element)      86
Элемент наименьший (least)      133
Элемент структуры (member of structure)      164
Элемент числового дерева (member of a number tree)      132
Элемент, содержащий ординал (containing the ordinal)      49
Элиминация кванторов (elimination of quantifiers)      121 177
Эрастосфен      14
Язык слабый второго порядка (weak second-order language)      166
Язык формальный (formal language)      113

1 2

О проекте