АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ

АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ ПРОБЛЕМ. одно из основных понятий алгоритмов теории и ее приложений Возникло в связи с тем, чт о неразрешимость(и разрешимость) многих алгоритмических проблем устанавливается бо льшей частью не непосредственно, апутем сведения к исследуемой проблеме такой алгорит мич. проблемы, неразрешимость к­рой уже доказана(или исследуемой проблемы к нек­рой  уже решенной проблеме). Так, неразрешимость проблемы гомотопиипутей в полиэдре дока зывается путем сведения к ней проблемы равенства слов в соответствующейфундаменталь ной группе. Ниже приведены простейшие примеры А. с. теоретико­числовых (т. е. определенных на нат уральных числах)предикатов и функций: где Ри 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. 284­316; [3] Кleene S.C., PostE.L., "Ann.Math.", ser. 2, 1954, v. 59, №3, p. 379­407;  [4] Selman A. L., "Proc. bond. Math. Soc.", ser. 3, 1972, v. 25, № 4, p.586­602;  [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, Вена, Австрия, 6­11 августа 2001 г. Computability and Models, Алматы, Казахстан, 24­28 июня 2002 Logic Colloquium 2002, Мюнстер, Германия, 3­10 августа 2002 г. British Mathematical Colloquium 2003, Берингем, Великобритания, 7­10 апреля 2003 г. Алгебра и Анализ 2004, 2 ­ 9 июля 2004, Казань; Мальцевские чтения 2004, Новосибирск, 16­18 ноября 2004 г. Methods of Logic in Mathematics 2005, Санкт­Петербург, 18­24 июля 2005 г. Computational prospects of infinity, Сингапур, лето 2005 г. Мальцевские чтения 2005, Новосибирск, 15­17 ноября 2005 г. Computabilty in Europe 2006, Суонси, Великобритания, 30 июня ­5 июля 2006 г. Мальцевские чтения 2006, Новосибирск, 14­16 ноября 2006 г. Computabilty in Europe 2007, Сиена, Италия, 16­18 июня 2007 г. Мальцевские чтения 2008, Новосибирск, 11­13 ноября 2008 г. Итоговые научные конференции Казанского университета, 2002 ­2008. Результаты докладывались на семинаре Алгебра и логика (Новосибирск, ИМ СО РАН, рук. ­ академик Ершов Ю.Л.), логическом семинаре Отделения Математики университета  Лидса (Великобритания, рук. ­ проф. С. Вейнер, проф. C.B. Купер), логическом семинаре  математического факультета Висконсинского университета (США, рук. проф. С. Лемпп),  семинаре по теории вычислимости Чикагского университета (США, рук. проф. Р. Соар),  логическом семинаре математического факультета университета Ватерлоо (Канада, рук. ­  Р. Виллард). В целом работа доложена на семинаре по теории вычислимости на механико­ математическом факультете Казанского государственного университета (рук. ­ проф.  М.М.Арсланов). Автор выражает глубокую благодарность М.М. Арсланову за постоянное внимание к  работе и плодотворные беседы, способствовавшие улучшению диссертации. Список литературы диссертационного исследования доктор физико­математических  наук Калимуллин, Искандер Шагитович, 2009 год 1. Е. 3. Дымент; О некоторых свойствах решетки Медведева, Ма­тем. сборник, 101 (1976),  360­379. 2. Ю.Л. Ершов; Определимость и Вычислимость, Научная книга, Новосибирск, Экономика, Москва, 2000. 3. И.Ш. Калимуллин; Об элементарных теориях п­в.п. степеней по перечислимости,  Известия Вузов. Математика, № 4 (2001), 24­27. 4. И.Ш. Калимуллин, В.Г. Пузаренко; О сводимости на семействах, Алгебра и логика, № 1  (2001), 33­51. 5. Ю.Т. Медведев; Степени трудности массовых проблем, ДАН СССР, 104 (1955), 501­504. 6. A.A. Мучник; О сильной и слабой сводимости алгоритмических про­ блем, Сиб. матем.  журнал, 4 (1963), 1328­1341. 7. A.C. Морозов, В.Г. Пузаренко; О Е­подмножествах натуральных чисел, Алгебра и  логика, 43, №3(2004), 291 320. 8. М.Г. Розинас; Полурешетка е­степеней, Рекурсивные функции, Ива­ ново, Ивановский  гос. университет, 71­84, 1978. 9. В. Л. Селиванов; Об индексных множествах вычислимых классов конечных множеств,  Алгориты и Автоматы, под ред. М.М. Арсланова, Казань, 1978, 95­99. 10. А.И. Стукачев; О степенях представимости моделей. I, Алгебра и логика, 6 (2007), 763­ 788 11. S. Ahmad; Embedding the diamond in the E2 enumeration degrees, J. Symbolic Logic, 50  (1991), 195­212. 12. S. Ahmad, A.H.Lachlan; Some special pairs of E2 e­degrees properties of E2— enumeration  degrees, Math. Logic Quarterly, 44 (1998) ,431­449. 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. Springer­Verlag, 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), 503­513. 16. R. Downey; On presentations of algebraic structures, Complexity, Logic, and Recursion  Theory, ed. A. Sorbi (New York: Dekker, 1997), 157­205. 17. Richard J. Coles, R.G. Downey, T.A. Slaman; Every set has a least jump enumeration. J.  London Math. Soc., 62(2000), 641­649. 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),  219­246. 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), 324­348. 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), 71­113. 22. C.G. Jockusch, Jr.; Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc.,  131 (1968), 420­436. 23. C.G. Jockusch, Jr.; Degrees in which the recursive sets are uniformly recursive, Canad. J.  Math., 24 (1972), 1092­1099. 24. J.F. Knight; Degrees coded in jumps of orderings, J. Symbolic Logic, 51 (1986), 1034­1042. 25. K. McEvoy; Jumps of quasi­minimal enumeration degrees, J. Symbolic Logic, 50 (1985),  839­848. 26. K. McEvoy, S.B. Cooper; On minimal pairs of enumeration degrees, J. Symbolic Logic, 50  (1985), 983­1001. 27. R.G. Miller; The Ail­spectrum of a linear order, J. Symbolic Logic 66 (2001), 470­486. 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), 714­722. 30. L.J. Richter; Degrees of structures, J. Symbolic Logic, 46 (1981), 723­731. 31. H. Rogers, Jr.; Theory of Recursive Functions and Effective Computability, McGraw­Hill,  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), 226­238. 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), Springer­Verlag, Tokyo, 303­316. 36. T. Slaman; Relative to any nonrecursive set, Proc. Amer. Math. Soc., 126 (1998), 2117­2122. 37. R.I. Soare; Recursively enumerable sets and degrees, Heidelberg: Springer­Verlag, 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. 839­848. 40. I.N. Soskov; Degree spectra and co­spectra of structures, Ann. Univ. Sofia, 96 (2003), 45­68 41. S. Weimer; Enumerations, countable structures, and Turing degrees, Proc. Amer. Math. Soc., 126 (1998), 2131­2139. 42. C.E.M. Yates; On the degrees of index sets II, Trans. Amer. Math. Soc., 135 (1969), 249­ 266.Список публикаций автора по теме диссертации 43. Арсланов М.М., Калимуллин И.Ш., Купер С.Б. Свойства разложения тотальных  степеней по перечислимости // Алгебра и Логика. 2003. ­ Т. 42, № 1. ­ С. 3­25. 44. Калимуллин И.Ш., Пузаренко В.Г. О принципах вычислимости на допустимых  множествах // Мат. Труды. 2004. ­ Т. 7, № 2,­ С. 35­71. 45. Калимуллин И.Ш. Спектры степеней некоторых алгебраических структур // Алгебра и  Логика. 2007. ­ Т. 46, № 6. ­ С. 729­744. 46. Калимуллин И.Ш., Почти вычислимо перечислимые семейства множеств //  Математический сборник. 2008. ­ Т. 199, № 10. ­С. 33­40 47. Калимуллин И.Ш., Ограничения на спектры степеней алгебраических структур //  Сибирский мат. журнал. 2008. ­ Т. 49, №6.­ С. 1296­1309. 48. Калимуллин И.Ш., Пузаренко В.Г. О сводимости на семействах // Алгебра и логика  2009. ­ № 1. ­ С. 33­51. 49. Калимуллин И.Ш. Равномерность сводимостей алгебраических систем // Сибирский  мат. журнал 2009. ­ № 2. ­ С. 334­343. 50. Калимуллин И.Ш. Соотношения между алгоритмическими сво­димостями  алгебраических систем // Известия ВУЗов 2009. ­№6. ­ С. 71­72. 51. Kalimulllin I.Sh. Splitting properties of n­c.e. enumeration degrees //J. Symbolic Logic.  2002. ­ V. 67. ­ P. 537­546. 52. Kalimulllin I.Sh. Definability of the jump operator in the enumeration degrees //J.  Mathematical Logic. 2003. ­ № 2. ­P. 257­267. 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. 277­284. 54. Kalimullin I. Sh., Enumeration degrees and enumerability of familes // Journal of Logic and  Computation. 2009. ­ V.19. ­ № 1. ­ P. 151­158. 55. Арсланов M.M., Калимуллии И.Ш. Исследования по теории вычислимости //В книге  "На рубеже веков. НИИММ Казанского университета". Казань, изд­во Казан, матем.  общества. ­ 2003.­ С. 50­68. 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.  249­258. 57. Kalimullin I.Sh. On the problems of definability in the enumeration degrees // Lecture Notes  in Computer Science. 2005. ­ V. 3526. ­P. 221­222. 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 7­2006. ­ P. 150­159 59. Kalimullin I.Sh. Some notes on degree spectra of the structures // Lecture Notes in Computer Science. 2007. ­ V. 4497. ­ P. 389­398. 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.  568­578 Научная библиотека диссертаций и авторефератов  disserCat http://www.dissercat.com/content/algoritmicheskie­svodimosti­schetnykh­ algebraicheskikh­sistem#ixzz3R8smw2ou Формулировка теоремы Райса  Теорема Райса ЧРФ1,  ,  ЧРФ1,  , тогда   не является ЧРФ. Здесь   ­ характеристическая функция множества  . Другая формулировка теоремы Райса   ­ некоторое свойство одноместных интуитивно вычислимых функций. Назовем   существуют и функции, обладающие  Пусть  свойство  нетривиальным , если в множестве  этим свойством, и функции, не обладающие им. Тогда теорему Райса можно переформулировать так: Каково бы не было нетривиальное свойство  вычислимых функций, задача распознавания этого свойства алгоритмически  неразрешима.  одноместных интуитивно  Отсюда следует, в частности, что задача восстановления алгоритма по тексту программы  алгоритмически неразрешима. В рамках ликбеза в уютной жежешечке: теорема Райса Давайте рассмотрим все алгоритмы, существующие на свете, и попытаемся узнать, можно  ли автоматически, с помощью машины (т.е. опять же алгоритма) отвечать на какие­то  вопросы, касающиеся тех или иных алгоритмов. Рассмотрим два алгоритма  входе   они оба либо не останавливаются, либо выдают один и тот же ответ. . Назовем их эквивалентными, если на одном и том же   и  Любой алгоритм имеет текст. Текст алгоритма — строка в некотором ограниченном  алфавите. Так что мы можем выписать все строки, которые существуют в этом алфавите  (например, в лексикографическом порядке), этих строк счетное число, и можно  пронумеровать их последовательно натуральными числами. Некоторые из этих строк  представляют собой корректные алгоритмы, остальные же — "не компилирующиеся" —  будем считать алгоритмами, которые всегда зацикливаются. Итак, каждый алгоритм  получил свой уникальный номер. , либо оба не лежат в нем. . Назовем его инвариантным, если  Рассмотрим некоторое числовое множество  выполняется следующее свойство: номера любых двух эквивалентных алгоритмов либо оба лежат в  Например, множество "Алгоритмы, которые на входе 1 выдают 39" — инвариантно.  Аналогично инвариантными являются множества "Алгоритмы, которые останавливаются  хоть на каком­нибудь входе", "Алгоритмы, которые возвращают только четные числа",  "Алгоритмы, которые никогда не зацикливаются" и так далее. Фактически, понятие инвариантного множества можно представлять как  некоторое свойство алгоритма. Причем мы берем только свойства, характеризирующие  алгоритм как класс — зависящие от его входа, выхода и факта конечного времени работы.  Например, множество "Алгоритмы, выполняющие ровно 42 шага" — не инвариантно. Очевидно, если множество  инвариантно.  — инвариантно, то его дополнение   также   называется разрешимым, если для него можно построить разрешающий  , который для любого числа   на входе всегда останавливается и выдает 1,  Множество  алгоритм  если  Простой пример разрешимого множества — простые числа. Сюда же относятся четные  , и 0, если  . числа, любые конечные множества, все множество  Существуют также неразрешимые множества, но в данном посте этот вопрос затрагивать не стоит. , и еще многие различные примеры.  , в противном же случае ( , который принимает на вход число  , и   называется перечислимым, если для него можно  Множество  построить полуразрешающий алгоритм  возвращает 1, если  Понятно, что любое разрешимое множество является перечислимым: разрешающий  алгоритм легко превратить в полуразрешающий, добавив ему в конец вечный цикл вместо  возвращения значения 0. Гораздо интереснее вопрос "Существует ли перечислимое  неразрешимое множество?" Правильный ответ — да, существует, и не одно, однако  построение конкретных примеров тоже выходит за рамки данного поста. ) — зацикливается. Теорема Райса (в некоторых редакциях теорема Успенского­Райса) утверждает  поразительный факт: Любое нетривиальное свойство алгоритма является неразрешимым. Иными словами: Если некоторое инвариантное множество  либо   разрешимо, то имеет место  , либо  . Доказательство проведем методом от противного. Пусть существует разрешимое  инвариантное множество  , и оно нетривиально. Рассмотрим алгоритм  принадлежит классу  классе  . , который зацикливается на любом своем входе. Он либо  , либо его дополнению; пускай для определенности он лежит в  Поскольку множество  одно число:  .  по условию нетривиально, то в его дополнении лежит хотя бы   — какое­нибудь перечислимое неразрешимое множество. Мы знаем, что такие в  Пусть  принципе существуют, а какое это конкретно множество, здесь неважно. Построим специальную функцию. Она будет принимать на вход два числа  себя следующим образом. Если  вычисления зацикливается). Иначе же мы берем алгоритм под номером   (номер мы  выбрали ранее из дополнения), и запускаем его на входе  . Если обозначить через   и  , и ведет  , то значение функции не определено (алгоритм её алгоритм под номером  , то данную функцию можно записать аналитически: Понятно, что эта функция является вычислимой, то есть для нее существует  соответствующий алгоритм вычисления значения. Возьмем полуразрешающий алгоритм  для  алгоритм никогда не остановится, что нам, собственно, и нужно. , если он выдал единицу — запустим алгоритм  , иначе полуразрешающий  Теперь зафиксируем один из параметров функции  аргумента   с параметром  , или  переписать следующим образом: , превратив её в функцию от одного  . Её определение как алгоритма теперь можно  Действительно, в одном случае она тождественно совпадает с алгоритмом  другом — с никогда не останавливающемся алгоритмом  . , а в  У  , как у любого алгоритма, есть свой номер. Обозначим его  . , то  Итак, если  случае они эквивалентны. По определению инвариантного множества  в   ведет себя так же, как и алгоритм  , как и число  . , а стало быть, в этом   тоже лежит  , как и   — множество разрешимое, а значит, существует алгоритм, который  Но  для любого числа   может за конечное время подтвердить либо опровергнуть  факт  эквивалентного факта  — множество неразрешимое. Пришли к противоречию. . Тогда такой алгоритм будет одновременно определять истинность  , и значит, подходит как разрешающий алгоритм для  . Но    Таким образом, принципиально невозможно построить такую среду/оболочку/систему/IDE, которая по коду данного ей произвольного алгоритма будет автоматически определять,  справедливо ли для него какое­то специфическое свойство, каким бы простым и  очевидным это свойство ни было. В частности, неразрешима так называемая проблема  останова — не существует алгоритма, который по коду другого алгоритма  числу   определил бы, остановится ли   и входному   на входе  . Примечательно, что огромное количество программистов, в глаза не видевших никогда теорию алгоритмов и theoretical computer science, свято уверены, что любую задачу на свете можно решить и запрограммировать, были бы время и ресурсы.