одно из основных понятий алгоритмов теории и ее приложений Возникло в связи с тем, что неразрешимость(и разрешимость) многих алгоритмических проблем устанавливается большей частью не непосредственно, апутем сведения к исследуемой проблеме такой алгоритмич. проблемы, неразрешимость к-рой уже доказана(или исследуемой проблемы к нек-рой уже решенной проблеме). Так, неразрешимость проблемы гомотопиипутей в полиэдре доказывается путем сведения к ней проблемы равенства слов в соответствующейфундаментальной группе.
Ниже приведены простейшие примеры А. с. теоретико-числовых (т. е. определенных на натуральных числах)предикатов и функций:
АЛГОРИТМИЧЕСКАЯ.docx
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ.
одно из основных понятий алгоритмов теории и ее приложений Возникло в связи с тем, чт
о неразрешимость(и разрешимость) многих алгоритмических проблем устанавливается бо
льшей частью не непосредственно, апутем сведения к исследуемой проблеме такой алгорит
мич. проблемы, неразрешимость крой уже доказана(или исследуемой проблемы к некрой
уже решенной проблеме). Так, неразрешимость проблемы гомотопиипутей в полиэдре дока
зывается путем сведения к ней проблемы равенства слов в соответствующейфундаменталь
ной группе.
Ниже приведены простейшие примеры А. с. теоретикочисловых (т. е. определенных на нат
уральных числах)предикатов и функций:
где Ри Q предикаты. Проблема разрешения предиката Р, т. е. установления истинности и
ложности Рдляразных х, сводится к проблеме разрешения Q, или, короче, Рсводится к Q. Г
оворят также, что множествоистинности Р, т. е.
, сводится
к
Пусть
и
где
числовые функции. Проблема вычисления функции f сводится к проблемевычисления g, ил
и, короче, f сводится к g.
теоретико
Понятие А. с. было уточнено А. М. Тьюрингом (А. М. Turing): если, грубо говоря, некрая
Тьюринга машинаперерабатывает последовательность закодированных значений функции
в последовательностьзакодированных значений функции f, то функция f сводится к функ
ции g. Близкое понятие относительнойвычислимости С. К. Клини (S. С. Kleene) уточнил с п
омощью рекурсивных схем равенств (см. [1]). Послеарифмети
зации каждая алгорптмич. проблема сводится к проблеме вычисления некрой теоретико
, то гов
числовойфункции f. Если f сводится к gпо Тьюрингу,
орят, что f и gимеют одну иту же степень неразрешимости, или
реф
лексивно и транзитивно. Таким образом,все функции (и множества натуральных чисел или
их характеристич. предикаты) разбиваются на классыэквивалентности, наз. тьюринговыми
степенями или Тcтепенями (см.
, a gсводится к f,
Отношение [3]). Большинство алгоритмич. проблем,рассматриваемых в логике и математике, являются
проблемами разрешения (рекурсивно) перечислимыхмножеств конструктивных объектов. В
связи с этим Э. Л. Пост [2] в 40х гг. 20 в. предпринял исследованиеперечислимых множест
в и ввел наряду с тьюрпнговой некрые специальные виды А. с., сформулировавпроблему (с
водимости): сводятся ли (по Тьюрингу) друг к другу различные перечислимые неразрешим
ыемножества? Позже было установлено, что перечислимые множества образуют бесконечн
ую весьма богатуюсистему Тстепеней. При этом был найден так наз. метод приоритета, ши
роко используемый в теорииалгоритмов.
определенная
В дальнейшем степени неразрешимости нашли применение в других областях математики.
Так, напр., длявсяких Tстепеней аи bперечислимых множеств при
группа, в крой проблема равенства слов имеет степень
существует конечно
а, а проблема сопряженности степень b. Имеется тесная связьмежду степенями (относите
льно различных видов А. с.) перечислпмых множеств и скоростью роста сложностиначальн
ых фрагментов перечислимых множеств. Специальный вид сводимости полиномиальнаясв
одимость, или р сводимость (сводимость с некрым ограничением на время), используетс
я придоказательстве универсальности алгоритмич. проблем "переборного типа", т. е. пробл
ем комбинаторногохарактера из разных областей математики (см.
[5]; более подробную лит. см. в [1]). В свою очередь, приисследовании степеней стали прим
енять методы теории меры (см. [1], гл. 16) и вынуждения метод (см. [4]).
Лит.:[1] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с а
нгл., М., 1972, гл. 9,10, 13, 16; [2] Роst Е. L., "Bull. Amer. Math. Вез.", 1944, v. 50,
№ 5, p. 284316; [3] Кleene S.C., PostE.L., "Ann.Math.", ser. 2, 1954, v. 59, №3, p. 379407;
[4] Selman A. L., "Proc. bond. Math. Soc.", ser. 3, 1972, v. 25, № 4, p.586602;
[5] Карп Р., в кн.: Кибернетический сборник, в. 12, М., 1975. А. А. Мучник.
В диссертации исследуются алгебраические системы с точки зрения их алгоритмической
сложности с помощью двух взаимосвязанных подходов. Первый подход заключается в
расширении сводимости по перечислимости на алгебраические системы, а второй
основывается на понятие спектра степеней алгебраической системы. Оба подхода могут
быть успешно формализованы на языке сводимосгей массовых проблем, введенных
Медведевым [5] в 1955 году.
Сводимость по перечислимости (есводимость) была введена Роджерсом [32] как
расширение тьюринговой сводимости всюду определенных (тотальных) функций на
частичные функции, определенные лишь на подмножествах натуральных чисел. Степенями по перечислимости (естепенями) были названы классы эквивалености относительно
отношения взаимоесводимости двух множеств друг к другу. Роджерсом было введено
понятие тотальной естепени — это в точности образы тыоринговых степеней,
относительно канонического вложения верхней полурешетки тыоринговых степеней в
полурештку степеней по перечислимости. Роджерсом [32] была поставлена
фундаментальная проблема инвариантности класса тотальных естепеней в полурештке
степеней по перечислимости. Эта проблема до сих пор остается нерешенной.
Другое фундаментальное понятие, связанное со сводимостью по перечислимостью,
операция скачка, было введено Розинасом [8] и Купером [15]. Данная операция также
является обобщением (расширением) операции скачка в тьюринговых степенях. Поскольку
областью значений операции скачка являются только тотальные естепени, с проблемой
инвариантности класса тотальных естепеней тесно связана проблема инвариантности
оператора скачка в полурешетке степеней по перечислимости. Купером [16] и Сорби [40]
были поставлены проблемы определимости класса тотальных естепеней и операции скачка
на языке первого порядка упорядочения естепеней. В диссертации получено частичное
решение первой проблемы и полное решение второй.
Понятия степени и спектра степеней алгебраической системы было введено Рихтер [31] в
1981 году. Цель введения степени алгебраической системы заключалась в попытке
классифицировать сложность неконструктивизируемых алгебраических систем с помощью
тьюринговых степеней, структура которых была к тому времени достаточно хорошо
изучена. Однако самой же Рихтер [31] было обнаружено, что не каждый спектр степеней
алгебраической системы имеет наименьший элемент, то есть не каждая алгебраическая
система имеет степень. Более того, остается до сих пор не решенной задача описания
возможных спектров степеней алгебраических систем. В этом направлении работали и
работают много российских и зарубежных исследователей (см. например [17], [19],[21],
[22],[25], [37],[41],[42]).
В настоящей диссертации предпринята попытка систематизации полученных сведений о
спектрах степеней на языке сводимостей массовых проблем, введенных Медведевым [5] и
Мучником [6]. На этом языке формулируются и новые результаты полученные автором,
являющиеся содержательной частью диссертации. В качестве массовых проблем здесь
рассматриваются проблемы представимости алгебраических систем. В качестве
сводимости этих проблем используется как равномерная сводимость Медведева (сильная
сводимость), так и неравномерная сводимость Мучника (слабая сводимость). Данная
трактовка позволяет, с другой стороны, рассматривать сводимость по перечислимости, как
частный случай сводимости проблем представимости на алгебраических системах специального вида. Отметим, что при таком рассмотрении тотальные естепени
соответствуют алгебраическим системам, имеющим степень (в смысле Рихтер [31]).
Перейдем теперь к конкретному описанию результатов, полученных в диссертации.
Диссертация разбита на пять глав. Каждая глава разбита на параграфы, количество
которых варьируется между тремя и пятью.
Первая глава носит вводный характер. В ней содержатся основные сведения о сводимости
па массовых проблемах (параграф 1), о массовых проблемах представимости
алгебраических систем (параграф 2), о сводимости по перечислимости (параграф 3), о е
сводимости алгебраических систем (параграф 4). В параграфе 5 приведены обозначения и
терминология, общие для всей диссертации.
Вторая глава посвящена различным описаниям класса тотальных естеиеней. В параграфе 1
второй главы устанавливается определимость операции скачка естепеней и и и' на языке
упорядочения естеиеней (что решает проблему, поставленную Купером [16] и Сорби [40]).
Для этого, установливается, что предикат х > и7 имеет место в естепенях тогда и только
тогда, когда х > и и
Уа > и)(УЪ > и) (Ус > и) [(Уг > и) [(а и г) П (Ь и г) г к (а и ъ) П (с и г) = г] Ь и х = с и х].
Кроме того, устанавливается, что предикат х < и' имеет место в естепенях тогда и только
тогда, когда
За > и)(ЗЬ > и) (Зс > и) (Уг > и) [(а и г) П (Ъ и г) = г & (Ь и ъ) П (с и г) = г & (а и г) П (с и г)
= г & х < а и Ь и с].
Следовательно, операция скачка ин^и' может быть определена в естепенях посредством
конъюнкции УЗУ и ЗУЗформул в сигнатуре частичного упорядочения естепеней.
Отсюда также следует определимость класса ТОТ(> 0^,) тотальных естепеней,
расположенных выше (или равных) естепсни 0'р (что частично отвечает на вопрос
Роджерса [32]).
А именно естепень х является тотальной и расположена выше (или равна) естепени 0'е
тогда и только тогда, когда выполняется конъюнкция формульных пердикатов
За > 0е)(ЗЬ > 0е)[х = а и Ь & (Уг)[(а и ъ) П (Ь и ъ) = г]] и
Уа > 0е) (УЬ > 0е) (Ус > 0е) [(Уг) [(а и г) П (Ь и г) = г] &
Уг)[(аиг) П (с и ъ) = г] Ь и х = с и х]. Из определимости класса ТОТ(> 0'е) следует
тождественность автоморфизмов полурешетки степеней по перечислимости на естепенях,
расположенных выше 0'е".
Кроме того, параграф содержит описание множеств, есводящихся к ескачку заданного
множества, являющееся аналогом леммы о пределе из классической
теории вычислимости для сводимости по перечислимости.
В параграфе 2 второй главы исследуется связь тотальности естепени с простейшими
принципами обобщенной вычислимости. В частности, установлена эквивалентность
тотальности естепени арифметического множества А с принципами униформизации и
редукции, если класс вычислимо псречислимых множеств заменить классом есводящихся
к А множеств. Результаты этого параграфа получены совместно с Пузаренко
(Новосибирск).
В параграфе 3 второй главы устанавливается эквивалентность проблем инвариантности и
определимости класса тотальных естепеней (проблема Роджерса) с проблемой
инвариантности и определимости предиката относительной квазиминимальности.
А именно, естепень а является нетотальной тогда и только тогда, когда выполнен
формульный предикат
Зи)[С^(аи и, и)], что также эквалснтно выполнению другого предиката (также являющегося
формульным в силу результатов параграфа 1 второй главы)
Зи) [(2 (а и и, и) & (а и и)' = и'].
Здесь С^(а, Ь) — предикат относительной квазиминимальности, означающий, что для
каждой тотальной естепени х < а справедливо х < Ь.
В параграфе 4 второй главы приводится достаточный критерий для того, чтобы тотальная
естепень разлагалась над заданной естепенью. Данный результат может быть в будущем
использован при решении вышеупомянутой проблемы Роджерса. Результаты этого
параграфа получены совместно с Арслановым (Казань) и Купером (Лидс,
Великобритания).
Отметим, что в параграфе 2 четвертой главы приведена еще одна характеризация
тотальных естепеней уже на языке сводимостей алгебраических систем.)
Третья глава посвящена развитию методологии построения алгебраических систем
спектров степеней с заданными свойствами; в частности, со спектрами степеней, имеющих
вид {х | х ^ Ь}. В параграфе 1 третьей главы, носящим вводный характер, излагается используемый в дальнейшем способ кодирования семейств множеств в алгебраические
системы.
В параграфе 2 третьей главы устанавливается существование алгебраических систем,
имеющих спектр степеней {х | х ^ Ь}, где Ь — произвольная низкая тьюринговая степень.
Для этого дается удобное описание спектров семейств, имеющих вид
W(TZ, v) = {{п} ®U\neu>&U eKkU ф z/(n)}, где 7Z — некоторое вычислимо перечислимое
семейство, содержащее все конечные множества (например семейство всех конечных
множеств или семейство всех вычислимо перечислимых множеств), а и — некоторая
вычислимая нумерация В частности, из описания следует, что спектр степеней таких
семейств не зависит от выбора семейства 1Z. Кроме того, выделяются такие нумерации v
(названные CSнумерациями), для которых описание спектра степеней семейства W(7Z, v)
наиболее просто. Вычислимых С ¿/нумераций ДЦ множеств оказывается достаточно,
чтобы получить спектры степеней вида {х ¡ х % Ь}, где b — произвольная низкая
тьюринговая степень: если В Е Ь, то v = Xn[Wrf] будет вычислимой Сб'нумерацией Д®
множеств, и спектр степеней семейства W( 1Z, v) в точности будет иметь вид {х | х ^ Ь}.
Кроме того, в данном параграфе приводится метод, позволяющий строить алгебраические
системы сводящиеся друг к другу в слабом смысле, но не сводящиеся в сильном смысле,
даже если позволить обагощать системы конечным числом констант. Этот метод найдет
применение как в четвертой главе (параграф 2), так и в пятой главе (параграф 3).
В параграфе 3 третьей главы доказана вложимость произвольной счетной дистрибутивной
решетки в структуры слабых степеней алгебраических систем. Кроме того, здесь найдено
некоторое патологическое свойство структуры сильных и слабых степеней. А именно,
установлено, что существуют возрастающие цепочки алгебраических систем (относительно
рассматриваемой сводимости), имеющие в качестве точной верхней грани некоторую
другую алгебраическую систему. При доказательстве этих результатов продолжается
изучение спектров степеней семейств \ViJZ, I/), начатое в предыдущем параграфе. В
частности, рассматриваются соотношения между теоретикомножественными операциями
на спектрах степеней семейств вида и) (пересечение и объединение спектров) и операциями
на нумерациях (прямая сумма и прямое произведедение). Изучаются также и бесконечные
суммы нумераций.
В параграфе 4 третьей главы устанавливается существование алгебраических систем,
имеющих спектр степеней {х | х ^ Ь}, где Ь — произвольная вычислимо перечислимая
тьюринговая степень. В частности, существует алгебраическая система, спектр степеней
которой есть {х | х ^ 0'}. Семейства, исследованые в первых двух параграфах третей главы, не могут быть здесь
использованы: если 71 — вычислимо перечислимое семейство, содержащее все конечные
множества, ни — вычислимая нумерация Д®, то спектр степеней семейства УУ(7^, у)
содержит все ненизкие степени. Поэтому, здесь рассматриваются семейства вида УУ(7\
£В), где V — семейство всех областей значений возрастающих примитивно рекурсивных
функций {V состоит только из бесконечных множеств), ев = \п[\¥в], и В 6 Ь — вычислимо
перечислимое множество (здесь Ь не обязательно является низкой степенью, так что ев
вообще говоря не будет нумерацией Д<] множеств). Устанавливается, что спектр
семейства УУ(Р,£В) есть {х | х ^ Ь}.
Четвертая глава посвящена в основном теоретическим результатам, ограничивающим
методологию развитую в третьей главе. Одновременно с этим получены некоторые
решения проблем, касающихся спектров степеней и различий сильной и слабой
сводимости.
В параграфе 1 четвертой главы доказана нерешеточность верхних полурешеток сильных и
слабых степеней алгебраических систем.
Для этого устанавливается, что если несравнимые степени ао и ах лежат в спектре
степеней счетной алгебраической системы, то этот, же спектр степеней должен содержать
также некоторую степень Ь такую, что ао ^ Ь, ах ^ Ь и Ь' < а^. Оценка Ь' < а^ вместе с
результатами из параграфа 1 третей главы, позволяет сделать вывод о том, что две
алгебраические системы, имеющие спектры степеней {х | х > ао} и {х | х > ах},
соответственно, не имеют точной нижней грани относительно слабой сводимости, если
степени ао и а.1 несравнимы и являются низкими. Выбирая две конкретные алгебраические
системы с указанными выше спектрами степеней, можно распространить данное
утверждение и на сильную сводимость алгебраических систем.
В параграфе 2 четвертой главы дается характеризация тотальных естепеней как е
степеней таких алгебраических систем, сильная и слабая сводимости к которым не
отличаются между собой (даже с точностью до конечных обогащений константами).
Для этого для каждой алгебраической системы, не имеющей степени, среди тыоринговых
скачков спектра степеней которой имеется наименьший, строится другая алгебраическая
система, слабо сводящаяся к первой (то есть неравномерно), но несводщаяся к ней сильно
(то есть равномерно), даже если разрешить обогащать системы конечным числом констант.
В параграфе 3 четвертой главы приводится отрицательный ответ на вопрос Миллера [28]
об отделимости несравнимых степеней спектрами степеней линейных порядков. Более того, установлено, что для каждой ненулевой степени а существует такая
несравнимая с а степень Ь, Ь' < а', содержащаяся во всех спектрах степеней счетных
линейных порядков, в которых содержится степень а.
Приводятся косвенные аргументы в пользу отрицательного ответа на вопрос Доуни [17] о
существовании линейных порядков со спектром степеней {х | х > 0}.
В параграфе 4 четвертой главы устанавливается существование тьюринговой степени b <
такой, что совокупность {х | х ^ Ь} не является спектром степеней никакой алгебраической
системы.
Для этого, устанавливается, что для каждой пары несравнимых степеней ао и ai существует
такая степень b < (aoUai)(4), что ао ^ Ь, ai ^ Ь, и каждый спектр степеней алгебраической
системы, содержащий степени а0 и ai должен содержать также степень Ь. В отличие от
указанного выше результата из параграфа 1 четвертой главы здесь степень b не зависит от
фиксированной заранее алгебраической системы со своим спектром степеней. Однако
здесь установленная ранее оптимальная оценка b' < а() ухудшается до b < (a0Uai)(4) (от
оценки скачка степени b всего лишь однократным скачком одной из степеней cío и ai до
оценки только лишь самой степени b четырехкратным скачком точной верхней грани
степеней ао и ai). Отметим также, что в силу вышеупомянутого результата из второго
параграфа оптимальная оценка сохраняется, если вместо произвольных алгебраических
систем ограничится лишь линейными порядками. В параграфе 5 четвертой главы основной
результат параграфа 4 усиливается, посредством построения степени b < 0" такой, что
совокупность {х | х ^ Ь} не является спектром степеней никакой алгебраической системы.
Для этого, в отличие от предыдущего параграфа, устанавливается, что для каждой
ненулевой степени ао существуют такие степени ai < а'о и b < а'о, что ао ^ b, ai Ь, и каждый
спектр степеней алгебраической системы, содержащий степени ао и ¿i, должен содержать
также степень Ь. При доказательстве этого утверждения используется метод приоритета с
бесконечными нарушениями, а также техника работы со степенями по перечислимости.
Пятая глава посвящена изучению есводимостей алгебраических систем, основанных на
сводимости частичных проблем представимости, введенных Дымент [1]. В частности,
оценивается возможность применения методов, разработанных в предыдущих главах для
изучения спектров естепеней и есводимостей алгебраических систем.
В параграфе 1 пятой главы исследуются спектры естепеней семейств множеств,
натуральных чисел. Доказывается, что спектр естепеней семейства всех бесконечных
вычислимо перечислимых множество совпадает с классом высоких естепеней (то есть е
степеней, скачок которых ограничен снизу двойным скачком нулевой естепени). Для доказательства используется аналог леммы о пределе для сводимости по перечислимости,
полученной в параграфе 1 второй главы.
Кроме того, устанавливается, что в отличие от результатов об обычных спектрах степеней
семейств из третей главы спектр естепеней семейств конечных множеств не может
совпадать с классом всех ненулевых естеиеней.
Наконец, доказывается, что спектр естепеней семейства б") состоит в точности из
ненулевых естепеней (где Е — семейство всех вычислимо перечислимых множеств, иг =
Лп[Ж„]). Откуда следует, что существует алгебраическая система со спектром естепеней,
совпадающим с классом всех ненулевых естепеней. То же самое оказывается верным, если
вместо понятия спектра естепеней использовать понятие расширенного спектра степеней,
введенного Сосковым [41].
В параграфе 2 пятой главы исследуется важный частный случай есводимости
алгебраических систем, связанный с £определимостью в допустимых множествах. Здесь
проводится сравнительный анализ выразительной мощности Еопределений относительно
простейших не вычислимо переслимых семействах вычислимо перечислимых множеств
(семейство графиков всюду определенных функций, семейство бесконечных вычислимо
перечислимых множеств и проч.). Обсуждается проблема введения операции скачка для Е
степеней семейств. Результаты этого параграфа получены совместно с Пузаренко
(Новосибирск).
В параграфе 3 пятой главы полностью описываются все возможные соотношения между
сильной сводимостью, слабой сводимостью, сильной есводимости, слабой есводимостью
алгебраических систем, также как и отношения Еопределимости одной системы в
конечнонаследственной надстройке другой (см. [2]).
А именно, установлено, что соотношения между
рассматриваемыми сводимостями исчерпываются нижеперечисленными:
• из Еопределимости одной системы в конечнонаследственной надстройке другой без
параметров следует сильная есводимость первой системы ко второй;
• из сильной сводимости следует слабая сводимость;
• из сильной есводимости следует слабая есводимость;
• из сильной есводимости следует сильная сводимость;
• из слабой есводимости следует слабая сводимость. Данное описание остается верным, если в определении сводимостей разрешить обогащать
системы конечным числом констант.
Данный параграф завершает исследование рассматриваемых соотношений, начатое
Стукачевым в работе [10]. При доказательстве используются результаты из параграфа 1
второй главы, параграфа 1 третьей главы и первых двух параграфов пятой главы.
На защиту выносятся следующие результаты:
• Решение проблемы определимости операции скачка естепеней, поставленной Купером
[16] и Сорби [40].
• Определимость класса тотальных естепеней, расположенных выше 07е, что частично
решает проблемы Роджерса об определимости класса тотальных естепеней.
Характеризации класса тотальных естепеней посредством предиката относительной
квазиминимальности, а также на языке сильных и слабых сводимостей алгебраических
систем.
• Решение проблемы Миллера [28] об отделимости несравнимых степеней спектрами
степеней линейных порядков.
• Построение алгебраических систем, спектр степеней которых имеет вид {х|х ^ Ь}, где b
— низкая или вычислимо перечислимая степень.
• Построение степени b < О" такой, что совокупность {х|х ^ Ь} не является спектром
степеней никакой алгебраической системы.
• Вложимость произвольной счетной дистрибутивной решетки в слабые степени
алгебраических систем с сохраниением точных верхних и нижних граней. Нерешеточность
верхних полу решеток сильных и слабых степеней алгебраических систем.
• Полное описание всех возможных соотношений между сильной сводимостью, слабой
сводимостью, сильной есводимости, слабой есводимостыо и отношения Еопредлимости.
Результаты главы 2 опубликованы в работах автора [1],[2], [9], [10], [11], [13], [15], [18]
(см. список публикаций автора по теме диссертации в конце диссертации), главы 3 в
работах [3], [4], [14], [17], главы 4 в работах [5], [7], [17], главы 5 в работах [6], [8], [12],
[16].
Результаты диссертации по мере их получения докладывались на следующих
конференциях:
Logic Colloquium 2001, Вена, Австрия, 611 августа 2001 г. Computability and Models, Алматы, Казахстан, 2428 июня 2002
Logic Colloquium 2002, Мюнстер, Германия, 310 августа 2002 г.
British Mathematical Colloquium 2003, Берингем, Великобритания, 710 апреля 2003 г.
Алгебра и Анализ 2004, 2 9 июля 2004, Казань;
Мальцевские чтения 2004, Новосибирск, 1618 ноября 2004 г.
Methods of Logic in Mathematics 2005, СанктПетербург, 1824 июля 2005 г.
Computational prospects of infinity, Сингапур, лето 2005 г.
Мальцевские чтения 2005, Новосибирск, 1517 ноября 2005 г.
Computabilty in Europe 2006, Суонси, Великобритания, 30 июня 5 июля 2006 г.
Мальцевские чтения 2006, Новосибирск, 1416 ноября 2006 г.
Computabilty in Europe 2007, Сиена, Италия, 1618 июня 2007 г.
Мальцевские чтения 2008, Новосибирск, 1113 ноября 2008 г.
Итоговые научные конференции Казанского университета, 2002 2008.
Результаты докладывались на семинаре Алгебра и логика (Новосибирск, ИМ СО РАН, рук.
академик Ершов Ю.Л.), логическом семинаре Отделения Математики университета
Лидса (Великобритания, рук. проф. С. Вейнер, проф. C.B. Купер), логическом семинаре
математического факультета Висконсинского университета (США, рук. проф. С. Лемпп),
семинаре по теории вычислимости Чикагского университета (США, рук. проф. Р. Соар),
логическом семинаре математического факультета университета Ватерлоо (Канада, рук.
Р. Виллард). В целом работа доложена на семинаре по теории вычислимости на механико
математическом факультете Казанского государственного университета (рук. проф.
М.М.Арсланов).
Автор выражает глубокую благодарность М.М. Арсланову за постоянное внимание к
работе и плодотворные беседы, способствовавшие улучшению диссертации.
Список литературы диссертационного исследования доктор физикоматематических
наук Калимуллин, Искандер Шагитович, 2009 год
1. Е. 3. Дымент; О некоторых свойствах решетки Медведева, Матем. сборник, 101 (1976),
360379. 2. Ю.Л. Ершов; Определимость и Вычислимость, Научная книга, Новосибирск, Экономика,
Москва, 2000.
3. И.Ш. Калимуллин; Об элементарных теориях пв.п. степеней по перечислимости,
Известия Вузов. Математика, № 4 (2001), 2427.
4. И.Ш. Калимуллин, В.Г. Пузаренко; О сводимости на семействах, Алгебра и логика, № 1
(2001), 3351.
5. Ю.Т. Медведев; Степени трудности массовых проблем, ДАН СССР, 104 (1955), 501504.
6. A.A. Мучник; О сильной и слабой сводимости алгоритмических про блем, Сиб. матем.
журнал, 4 (1963), 13281341.
7. A.C. Морозов, В.Г. Пузаренко; О Еподмножествах натуральных чисел, Алгебра и
логика, 43, №3(2004), 291 320.
8. М.Г. Розинас; Полурешетка естепеней, Рекурсивные функции, Ива ново, Ивановский
гос. университет, 7184, 1978.
9. В. Л. Селиванов; Об индексных множествах вычислимых классов конечных множеств,
Алгориты и Автоматы, под ред. М.М. Арсланова, Казань, 1978, 9599.
10. А.И. Стукачев; О степенях представимости моделей. I, Алгебра и логика, 6 (2007), 763
788
11. S. Ahmad; Embedding the diamond in the E2 enumeration degrees, J. Symbolic Logic, 50
(1991), 195212.
12. S. Ahmad, A.H.Lachlan; Some special pairs of E2 edegrees properties of E2— enumeration
degrees, Math. Logic Quarterly, 44 (1998) ,431449.
13. M.M. Arslanov, A. Sorbi; Relative splittings of 0'e in the enumeration degrees, In Buss S.
and Pudlak P., editors, Logic Colloquium '98. SpringerVerlag, 1999.
14. H.G. Carstens; Д^mengen, Arch.Math. Log. Grundlag., 18 (1978), 55 65.
15. S.B. Cooper; Partial degrees and the density problem. Part 2: The enumeration degrees of the
E2 sets are dense, J. Symbolic Logic, 49 (1984), 503513.
16. R. Downey; On presentations of algebraic structures, Complexity, Logic, and Recursion
Theory, ed. A. Sorbi (New York: Dekker, 1997), 157205. 17. Richard J. Coles, R.G. Downey, T.A. Slaman; Every set has a least jump enumeration. J.
London Math. Soc., 62(2000), 641649.
18. S.S. Goncharov, V.S. Harizanov, J.F. Knight, C. McCoy, R.G. Miller, R. Solomon;
Enumerations in computable structure theory, Annals of Pure and Applied Logic, 136, 3 (2005),
219246.
19. L. Gutteridge; Some results on enumeration reducibility, PhD thesis, Simon Fraser
University. 1971.
20. V.S. Harizanov, R. Miller; Spectra of structures and relations, Journal of Symbolic Logic, 72
(2007), 324348.
21. D.R. Hirschfeldt, B. Khoussainov, R.A. Shore, A.M. Slinko; Degree spectra and computable
dimensions in algebraic structures, Annals of Pure and Applied Logic, 115 (2002), 71113.
22. C.G. Jockusch, Jr.; Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc.,
131 (1968), 420436.
23. C.G. Jockusch, Jr.; Degrees in which the recursive sets are uniformly recursive, Canad. J.
Math., 24 (1972), 10921099.
24. J.F. Knight; Degrees coded in jumps of orderings, J. Symbolic Logic, 51 (1986), 10341042.
25. K. McEvoy; Jumps of quasiminimal enumeration degrees, J. Symbolic Logic, 50 (1985),
839848.
26. K. McEvoy, S.B. Cooper; On minimal pairs of enumeration degrees, J. Symbolic Logic, 50
(1985), 9831001.
27. R.G. Miller; The Ailspectrum of a linear order, J. Symbolic Logic 66 (2001), 470486.
28. A. Nies; Lowness properties and randomness, Advances in Mathenatics, 197 (2005), 274
305.
29. D. Posner, R.W. Robinson; Degrees joning to 0', J. Symbolic Logic, 46 (1981), 714722.
30. L.J. Richter; Degrees of structures, J. Symbolic Logic, 46 (1981), 723731.
31. H. Rogers, Jr.; Theory of Recursive Functions and Effective Computability, McGrawHill,
New York, 1967.
32. A.L. Selman; Arithmetical reducibilities. I. Z. Math. Logik Grundlag. Math., 17(1971), 335
350. 33. R.A. Shore; Local definitions in degree structures: the turing jump, hyperdegrees and
beyond, Bull. Symbolic Logic, 13 (2007), 226238.
34. R.A. Shore, T.A. Slaman; Defining the Turing jump, Math. Research Letters, 6 (1999), 711
722.
35. T. Slaman; Degree structures, Proceedings of the international congress on mathematics,
Kyoto (1990), SpringerVerlag, Tokyo, 303316.
36. T. Slaman; Relative to any nonrecursive set, Proc. Amer. Math. Soc., 126 (1998), 21172122.
37. R.I. Soare; Recursively enumerable sets and degrees, Heidelberg: SpringerVerlag, 1987.
38. A. Sorbi; The enumeration degrees of £<] Complexity, Logic, and Recursion Theory, ed. A.
Sorbi (New York: Dekker, 1997), 303330.
39. A. Sorbi; Open problems in the enumeration degrees //In P.A. Cholak, S. Lempp, M.
Lerman, and R.A. Shore, Contemporary Mathematics 257, American Mathematical Society,
Providence, 2000, C. 839848.
40. I.N. Soskov; Degree spectra and cospectra of structures, Ann. Univ. Sofia, 96 (2003), 4568
41. S. Weimer; Enumerations, countable structures, and Turing degrees, Proc. Amer. Math. Soc.,
126 (1998), 21312139.
42. C.E.M. Yates; On the degrees of index sets II, Trans. Amer. Math. Soc., 135 (1969), 249
266.Список публикаций автора по теме диссертации
43. Арсланов М.М., Калимуллин И.Ш., Купер С.Б. Свойства разложения тотальных
степеней по перечислимости // Алгебра и Логика. 2003. Т. 42, № 1. С. 325.
44. Калимуллин И.Ш., Пузаренко В.Г. О принципах вычислимости на допустимых
множествах // Мат. Труды. 2004. Т. 7, № 2, С. 3571.
45. Калимуллин И.Ш. Спектры степеней некоторых алгебраических структур // Алгебра и
Логика. 2007. Т. 46, № 6. С. 729744.
46. Калимуллин И.Ш., Почти вычислимо перечислимые семейства множеств //
Математический сборник. 2008. Т. 199, № 10. С. 3340
47. Калимуллин И.Ш., Ограничения на спектры степеней алгебраических структур //
Сибирский мат. журнал. 2008. Т. 49, №6. С. 12961309. 48. Калимуллин И.Ш., Пузаренко В.Г. О сводимости на семействах // Алгебра и логика
2009. № 1. С. 3351.
49. Калимуллин И.Ш. Равномерность сводимостей алгебраических систем // Сибирский
мат. журнал 2009. № 2. С. 334343.
50. Калимуллин И.Ш. Соотношения между алгоритмическими сводимостями
алгебраических систем // Известия ВУЗов 2009. №6. С. 7172.
51. Kalimulllin I.Sh. Splitting properties of nc.e. enumeration degrees //J. Symbolic Logic.
2002. V. 67. P. 537546.
52. Kalimulllin I.Sh. Definability of the jump operator in the enumeration degrees //J.
Mathematical Logic. 2003. № 2. P. 257267.
53. Kalimullin I.Sh. Elementary differences between the (2p)c.e. and the (2p+ l)c.e.
enumeration degrees. //J. Symbolic Logic. 2007. V. 72, № 1. P. 277284.
54. Kalimullin I. Sh., Enumeration degrees and enumerability of familes // Journal of Logic and
Computation. 2009. V.19. № 1. P. 151158.
55. Арсланов M.M., Калимуллии И.Ш. Исследования по теории вычислимости //В книге
"На рубеже веков. НИИММ Казанского университета". Казань, издво Казан, матем.
общества. 2003. С. 5068.
56. Kalimullin I.Sh. On primitive recursive permutations // In: Cooper S.B., Goncharov S.S. eds.
Computability and models. New York, NY: Kluwer Academic/Plenum Publishers 2003. P.
249258.
57. Kalimullin I.Sh. On the problems of definability in the enumeration degrees // Lecture Notes
in Computer Science. 2005. V. 3526. P. 221222.
58. Kalimullin I.Sh. The Dyment reducibility on the algebraic structures and on the families of
subsets of omega // Proceedings of the Second Conference on Computability in Europe (CiE
2006), University of Wales Swansea 2006. № CSR 72006. P. 150159
59. Kalimullin I.Sh. Some notes on degree spectra of the structures // Lecture Notes in Computer
Science. 2007. V. 4497. P. 389398.
60. Arslanov M. M., Cooper S.B., Kalimullin I.Sh., Soskova M.I., Total degrees and nonsplitting
properties of enumeration degrees //1.cture Notes in Computer Science. 2008. V. 4978. C.
568578 Научная библиотека диссертаций и авторефератов
disserCat http://www.dissercat.com/content/algoritmicheskiesvodimostischetnykh
algebraicheskikhsistem#ixzz3R8smw2ou
Формулировка теоремы Райса
Теорема Райса
ЧРФ1,
,
ЧРФ1,
, тогда
не является ЧРФ.
Здесь
характеристическая функция множества
.
Другая формулировка теоремы Райса
некоторое свойство одноместных интуитивно вычислимых функций. Назовем
существуют и функции, обладающие
Пусть
свойство нетривиальным , если в множестве
этим свойством, и функции, не обладающие им.
Тогда теорему Райса можно переформулировать так:
Каково бы не было нетривиальное свойство
вычислимых функций, задача распознавания этого свойства алгоритмически
неразрешима.
одноместных интуитивно
Отсюда следует, в частности, что задача восстановления алгоритма по тексту программы
алгоритмически неразрешима. В рамках ликбеза в уютной жежешечке: теорема Райса
Давайте рассмотрим все алгоритмы, существующие на свете, и попытаемся узнать, можно
ли автоматически, с помощью машины (т.е. опять же алгоритма) отвечать на какието
вопросы, касающиеся тех или иных алгоритмов.
Рассмотрим два алгоритма
входе они оба либо не останавливаются, либо выдают один и тот же ответ.
. Назовем их эквивалентными, если на одном и том же
и
Любой алгоритм имеет текст. Текст алгоритма — строка в некотором ограниченном
алфавите. Так что мы можем выписать все строки, которые существуют в этом алфавите
(например, в лексикографическом порядке), этих строк счетное число, и можно
пронумеровать их последовательно натуральными числами. Некоторые из этих строк
представляют собой корректные алгоритмы, остальные же — "не компилирующиеся" —
будем считать алгоритмами, которые всегда зацикливаются. Итак, каждый алгоритм
получил свой уникальный номер.
, либо оба не лежат в нем.
. Назовем его инвариантным, если
Рассмотрим некоторое числовое множество
выполняется следующее свойство: номера любых двух эквивалентных алгоритмов либо оба
лежат в
Например, множество "Алгоритмы, которые на входе 1 выдают 39" — инвариантно.
Аналогично инвариантными являются множества "Алгоритмы, которые останавливаются
хоть на какомнибудь входе", "Алгоритмы, которые возвращают только четные числа",
"Алгоритмы, которые никогда не зацикливаются" и так далее.
Фактически, понятие инвариантного множества можно представлять как
некоторое свойство алгоритма. Причем мы берем только свойства, характеризирующие
алгоритм как класс — зависящие от его входа, выхода и факта конечного времени работы.
Например, множество "Алгоритмы, выполняющие ровно 42 шага" — не инвариантно.
Очевидно, если множество
инвариантно.
— инвариантно, то его дополнение
также
называется разрешимым, если для него можно построить разрешающий
, который для любого числа на входе всегда останавливается и выдает 1,
Множество
алгоритм
если
Простой пример разрешимого множества — простые числа. Сюда же относятся четные
, и 0, если
. числа, любые конечные множества, все множество
Существуют также неразрешимые множества, но в данном посте этот вопрос затрагивать не
стоит.
, и еще многие различные примеры.
, в противном же случае (
, который принимает на вход число , и
называется перечислимым, если для него можно
Множество
построить полуразрешающий алгоритм
возвращает 1, если
Понятно, что любое разрешимое множество является перечислимым: разрешающий
алгоритм легко превратить в полуразрешающий, добавив ему в конец вечный цикл вместо
возвращения значения 0. Гораздо интереснее вопрос "Существует ли перечислимое
неразрешимое множество?" Правильный ответ — да, существует, и не одно, однако
построение конкретных примеров тоже выходит за рамки данного поста.
) — зацикливается.
Теорема Райса (в некоторых редакциях теорема УспенскогоРайса) утверждает
поразительный факт:
Любое нетривиальное свойство алгоритма является неразрешимым.
Иными словами:
Если некоторое инвариантное множество
либо
разрешимо, то имеет место
, либо
.
Доказательство проведем методом от противного. Пусть существует разрешимое
инвариантное множество
, и оно нетривиально.
Рассмотрим алгоритм
принадлежит классу
классе
.
, который зацикливается на любом своем входе. Он либо
, либо его дополнению; пускай для определенности он лежит в
Поскольку множество
одно число:
.
по условию нетривиально, то в его дополнении лежит хотя бы
— какоенибудь перечислимое неразрешимое множество. Мы знаем, что такие в
Пусть
принципе существуют, а какое это конкретно множество, здесь неважно.
Построим специальную функцию. Она будет принимать на вход два числа
себя следующим образом. Если
вычисления зацикливается). Иначе же мы берем алгоритм под номером (номер мы
выбрали ранее из дополнения), и запускаем его на входе . Если обозначить через
и , и ведет
, то значение функции не определено (алгоритм её алгоритм под номером , то данную функцию можно записать аналитически:
Понятно, что эта функция является вычислимой, то есть для нее существует
соответствующий алгоритм вычисления значения. Возьмем полуразрешающий алгоритм
для
алгоритм никогда не остановится, что нам, собственно, и нужно.
, если он выдал единицу — запустим алгоритм
, иначе полуразрешающий
Теперь зафиксируем один из параметров функции
аргумента с параметром
, или
переписать следующим образом:
, превратив её в функцию от одного
. Её определение как алгоритма теперь можно
Действительно, в одном случае она тождественно совпадает с алгоритмом
другом — с никогда не останавливающемся алгоритмом
.
, а в
У
, как у любого алгоритма, есть свой номер. Обозначим его
.
, то
Итак, если
случае они эквивалентны. По определению инвариантного множества
в
ведет себя так же, как и алгоритм
, как и число .
, а стало быть, в этом
тоже лежит
, как и
— множество разрешимое, а значит, существует алгоритм, который
Но
для любого числа может за конечное время подтвердить либо опровергнуть
факт
эквивалентного факта
— множество неразрешимое. Пришли к противоречию.
. Тогда такой алгоритм будет одновременно определять истинность
, и значит, подходит как разрешающий алгоритм для
. Но
Таким образом, принципиально невозможно построить такую среду/оболочку/систему/IDE,
которая по коду данного ей произвольного алгоритма будет автоматически определять,
справедливо ли для него какоето специфическое свойство, каким бы простым и
очевидным это свойство ни было. В частности, неразрешима так называемая проблема
останова — не существует алгоритма, который по коду другого алгоритма
числу определил бы, остановится ли
и входному
на входе .
Примечательно, что огромное количество программистов, в глаза не видевших никогда теорию алгоритмов и theoretical computer science, свято уверены, что любую задачу на свете
можно решить и запрограммировать, были бы время и ресурсы.
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ
Материалы на данной страницы взяты из открытых истончиков либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.