Нетотальные степени перечислимости

• Автор: Солон, Борис Яковлевич
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2003
• Место защиты: Иваново
• Количество страниц: 154 с.

Введение

Основные определении н обзор результатов.

Пусть cj — {0,1,...} — множество натуральных чисел. Одноместная функция / : и> —» и называется алгоритмически вычислимой или вычислимой с помощью аффективной процедуры (в интуитивном смысле), если существует алгоритм, позволяющий по данному входу я получить выход /(г). Опуская слово ” алгоритмически”, мы получаем понятие вычислимой функции (computable function), если / - тотальная функция, и частично вычислимой (partial . 1 computable), если / — частичная функция.
Уточнения или, как принято говорить, формализации понятий алгоритма и вычислимой функции были сделаны в 30-е годы прошлого века К ли ни [23], Черчем [77], Тьюрингом [70], Геделем и другими. Как один из результатов - создание теории вычислимости и соответствующей терминологии, в которой термин "рекурсивный”, введенный Клини [22] для обозначения функций, вычислимых по Клини (recursive function), стал использоваться и для названия функций, вычислимых по Тьюрингу, и в случае других формализаций. Это привело к появлению ”Теории рекурсивных функций” (Recursive Function Theory). Различие в использовании терминов "вычислимый” и "рекурсивный” было стерто в монографии Роджерса [49] "Теория рекурсивных функций и эффективная вычислимость”. Как было сказано в предисловии "От редактора перевода” В.А. Успенским, в этой книге "систематически излагается общая теория рекурсивных функций, то есть функций, вычислимых посредством алгоритмов”. Термин ”рекрсивный” стал использоваться также и в смысле "разрешимый” (decidable), в результате множества, характеристическая функция которых рекурсивна (разрешимые множества), были названы рекурсивными, а множества, которые являются областями определения подходящих частичнорекурсивных функций, — рекурсивно перечислимыми (recursively enumerable).

1' В 1995 г. Роберт Соар предложил вернуться к исходной терминологии и

I использовать термин "вычислимый” в смысле Геделя и Тьюринга, а термин "рекурсивный" только для определений по рекурсии (то есть сузить понятие "рекурсивный” до его фактического смысла). Это предложение стало общепринятым и теперь название предмета из "Теории рекурсии” изменено на "Теория вычислимости”, "рекурсивные функции” (в широком смысле) называются "вычислимыми", "рекурсивно перечислимые множества” — "вычислимо пере-

числимыми" И Т.Д.

В диссертации нумерация определений, предложений, лемм и теорем сплошная внутри каждого параграфа или главы, (если она не разбита на параграфы). В введении номер утверждения состоит из одного числа. В главах I и II но-

мер состоит из трех чисел: "номер главы.номер параграфа.порядковый номер утверждения". В главах III -VI номер утверждения состоит из двух чисел: "номер параграфа, порядковый номер утверждения".
Приведем обозначения и терминологию, которые будут использованы в тексте диссертации. Многие из них такие же, как и в монографии [49]. О учетом общепринятого ныне предложения Со ара, пусть {Уп}п£ы и {Фп)п£ы - гелелева нумерация всех вычислимо перечислимых (в.п.) множеств и частично вычислимых (ч.в.) функций, ~ конечная вычислимая аппроксимация
вычислимо перечислимого множества УЛ. Как обычно, Д, — конечное множество с каноническим индексом « таким, что если = {*і,...,жп} и
*1 < ••• < жп, то « = 2*1 +••• + 2“’*, и £>о = 0, (к,1) - каиторовскнй номер упорядоченной пары (й, I). Если і — каиторовскнй номер пары (к, I), то (1)^ — к ■ и (і)г = I. Обозначим для множества В через (В)і = {я : Эи((я, и) Є В)}, через (ж, О) — {ж, и), где I) = £>и. Через А будем обозначать мощность множества А Сц то есть |Л| = Ко, если А — бесконечное множество, А - число элементов конечного множества А ф 0 я |0| = 0. Иногда будем писать |Л| = со, если А - бесконечное и |А| < оо, если А - конечное множество. Пусть, как обычно, К = {ж : х Є И'’«,} и К = ыК, Ко = {{ж, п) : ж Є И»}. Хорошо известно, что К вычислимо изоморфно К0 (и, следовательно, К з Ко).
Для функции а : ш —♦ и через 8 а будем обозначать область определения, ра - область значений и та = {(я, а(я)) : я Є 8 а) - график а. Тот факт, что я Є Да будем записывать как а(я) ], а я ^ 5а, как а(я) ]. Буквы /,д будем использовать только для обозначения тотальных функций, т.е. 8/ — 8д — и.
Обозначим для множества А через ■
если я Є А
если я ^ А — характеристическую и
если я 6 А
если я $. А — частичную характеристическую функции множества А. Множество А называется однозначным, если А = га для некоторой функции а.
В вычислениях, использующих дополнительную информацию, имеет большое значение способ, с помощью которого она становится доступной для вычислителя. Без учета временных ограничений таких принципиально различных способа два: через оракула, когда новая информация появляется на запрос немедленно, и через перечисление, когда новая информация постоянно генерируется и может быть поставлена на запрос только ее некоторая часть. Первая модель вычисления, основанная на оракулах, приводит х понятию Т-сводимости (сводимости по Тьюрингу) множеств, а вторая, основанная на перечислимости, приводит к е-сводимости (сводимости по перечислимости) множеств. Т~ сводимость и связанная с ней степенная структура изучаются, начиная с 1

