Алгоритмические сводимости счетных алгебраических систем

• Автор: Калимуллин, Искандер Шагитович
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Казань
• Количество страниц: 220 с.

Оглавление

1 Массовые проблемы представимости алгебраических

систем

1.1 Массовые проблемы и решетка Медведева

1.2 Проблемы представимости алгебраических систем и их

спектры степеней

1.3 Сводимость по перечислимости

1.4 Е- сводимости алгебраических систем

1.5 Обозначения и терминология

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

2.1 Тотальные е-степени и операция скачка в е-степенях

2.2 Тотальные е-степени и простейшие принципы теории
вычислимости
2.3 Тотальные е-степени и относительная квазимималыюсть
2.4 Свойства разложимости тотальных е-степеней
3 Массовые проблемы перечислимости семейств
3.1 Предварительные сведения
3.2 Новые спектры степеней
3.3 Операции на нумерациях и спектры
3.4 Вычислимые нумерации Е-множеств
4 Ограничения на спектры степеней алгебраических систем

4.1 Нерешеточность полурешеток и
4.2 Равномерность сводимости к алгебраическим системам
и тотальные е-степени
4.3 Случай линейных порядков
4.4 Спектры степеней систем произвольной сигнатуры
4.5 Построение степени Ь < О" для которой совокупность
{X І X зс Ь} не является спектром
5 Частичные проблемы представимости алгебраических систем
5.1 Спектры е-степеней семейств подмножеств множества
натуральных чисел
5.2 Относительная Е-определимость семейств в допустимых множествах
5.3 Соотношения между сводимостями алгебраических систем

Введение
В диссертации исследуются алгебраические системы с точки зрения их алгоритмической сложности с помощью двух взаимосвязанных подходов. Первый подход заключается в расширении сводимости по перечислимости на алгебраические системы, а второй основывается на понятие спектра степеней алгебраической системы. Оба, подхода могут быть успешно формализованы на языке сводимостей массовых проблем, введенных Медведевым [5] в 1955 году.
Сводимость по перечислимости (е-сводимость) была введена Роджерсом [32] как расширение тьюринговой сводимости всюду определенных (тотальных) функций на частичные функции, определенные лишь на подмножествах натуральных чисел. Степенями по перечислимости (е-степенями) были названы классы эквивалености относительно отношения взаимо-е-сводимости двух множеств друг к другу. Роджерсом было введено понятие тотальной е-степени — это в точности образы тыоринговых степеней, относительно канонического вложения верхней полурешетки тыоринговых степеней в полурештку степеней по перечислимости. Роджерсом [32] была поставлена фундаментальная проблема инвариантности класса тотальных е-степеией в полурештке степеней но перечислимости. Эта проблема до сих пор остается нерешенной.
Другое фундаментальное понятие, связанное со сводимостью по перечислимостью, операция скачка, было введено Розинасом [8] и Купером [15]. Данная операция также является обобщением (расшире-

что К(U) <е Со® С ® С'2 © U. Зададимся произвольной вычислимой функцией / такой, что для всех х € со выполнено
xeK{U) => Фт(Ц)=ш,
X i K(U) => $f(x)(U) = 0.
Тогда условие х G K(U) эквивалентно условию 5(3/(ж)) Фf(x)(U), что в свою очередь эквивалентно условию 5(3f(x)) € Со, так что Щи) <с graph (5) ® С0 <е Со Ф Сх ф С2 ® U. □
Для получения теоретико-порядкового описания е-степеней и-е-идеальпых пар (см. теорему 2,1.5 ниже), нам необходим следующий результат.
Теорема 2.1.4. Если пара множеств А и В не является 17-е-идеальной, то существуют такие множества X и Y, что Y <е X Ф A, Y <е X © В uY ДХ©[/. Более того, множества X и Y могут быть выбраны вычислимыми (по Тьюрингу) относительно множества А © В © K(U).
Доказательство. Пусть {Ех, Fx}xeu — произвольная вычислимая нумерация всех пар конечных множеств. Для хеш определим множество
Ух —dfn {у G ш | Ех С Еу & Fx С Fv}.
Будем строить множества X и У такими, что для всех х Е си
жеУ ж е X & Ех С А *=> хеХ &FXQ В
(таким образом, множество X может содержать только такие элементы х, для которых условие Ех С А выполняется или не выполняется одновременно с условием Fx С В), что будет обеспечивать сводимости У <е X ® А и У <е X © В. Мы будем также выполнять требования Re : У ф Фе(А' ® U) для каждого е 6 ш.