Математическая энциклопедия - рекурсивная теория множеств

раздел тео-рии рекурсивных функций, в к-ром рассматриваются и классифицируются подмножества натуральных чисел с алгоритмич. точки зрения, а также исследуются структуры, возникающие в результате такой классификации. Для каждого множества А, к-рое является подмножеством множества всех натуральных чисел N, можно сформулировать следующую п р о б л е м у р а з р еш и м о с т и: существует ли алгоритм, позволяющий для любого ответить на вопрос о принадлежности x к A?

Математическая постановка проблем такого рода, как и развитие Р. т. м., стала возможна лишь в 40-х гг. 20 в. после успешной формализации интуитивного понятия (алгоритмически) вычислимой функции. Области значений таких функций образуют семейство р е к у рс и в н о п е р е ч и с л и м ы х м н о ж е с т в (р. п. м.). Множества, для к-рых сформулированная выше проблема разрешима, наз. р е к у р с и в н ы м и. Точнее, Арекурсивно тогда и только тогда, когда Аи оба являются р. п. м. Первыми примерами нерекурсивных р. п. м. оказались т. н. креативные (творческие) множества. Именно, р. п. м. Kназ. к р е а т и в н ы м, если существует вычислимая функция, к-рая по номеру любого р. п. м. А, не пересекающегося с K, выдает число, принадлежащее . Одновременно с креативными множествами были обнаружены и другие нерекурсивные р. п. м., в частности простые. Р. п. м. наз. п р о с т ы м, если оно имеет бесконечное дополнение, к-рое не содержит бесконечных р. п. м. Таким образом, уже для р. п. м. возникает тонкая проблема классификации их проблем разрешимости. Одним из инструментов для такой классификации служит понятие с в о д и м о с т и. На интуитивном уровне множество Ас в о д и м о к множеству В, если существует алгоритм, к-рый решал бы проблему вхождения элементов для множества А при условии, что есть возможность по мере надобности пользоваться информацией о принадлежности тех или иных натуральных чисел множеству В. В этом случае Аоказывается в определенном смысле "рекурсивным" относительно В, а обычные рекурсивные множества "рекурсивными" относительно любого множества. Такая сводимость в самом общем виде (точная формулировка к-рой достаточно сложна) наз. т ь ю р и н г о в о и, или Т- сводимостью. Накладывая те или иные ограничения на алгоритм, участвующий в понятии сводимости, приходят к определению других сводимостей, напр. 1-, т-, btt- или tt -сводимости. В частности, А m -с в о д и м о к В, если существует всюду определенная вычислимая функция f такая, что для всех хиз N

Если f можно выбрать разнозначной, то говорят, что А1-с в о д и м о к В.

Обобщением m-сводимости является т а б л и ч н а я (tt-).сводимость. Множество А tt -сводимо к множеству В, если существует алгоритм, к-рый для каждого хдает набор чисел и булеву функцию , причем

где c(t)=1, если , и c(t)=0 в противном случае. Если Аможно таблично свести к Втак, что n(х)будет ограничено нек-рой константой, то говорят, что Ао г р а н ич е н н о т а б л и ч н о (btt- )с в о д и т с я к В.

Пусть r нек-рая сводимость. Пишут , если множество А r -сводимо к В. Отношение должно быть предпорядком. Если положить

то будет отношением эквивалентности, отдельный класс к-рой наз. r-с т е п е н ь ю (и рекурсивно перечислимой r-степенью, если этот класс содержит р. п. м.). Тьюринговы степени известны в литературе и как с т е п е н и н е р а з р е ш и м о с т и. Отношение порождает частичное упорядочение всех r-степеней. Сводимость r' слабее, чем r, если влечет Частично упорядоченные множества r-степеней для т- и более слабых сводимостей образуют верхние полурешетки (что неверно для 1-степеней), имеющие наименьший элемент 0-r-степень рекурсивных множеств. Если ограничиться изучением только рекурсивно перечислимых r-степеней, то они имеют также и наибольший элемент 1, к-рый наз. п о л н о й r-с т е п е н ь ю. Р. п. м., содержащиеся в полной r-степени, наз. r-п о л н ы м и. М и н и м а л ь н ы м и r-степенями наз. такие, к-рые имеют лишь единственную строго меньшую r-степепь, а именно 0.

После определения той или иной сводимости ее изучение развивается в основном в двух направлениях. Первое связано с вопросами описания верхней полурешетки степеней относительно введенной сводимости. Известным примером проблемы такого типа явилась п р о б л е м а П о с т а [1]: верно ли, что все рекурсивно перечислимые нерекурсивные множества имеют одну и ту же степень неразрешимости? Или, другими словами, верно ли, что полурешетка рекурсивно перечислимых степеней неразрешимости состоит лишь из двух элементов? Получено отрицательное решение этой проблемы [2]. Решения этих вопросов о строении верхних полурешеток рекурсивно перечислимых т-, tt- и Т-степеней являются определенными вехами в изучении сводимостей. В нач. 1960-х гг. было доказано, что полурешетка Т-степеней (везде ниже подразумеваются полурешетки рекурсивно перечислимых степеней) не является решеткой и не имеет минимальных элементов; тогда же было отмечено существование минимальных m-степеней и показано, что полная m-степень не является точной верхней гранью двух несравнимых т- степеней. Позднее выяснилось, что этот факт не имеет места для btt- и более слабых сводимостей. Ю. Л. Ершов [4] доказал, что верхняя полурешетка m-степеней не является решеткой и что под нек-рыми ее элементами нет минимальных. Аналогичные результаты, а также существование минимальных элементов, были получены для полурешеток btt- и tt -степеней [5]. Установлено, что элементарные теории полурешеток т-, btt-, tt-, Т- и нек-рых других степеней попарно различны.

Второе направление связано с вопросами о том, какие r -степени, сколько их и как они расположены в степенях относительно более слабой сводимости, чем r. В частности, полная Т (tt-, btt- )-степень содержит счетное число рекурсивно перечислимых tt (соответственно btt-, m -)-степеней. С другой стороны, существуют нерекурсивные Т(btt -)-степени, состоящие из одной tt(m-)-степени, но каждая нерекурсивная tt -степень содержит, по крайней мере, две btt -степени.