хлЫ “ {

года, и имеют обширную и глубокую теорию, а е-сводимость, возникшая в 1955 году, привлекла активное внимание математиков лишь в последние десятилетие.
Напомним определение Фрндберга и Роджерса из [74], которое мы принимаем за основное. С интуитивной точки зрения, множество А сводится по перечислимости или с-сводитск к множеству В (символически, А <„ В), если существует равномерный алгоритм для получения некоторого перечисления элементов А из любого перечисления элементов В. Формально,
Определение 1.
А<а В -с=> ЗпУф е А ■«=>■ Зы[(ж, «> £ ХУп Л Ои С В]].
В $1 главы 1 дадим подробное обоснование данного формального определения. Обозначим через Фп(В) = {х : 3«((я, и) е Уп Л С В)}, тогда А <* В <=> Зп(Л = Фп(В)). Отображение ФЛ : 2" —» 2" называется оператором перечислеиия или е-оператором с индексом п (как и ХУп> определяющее Ф„). Хорошо известно, что е-операторы монотонны и непрерывны, т.е. для любого г» € у и любых А, В С ш
ЛСВ-» ФЛ(Л) С ФП(В) и
Уж[ж 6 Ф„(Л) —» (ЭВ — хонечное)[0 С Л А ж € ФЛ(В)]].
Пусть, как обычно, Л =е В <=>• Л <е В А В <* Л, 6е(А) = {В : В =е Л}-е-степень множества Л (для обозначения е-степеней будем также использовать малые жирные латинские буквы: например, а — де(А)) я де(А) < й„(В) <=> А <« В - частичное упорядочение е-степеней. Если е-степени а и Ъ несравнимы относительно <, то обозначим это через а| Ь, а< Ъ, если а< Ъ и а. Будем писать для функций а, Р а <е А или а <„ В, если та <е Л или та <„ т/3. Обозначим через Т>е множество е-степеней, упорядоченное отношением <, 2>е(< а) = {* € 9, : х < а}, [а, Ь]е = {х € Т>е : а < х < Ь}, (а, Ь)е = {х € Х>е : а < х < Ь}, Хорошо известно (см., например, [21]), что образует верхнюю полу решетку, не решетку с наименьшим элементом 0« = {У7п : я € у}, е-степени, содержащие графики тотальных функций, называются тотальными. Обозначим через Т частично упорядоченное множество тотальных е-степеней. Обозначения Т(< а) и Т(< а) используются в обычном смысле.
Термин нетотальная е-степень применим, таким образом, к степеням перечислимости, которые не содержат графиков ни одной тотальной функции. Как было показано Кейсом в [21], по любому перечислению любого множества Л, принадлежащего тотальной е-степени и только тотальной е-степени, можно эффективно получить некоторое фиксированнное перечисление элементов этого
однозначное множество. Так как А С £за+1, то т/ = ФП(Л) С Фп(£зп+г). В этом случае, в силу тотальности функции / должно выполняться равенство т/ = ФпС^Зп+Г)- Так как ^&Г+Г ~ вычислимое множество, то Ф» (£3*1+1) — вычислимо перечислимое множество и / — вычислимая функция.
Наконец докажем, что требования Уп удовлетворены для всех п 6 «. Рассмотрим множество Ф„(Л Ф А) и шаг Зп+З. Если на этом шаге выполнено условие (3), то Фп(А ф А) П Р ф 0, поэтому ФП(Л ф А) ф Р. Пусть условие (3) на этом шаге не выполняется, то есть
У17(1? П £3*1+2 — 9-+ Фп(^зп+2 и 17 ф Азп+2 и 17) П Р — 0).
Докажем, что в этом случае
Фп(Дзп+2 и £3*1+2 Ф Дз*1+2 и £3*1+2)
- конечное множество. Обозначим через О — Дзп+гО^зп+г * докажем сначала, что Фп(С ф С) П Р = 0. Предположим, что это неверно, то есть что Фп(^7 Ф С) П Р Ф 9, тогда существует конечное множество Р С С ф С, такое, что Фл(Р’) ПРф9. В этом случае существует конечное множество 17, такое, что
17 П £зп+2 “ 9 и
Р С Азп+г и 17 ф Дзп+2 и 17.
В качестве такого конечного множества 17 можно взять, например, О = Д П С. Из конструкции следует, ЧТО Лзп+2 п £з*1+2 = 0, поэтому 17 П £зп+2 = 0- Так как в этом случае
Ф*1(Р) С Ф„(Л8„+2 и 17 ф ^3л+2 и 17),
то Фп(Дз*1+2 и 17 ф Дзп+2 и 17) Г) Р ф 0, что противоречит предположению о невыполнении условия (3).
Итак,
Фп (Азп+2 и £3*1+2 Ф -Азп+г и ^3*1+2) П Р = 0.
Множества Дзп+2 * £3*1+2 являются конечными, следовательно, множество С® С вычислимо и Ф„(С ф С) вычислимо перечислимо. По условию Леммы Р -простое множество, поэтому множество Фп(С®С) должно быть конечным. Так как Л © Л С <7 ф Осталось заметить, что требования ЕСЕп, п € м и ф обеспечивают квазиминимальность е-степени ^е(Л), а требования Уп, п 6 ы обеспечивают то, что Р £е А Ф Л. Лемма полностью доказана.
Теорема 1.2.6. Существует квазлмипимальная е-степень Ле(Л), такая, что
ге(А) 2 МА).
Доказательство. Пусть Р - простое множество и <1е(Л) - квазиминималь-ная е-степень, построенная в ходе доказательства Леммы 1.2.5. Так как Р — вычислимо перечислимое множество, то Р ф А € 4е(А). Предположим, что Р Ф А Е с1т(А), тогда, в частности, Р ® А <т А, откуда следует, что Р <т А.