Оглавление
Введение. 3
Предварительные сведения....................... 14
1 Автоустойчивость гиперарифметических моделей. 30
1.1 Свягзь автоустойчивости и ранга Скотта....... 30
1.2 Автоустойчивость булевых алгебр.............. 38
2 Е- определимость в наследственно конечных надстройках. 53
2.1 Однозначность и автоустойчивость.............. 53
2.2 Определимость линейных порядков над булевыми
алгебрами и булевых алгебр над линейными порядками. 59
Введение
Работа посвящена обобщённой вычислимости моделей, а именно, их представимости в допустимых множествах: А}- конст-руктивизируемости и II-определимости и существованию различных неэквивалентных эффективных представлений модели (в смысле обобщённой вычислимости).
Существуют различные подходы к обобщению понятия вычислимости. Одни возникли из попыток решать алгоритмические проблемы, относящиеся к объектам, отличным от натуральных чисел (ординалы, вещественные числа и т.д.) Другие — из построений более сложных машин Тьюринга или вычислений при условии возможности использовать информацию о принадлежности числа определенному множеству (вычисления на обобщенных машинах, вычисления с оракулом). В данной работе рассматривается два подхода к обощению
3
понятия вычислимости (оба. в конечном итоге, приводят к рассмотрению допустимых множеств).
Допустимые множества были введены Кринке [19] и Пла-теком |20]. Они перенесли обычную теорию рекурсии на ординалы, меньшие некоторого допустимого ординала. Первоначально допустимые ординалы были определены в терминах теории рекурсии, изложенной в стиле исчисления равенств Эрбрана-Гёделя. Позднее условия допустимости ординала были преобразованы в систему аксиом Крипке- Платека (КР), и произошёл переход от допустимых ординалов к допустимым множествам.
Результаты о том, что:
(a) наименьшее нетривиальное допустимое множество есть НК Р(ш) = Ьшск , то есть множество всех подмножеств, конст-руируемых до уровня ординала Чёрча-Клини (наименьший нерекурсивный ординал) серк, и
(b) а С о; является гиперарифмстичсским тогда и только тогда, когда а 6 НК Р(со')
были получены Крипке и Платеком. Таким образом, существует нетривиальная связь между гипсрарифметической вычислимостью и вычислимостью в допустимом множестве НКР(ш)
4
Клини и Чёрч являются создателями общей теории систем обозначений для ординалов. Определение ниже принадлежит Клини.
ОПРЕДЕЛЕНИЕ 1 Система обозначений 5 есть отображение множества натуральных чисел на отрезок ординальных чисел, удовлетворяющее условиям:
(і) существует частичнорекурсивная функция к$ такая, что
і/5(х) = 0 -¥ к3(х) = О
нз(х) есть предельный ординал —► кя(х) = 2,
(гг) существует частичнорекурсивная функция р$ такая, что
^(х) есть последователь —> (рб{х) определена &
М*) = Ырз(х)) + 1),
(пі) существует частичнорекурсивпая функция ^ такая, что
и$(х) есть предельный ординал -» (^5 (ж) определена &;
{^5(^5(*) (п))К£=о естъ возрастающая последовательность, имеющая дз{х) своим пределом).
5
В [11| определяется универсальная (клиниевская) система обозначений О вместе с порядком <<?.
Определение по индукции:
О получает обозначение 1,
предположим, что все ординалы меньше 7 получили обозначения и что упорядочение <0 определено на этих обозначениях.
(\) если 7 = в + 1, то для каждого х такого, что (3 имеет х в качестве обозначения. 7 получает обозначение 2х, и пары (г, 2*) добавляются к <о для всех г таких, что г = х или (г, х) уже лежит в <о ■
(11) сети 7 — предельный ординал,то для каждого у такого, что
{^у(п)}~=0 “ СУТЬ обозначения возрастающей последовательности ординалов с пределом 7 и такой, что
(V*)(УУ)(г < 3 -> (^у(г'),^У0')> уже принадлежат <0),
7 получает 3*5У в качестве обозначения, и (,г,3*5у) добавляется к <(9 для всех 2, для которых су шествует п такое, что (г, <Ру(п)) уже лежит в <о •
Тьюринг обобщил понятие вычислимости [23|, введя понятие оракула. Из сравнения различных оракулов возникла теория степеней неразрешимости и строились различные ие-
б
- Київ+380960830922