Структурные свойства тьюринговых степеней множеств из иерархии Ершова тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Ямалеев, Марс Мансурович

• Ямалеев, Марс Мансурович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Ямалеев, Марс Мансурович

Введение

Глава 1. Разложимость 2-в.п. степеней с избеганием конусов

§1.1. Достаточные условия избегания верхнего конуса Д^-степени

§1.2. Разложимость и изолированность.

Глава 2. n-низкие в.п. и n-низкие 2-в.п. степени не являются элементарно эквивалентными

Глава 3. Сильная недополняемость в низких в.п. степенях

Введение диссертации (часть автореферата) на тему «Структурные свойства тьюринговых степеней множеств из иерархии Ершова»

Тьюринговая, или алгоритмическая, сводимость является одной из самых естественных и важных сводимостей, рассматриваемых на классе подмножеств множества натуральных чисел и. Интуитивно, множество А сводится по Тьюрингу к множеству В, если мы, умея распознавать элементы множества В, можем эффективно распознавать элементы множества А. Хорошо известно, что все тыорииговые степени D образуют верхнюю полурешетку D(<r,U). Локальная теория вычислимости изучает D(<t О', U) (или Д^-степени), т.е. тыоринговые степени расположенные ниже 0', которые также образуют верхнюю полурешетку. Диссертационная работа посвящена изучению структурных свойств верхних полурешеток n-вычислимо перечислимых (далее, п-в.п.) тьюринговых степеней (далее, Т-степеней, или степеней) для различных натуральных п > 0. Степень называется п-в.п., если она содержит п-в.п. множество, если она при этом не содержит (п — 1)-в.п. множеств, то она называется собственной п-в.п. степенью.

Изучению верхних полурешеток тыоринговых степеней, состоящих из конечных булевых комбинаций перечислимых множеств, посвящены многие работы. В трудах Арсланова, Доуни, Ейтса, Калимуллина, Купера, Лахлана, Лемппа, Ли, Сакса, Соара, Харрингтона исследуются различные свойства разложимости, изолированности, дополняемости и недополняемости для степеней из этих структур.

Степень а называется разложимой в классе степеней С, если существуют степени xo,xi G С такие, что а < хо Uxi и Xo,Xi < а. При рассмотрении конечных уровней иерархии Ершова если класс С не упоминается, то 3 будем считать, что разложение проводится на том же уровне. При изучении свойств разложимости возникают два типа дополнительных вопросов: разложение одних степеней над другими и разложение степеней с избеганием верхних конусов других степеней. Пусть даны степени 0 < b < а, и имеется разложение а = х0 U xi. Если b < Xj (i = 0,1), то говорим, что степень а разложима над степенью Ь; если b ^ Xi (г = 0,1), то говорим, что а разложима с избеганием верхнего конуса Ь. В обоих случаях представляет интерес хотя бы одно разложение с требуемыми свойствами. Как увидим далее, ни один этих вопросов не является тривиальным. Также будем считать, что разлагаемая степень расположена сверху, если это не указано явно.

Свойства разложимости первым начал изучать Сакс [1]. Теорема Сакса о разложении гласит, что произвольная невычислимая в.п. степень может быть разложена в классе низких в.п. степеней с избеганием верхнего конуса произвольной в.п. степенью. Отметим, что доказательство переносится на случай избегания конуса произвольной А^-степени. Позднее, Робинсон

2] доказал, что произвольную невычислимую в.п. степень можно разложить над произвольной низкой в.п. степенью.

Спустя некоторое время Арсланов, Купер и Ли получили серию результатов о разложимости на более высоких уровнях иерархии Ершова. Купер

3] доказал, что произвольная невычислимая 2-в.п. степень разлагается в классе 2-в.п. степеней; Купер и Ли [4] доказали, что произвольная 2-в.п. степень разлагается над произвольной в.п. степенью; Арсланов, Купер и Ли [5-6] доказали, что произвольная в.п. степень разлагается в классе 2-в.п. степеней над произвольной низкой 2-в.п. степенью. Вопросы разло4 жимости одних степеней над другими представляют до конца не изучены даже для класса 2-в.п. степеней, до сих пор открыт вопрос о разложимости 2-в.п. степени над произвольной низкой 2-в.п. степенью.

Другим направлением является разложимость с избеганием конусов. Это направление также представляет интерес. При доказательстве определимости оператора скачка в структуре степеней неразрешимости Купером [7] была доказана Основная теорема, которая гласит, что существует 2-в.п. степень d, которая не может быть разложена над некоторой степенью а < d, избегая верхний конус некоторой степени b ^ а. Разложение проводится в классе Д^-степеней, степени а и b также строятся в классе Д^-степеней. Однако, позднее Сламан и Шор [8] доказали теорему, частным случаем которой является тот факт, что любую 2-в.п. степень d можно разложить в классе ДЦ-степеней над произвольной степенью а < d, избегая верхний конус произвольной степени b ^ а. Этим они опровергли Основную теорему Купера. Отметим, что в этих работах прослеживается связь вопросов разложимости с избеганием конусов и вопросов определимости.

Если пытаться проводить разложение 2-в.п. степени в классе 2-в.п. степеней, избегая верхний конус 2-в.п. степени, то, вообще говоря, это не всегда удается. Например, из работы Арсланова, Калимуллина и Лемппа [9] или теоремы 2.1 следует, что существует пара 2-в.п. степеней, образующих "восьмерку" 3 х, у {[0 < х < y]AV z [z < у —> [z < xVx < z]]}, где все кванторы берутся по классу 2-в.п. степеней. Очевидно, что любое разложение степени у будет разложением над х. Если взять две собственные 2-в.п. степени, то может оказаться так же: достаточно рассмотреть пару yi < у и х. Существование такой собственной 2-в.п. степени yi следует из известной теоремы Лахлана (о существовании в.п. степени под каждой собственной 2-в.п. степенью) и из теоремы Купера, Лемппа и Уотсона [10] о слабой плотности, а собственность степени х следует из теоремы Сакса [1] о разложении в.п. степеней. Отметим, что из теоремы Купера и Ли [11] следует, что вопрос разложимости п-в.п. степеней с избеганием конусов при произвольных n > 1 также не тривиален.

Как видно, если пытаться доказывать теорему Сламана и Шора, разлагая степень d в классе 2-в.п. степеней над вычислимой степенью, то нужны дополнительные условия. Автором найдено достаточное условие (см. теорему 1.1) для разложения собственной 2-в.п. степени с избеганием верхнего конуса другой собственной 2-в.п. степени. Кроме того, с одной стороны теорема 1.1 обобщает теорему Купера [3] о разложении 2-в.п. степеней, с другой стороны она обобщает теорему Сакса [1] о разложении в.п. степеней с избеганием конусов. Таким достаточным условием является изолированность, что в этой работе означает отсутствие в.п. степеней между двумя сравнимыми Д^-степенями. Также была проверена возможность характеризации разложимости в терминах изолированности, и доказано (см. теорему 1.2), что изолированность не является необходимым условием. Свойство изолированности в различных смыслах (сверху, свнизу и между различными степенями) изучалось Купером и Ли [12], Ефремовым [13-14], By [15].

В последние несколько десятилетий в теории вычислимости особый интерес представляют теоретико-модельные аспекты различных структур. Многие крупные проблемы для Т-степеней на сегодняшний день связаны с вопросами определимости и элементарной эквивалентности. Изучение структурных свойств нередко приводит к нахождению различий в элементарных теориях изучаемых структур.

Например, изучая вопросы дополняемости в 2-в.п. степенях и используя теорему Купера и Ейтса [16] о недополняемости в в.п. степенях, Арсланов [17-18] доказал различие элементарных теорий верхних полурешеток в.п. и п-в.п. степеней при любом п > 1. Затем Доуни [19] выдвинул гипотезу о том, что элементарные теории п-в.п. и тп-в.п. степеней при различных n, т > 1 совпадают. Однако Арсланов, Калимуллин и Лемпп [9] доказали, что верхние полурешетки 2-в.п. и 3-в.п. степеней не являются элементарно эквивалентными (для общего случая вопрос до сих пор остается открытым). Для этого они построили слабую "3-восьмерку" в классе 3-в.п. степеней. Введенное ими понятие "восьмерки" (или "2-восьмерки") и сама конструкция оказались полезными для изучения и других тоеретико-модельных свойств структур, образованных п-в.п. степенями при различных п > 1.

Будем говорить, что невычислимые степени а и b образуют "восьмерку" в классе степеней С, если степени a, b G С, степень b находится строго ниже а, и любая степень из класса С, которая ниже а, будет сравнима с Ь. Во второй главе диссертации (см. теорему 2.1) доказывается существование невычислимых низких 2-в.п. степеней, образующих "восьмерку" в классе 2-в.п. степеней. Этот результат вместе с теоремой Сакса [1] о разложении в.п. степеней позволяет получить различие элементарных теорий частичных порядков низких в.п. и низких 2-в.п. степеней (см. следствие 2.1). Кроме того, поскольку каждая низкая степень является и п-низкой для любого п > 1, то теорема и следствие верны, если условие низости заменить на условие n-низости (для произвольного п > 1, также см. следствие 2.2). Для случая п — 2 вопрос об элементарной эквивалентности частичных порядков неоднократно ставился в работах Доуни [20-21] и до сих пор оставался открытым.

Вопросы разложимости и конструкция "восьмерки" оказываются тесно связанными. Действительно, "восьмерка" показывает, что не всегда удается провести разложение с избеганием заданного верхнего конуса и что этот вопрос не является тривиальным. С другой стороны возможность разложения с избеганием конусов накладывает некоторые ограничения на компоненты "восьмерки". В частности получаем, что середина "восьмерки" (в классе 2-в.п. степеней) имеет в.п. степень.

Будем говорить, что невычислимые степени ах, а.2, ., ап образуют "n-восьмерку" (п > 2) в классе степеней С, если дц € С, (г = 1 ,.,п), ai < а.2 < . < ап, степени ах, аг, ., апх образуют "(п — 1)-восьмерку"и любая степень из класса С, которая ниже ап, будет сравнима с ап!. По определению положим, что "2-восьмерка" есть обычная "восьмерка". Вышеупомянутый результат о разложимости 2-в.п. степеней с избеганием конусов позволяет получить, что не существует "З-восьмерки" в классе 2-в.п. степеней. Обобщение результата о разложимости 2-в.п. степеней с избеганием конусов на п-в.п. степени (соответственно, здесь будет изолированность в (п — 1)-в.п. степенях) позволяет аналогичным образом получить, что не существует "n-восьмерки" в классе (п— 1)-в.п. степеней. Более того, получаем сильные ограничения на степени зц{г = 1,.,п) в случае, если они образуют "n-восьмерку" в классе п-в.п. степеней, а именно: степени дц будут г-в.п. для всех г = 1 ,.,п. Таким образом, если удастся доказать существование "n-восьмерки" в классе п-в.п. степеней, то набор составляющих степеней будет единственным, и вкупе с тем, что не существует "n-восьмерки" в классе (п — 1)-в.п. степеней, в качестве следствия получим, что верхние полурешетки п-в.п. и m-в.п. степеней не являются элементарно эквивалентными для всех n, т > 1 и п ф т. Это опровергнет гипотезу Доуни для всех п,ш > 1.

Возвращаясь к изучению структурных свойств, сделаем небольшой исторический обзор по вопросам дополняемости и недополняемости. В 1960-х годах Шенфилд сформулировал свою знаменитую гипотезу о том, что класс в.п. степеней R, рассматриваемый как верхняя полурешетка, является плотной структурой. Эта гипотеза имеет два интересных следствия, и одно из следствий гласит: для любых в.п. степеней 0 < b < а существует в.п. степень с < а, что а = b U с. Позднее выяснилось, что это следствие неверно, однако оно привело к интенсивному изучению вопросов дополняемости и недополняемости, и вскоре был получен ряд интересных результатов.

Пусть тьюринговые степени а и b такие, что 0 < b < а. Назовем b недополняемой до а в классе степеней С, если не существует w £ С такой, что w<aHa = bUw, и назовем b сильно недополняемой до а в классе степеней С, если не существует w G С такой, что а ^ w и а < b U w.

Одним из первых результатов о недополняемости является теорема Купера и Ейтса [16], где установлено существование невычислимой в.п. степени, недополняемой до 0' в классе R. Немного позднее Харрингтон [16] 9 усилил этот результат, доказав, что для любой высокой в.п. степени h существует высокая в.п. степень, которая сильно недополняема до h в классе R. Затем Купер [22] и Сламан и Стил [23] доказали, что существуют невычислимые в.п. степени b < а такие, что степень b недополняема до степени а в классе Д^-степеней.

С этими теоремами контрастирует другой результат Харрингтона [24], известный как "Плюс-наверх теорема", и показывающий, что некоторые в.п. степени всегда будут дополняемы до определенных в.п. степеней в классе R.

Теорема (Харрингтон). Существует невычислимая в.п. степень а, что для любой невычислимой в.п. степени b < а и для любой в.п. степени d > а существует в.п. степень с < d; что bUc = d.

Изучая вопросы дополняемости для 2-в.п. степеней в классе 2-в.п. степеней, Арсланов [17-18] доказал следующую теорему.

Теорема (Арсланов). Для любой невычислимой 2-в.п. степени b существует неполная 2-в.п. степень d такая, что 0' = b U d.

Отсюда как следствие получаем, что полурешетки в.п. и 2-в.п. не являются элементарно эквивалентными. Позднее теорему Арсланова следующим образом обобщили Купер, Лемпп и Уотсон [10).

Теорема (Купер, Лемпп и Уотсон). Для любой высокой в.п. степени h, для любой невычислимой п-в.п. (п > 1) степени b < h существует низкая 2-в.п. степень d такая, что h = b U d.

В главе 3 (см. теорему 3.1) доказывается существование низких невычислимых в.п. степеней b < а таких, что b сильно недополняема до а в классе в.п. степеней.

В.п. степень а называется почти глубокой, если (aUw)' = 0' для любой низкой в.п. степени w. Грожек, Сламан и Чолак [25] доказали существование почти глубокой степени. Анализ их конструкции показывает, что в теореме 3.1 степень b также можно сделать почти глубокой, однако это сильно усложнит доказательство. Это дополнение вместе с вышеупомянутой теоремой Купера, Лемппа и Уотсона позволяет получить элементарное различие частичных порядков низких в.п. и низких 2-в.п. степеней другим путем. Независимо от автора Файзрахманов [26] также получил этот результат в качестве следствия. Однако, оба эти подхода не обобщаются непосредственно на случай n-низких степеней, как в случае с теоремой 2.1. Отметим, что во всех трех случаях доказательства элементарного различия частичных порядков низких в.п. и низких 2-в.п. степеней используются принципиально разные подходы.

Итак, основные результаты диссертации:

- Сформулировано и доказано достаточное условие для возможности разложения собственной 2-в.п. степени с избеганием верхнего конуса произвольной Аз-степени. Тем самым доказан специальный случай теоремы Сламана и Шора и в разных смыслах обобщены теорема Купера о разложении 2-в.п. степеней и теорема Сакса о разложении в.п. степеней с избеганием конусов.

- Доказано существование двух низких невычислимых 2-в.п. степеней d и е таких, что 0 < d < е и для любой 2-в.п. степени w выполняется: [w < е —> [w < d V d < w]]. В качестве следствия получаем различие элементарных теорий частичных порядков п-низких в.п. и n-низких 2-в.п. степеней для любого натурального п > 0.

- Доказано свойство сильной недополняемости в низких в.п. степенях.

В доказательствах теорем 1.1, 2.1 и 3.1 используется техника метода приоритета с бесконечными нарушениями, изложенная на деревьях. Причем в теоремах 2.1 и 3.1 каждая вершина, отвечающая некоторому положительному требованию, либо со временем инициализируется, либо удовлетворится и, начиная с некоторого шага, прекратит свою работу. Это позволяет определенным образом вставить в конструкции стандартное требования низости.

Теперь скажем о некоторых определениях, сокращениях и договоренностях, используемых в дальнейшем. Некоторые специальные определения приведем еще раз в главах.

Множества, рассматриваемые ниже, являются подмножествами множества натуральных чисел и = {0,1, 2,.}. У функций, рассматриваемых ниже, если специально не оговорено другое, область определения и область значения являются подмножествами со. Греческими буквами и малыми латинскими буквами обозначаются функции, большими латинскими буквами обозначаются множества и характеристические функции этих множеств, т.е. если А С w, то обозначает следующую функцию:

Если А С со, то А и со — А обозначают разность to \ А. Если А, В С ш, то через А — В обозначается разность А \ В, а через А © В - множество {2х\х G A} \J{2x 4- 1\х € В}. Мощность множества А обозначается через \А\. А=* В означает, что \(А- В) [J(£ -А) | < оо.

О, если х £ А.

1, если х € А,

Пусть Фо, Фь Ф2,. - некоторая эффективная нумерация всех частично-вычислимых (ч.в.) функций, тогда Wq, W\, W2,. обозначает соответствующую ей эффективную нумерацию вычислимо перечислимых (в.п.) множеств. Аналогично, если Ф^,Ф^,Ф2,.- - некоторая эффективная нумерация частично вычислимых относительно множества А функций, то . обозначает соответствующую ей нумерацию множеств, вычислимо перечислимых относительно множества А. Вычислимыми функциями называем ч.в. функции, область определения которых совпадает с со. Через {Dn}nSLJ обозначаем стандартную нумерацию всех конечных подмножеств си, т.е. Dq = 0, и если .,хп - различные числа из ш и х = 2Xl + . + 2хто Dx = {ж1}., хп}.

Результат, полученный к концу шага s в процессе вычисления Ф^(гс) обозначаем через (или также Фе(А;ж)[5]). Например, если множество А в.п. (или допускает какую-нибудь пошаговую аппроксимацию), то эта запись означает результат, полученный за s шагов работы е-ой машины Тьюринга на входе х с оракулом последнее означает подмножество множества А, перечисленное к концу шага s (соответственно, аппроксимацию множества А к концу шага s). Если Фе(А;х) определена, то значение ее wse-функции записывается как ipe(A,x). По определению, <ре(А, ж) = 1+ наибольшее число, использованное в этом вычислении. Аналогично определяется tpe(A,x)[s\.

Запись / f х означает ограничение функции / к числам у < х. Таким образом, если Ф^(ж) определена, тогда значение ее ияе-функции равно А \ ipe(A,x), и изменение А в промежутке < ipe(A,x) разрушает это вычисление.

Двухместная функция (х, у), определенная как (х, у) := +Зж+г/ дЛЯ х, у Е о;, и осуществляющая биективное отображение си2 на а;, называется канторовской нумерующей функцией. Через I и г обозначаются однозначно определенные функции такие, что для всех х,у G ш, (1(х),г(х)) = х: 1({х,у)) = х,г((х,у)) = ?/; n-местная функция (жх,. ж^) при п > 2 определяется так: (a?i,. хп) = {(. (х\, жг), ж3),., жп). Если функция / в точке ж определена, то пишем /(ж) j, в противном случае пишем f(x) j. Область определения функции / обозначается через dom(f), область ее значений - через rng(f).

Множество А называется 2-СЕА множеством, если существует такое в.п. множество В <т А, что А = Wf для некоторого е.

Множество А сводится по Тьюрингу (или Т-сводится) к множеству В (А <т В), если (3n)(V:r)(A(:r) = где Ф^ - некоторая вычислимая относительно В функция.

Множество А называется п-в.п. множеством (или принадлежит классу Е"1) для некоторого п > 1, если существует вычислимая функция f{s,x) такая, что для каждого х : /(0,30 = 0, А{х) = limSf(s,x), и \{s: f(s,x)^f(s + l}x)}\<n.

Степень а называется п-в. п. степенью для n > 1, если она содержит п-в. п. множество, и она называется собственно п-в. п. степенью, если она содержит п-в. п. множество, но не содержит т-в. п. множеств для 771 < п.

Для произвольного множества А обозначим через А' = {х\Ф^{х) |} его

14 скачок. Множество А назовем низким (высоким), если А' <т О' (О" <т А!).

Напомним некоторые соглашения и обозначения, которые используются в приоритетных конструкциях на деревьях.

Если задано дерево Т = А<ы с конечным или бесконечным алфавитом Л, и на множестве Л введен линейный порядок <л, то будем рассматривать следующие отношения на множестве Т:

1. и <л т, если существуют такие a £ Т и а <д Ь, что а С а и оГЪ С г.

2. <т <л г, если либо а <л т, либо а = г.

Далее в доказательствах, индекс Л будем опускать, а при инициализации некоторой вершины будем автоматически инициализировать все вершины, которые ее расширяют.

Требования типа Vy (или Se) будем называть Р-требованиями («5-требованиями, соответственно), и в дальнейшем, специально не оговаривая, будем опускать индексы, когда понятно о каком именно требовании идет речь. Индексы требований в зависимости от теоремы будем обозначать либо натуральными числами, либо непосредственно множествами или функционалами.

Под "большим" числом, как обычно, будем подразумевать первое еще не упомянутое в конструкции число. Также, когда из контекста понятно о чем идет речь, будем употреблять термины вершина, стратегия, требование, как синонимы. Например, "требование действует" означает "стратегия требования действует", "вершина переходит из пункта (1) в пункт (2)" означает "стратегия вершины переходит из пункта (1) в пункт (2)" и т.п.

Во всех конструкциях у каждого требования будут стратегии, или стратегия, которые это требование удовлетворяют. Каждая стратегия имеет пункты, и в процессе конструкции будет указываться, когда стратегия переходит из одного пункта в другой. В конструкциях при описании действий, иногда будем ссылаться на базовые модули.

Запись "ж A[s]" ("ж \ A[s]") означает, что элемент х на шаге s + 1 покидает (перечисляется в) множество А, или также пишем х 6 As — As+i (a: 6 ^s+i — As). Иногда будем опускать индексы или аргументы, когда они восстанавливаются однозначно из контекста.

Основные определения и результаты, касающиеся данной тематики, могут быть найдены в книгах [24], [27-31].

Нумерация теорем, следствий и определений отдельная для каждой главы. Например, запись "теорема 3.1" и "следствие 2.2" означает, что теорема является первой по счету теоремой в третьей главе, а следствие является вторым по счету следствием для второй главе.

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Ямалеев, Марс Мансурович

Выходы:

A. Бесконечное ожидание в пункте (1). Требование в данном случае удовлетворяется, т.к. левая часть импликации требования будет ложна.

B. Успешное завершение работы. Требование в данном случае также удовлетворяется, ибо после запрещения use-функции множества А функ

55 ционал в точке е будет определен, и, соответственно, правая часть импликации будет истинна.

Требования Ve и J\fe в отдельности удовлетворяются за конечное число шагов, т.е. начиная с некоторого шага данные требования не будут ничего перечислять или запрещать новые интервалы. Перечислить что-либо в множество А могут лишь V- требования, и при этом Л/*-требования не конфликтуют с ^-требованиями. Поэтому, если требования типа Ve будут удовлетворяться (с учетом 7£-требований) через конечное число шагов, то требования типа Afe также удовлетворятся через конечное число шагов. Таким образом, если мы сможем удовлетворить требования типа Ve через конечное число шагов при работе их модифицированных стратегий, то М-требования также удовлетворятся — их достаточно легко будет встроить в конструкцию из стратегий типа 7Ze и Ve- Поэтому вплоть до конструкции будем рассматривать лишь требования типа Ле и Ve и соответствующие конфликты между ними.

Взаимодействие требований.

Поскольку конструкцию будем проводить используя деревья, то сначала рассмотрим ^-стратегии, которые имеют со + 2 выхода: конечный выход '/т' (соответствует А); успешное построение функционала Г, выход 'ш' (соответствует С); остальные со выходов — это скачки соответствующих циклов, обозначим 0,1, 2,. (случай В).

Выходы будут упорядочены следующим образом: 0 < 1 < 2 < . < uj < fin. При таких выходах удобней рассматривать характерные трудности, но в итоге у нас останется 2 выхода, одним из которых является вышеприведенный конечный, а второй будет содержать все оставшиеся выходы. Требования вида Ve и J\fe будут иметь всего один выход. Так как они будут удовлетворяться через конечное число шагов, то они в процессе своего удовлетворения могут просто инициализировать все вершины, которые их расширяют.

Очевидно, нет трудностей, когда некоторое требование Vc имеет приоритет более высокий, чем некоторое требование 1Zi, поэтому рассмотрим сначала случай, когда одно Р-требование находится под одним 1Z-требованием (индексы в дальнейшем будем опускать).

Требование V под требованием TZ. Понятно, что трудностей не возникает под выходами fin и 0,1,2,.: в этом случае мы априори знаем запрет на множество В. Но при выходе ш запрет на множество В может постоянно увеличиваться из-за появления новых циклов. Согласно стратегии 7Z запрет на множество В нужен для поддержания корректности Г, и если некоторый к не будет перечислен в Л, то цикл к может сбросить свои запреты. Множество А мы перечисляем сами, поэтому можем ограничиться рассмотрением запретов тех циклов, номера которых равны в(х), где х является свидетелем некоторого Р-требования. Таким образом, в случае одного Р-требования конфликт возникает только из-за того, что в множество А может перечислиться номер цикла 9(х) = ао, где х — свидетель требования Р. Предположим, что мы уже находимся в пункте (3) требования Р, и х запрещен циклом ао, тогда мы перечисляем 9{х) в А и определяем ЭА(ж) = В(х) = 0 с "большим" в(х) = ai, в частности а\

57 больше, чем номера циклов, которые открыты к этому моменту требованием 7Z. Перечисление ао в А вызывает неравенство в левой части R, и запрет на В позволяет сохранить это неравенство, если только не перечислится элемент в W. Это заставит измениться $Wei?(ao), и тогда можно будет сбросить запрет с множества В. Когда в следующий раз мы опять начнем работать с требованием V, то у требования 1Z на дереве стратегий будет выход со, циклов прибавится не более, чем на один, и запрет будет сброшен. То есть теперь мы сможем перечислить в(х)(= ai) в А, х перечислить в В, не нарушая запрета, и определить Ол(х) = В(х) — 1 с тем же 6(х) = а\. Таким образом преодолевается эта трудность. Перейдем к рассмотрению второй трудности, которая возникает при взаимодействии одного "Р-требования с несколькими ^-требованиями более высокого приоритета.

Требование V под требованиями IZo и TZ\. Новая трудность возникает лишь в случае, когда оба 7£-требования имеют выходы со, и пока для удобства будем считать, что этим требованиям соответствует одноименные вершины на дереве стратегий: вершина TZi находится под со выходом вершины TZq, а вершина V находится под со выходом вершины TZ\. Может оказаться так, что, пока мы заставляем одно из требований сбрасывать запрет, другое требование открывает новые циклы и налагает новые запреты. Предположим, что мы уже находимся в пункте (3) требования V, тогда мы, как и в предыдущем случае, перечисляем 9(х)(— ао) в А и определяем Вл(х) = В(х) = 0 с "большим" 9(х) = а\. Опять начав работать с "Р, мы не определяем функционал Ti в точке ао, но вместо этого делаем вершину помощником вершины V. Смысл помощника

58 в конструкции будет в том, что после работы с вершиной, являющийся помощником, мы обязательно попадем к вершине, чьим помощником она является, при этом стратегии вершин-помощников не производят никаких действий (поэтому, поддерживая функционал Ti неопределенным, мы можем необходимое время держать запрет сброшенным). Получаем, что х может находиться под запретом только у требования TZq. Теперь мы еще раз перечисляем в(х)(= а\) в А, не перечисляя хв В, м полагаем 9{х) = а2, где «2 "большое" число. После того, как требование IZq после ожидания вернется на выход со, мы начнем работать с 7Zi, а поскольку IZi является помощником, то перейдем сразу же к V (в формальной конструкции все 7£-вершины между TZ\ и V будут помогать V, также мы докажем, что ни одна вершина не будет вечным помощником). Таким образом, у запрет будет сброшен, а у 71\ запрет будет поддерживаться сброшенным, следовательно, свидетель требования V больше не будет запрещен циклом в(х)(— аг) ни одного 7£-требования, и мы сможем перечислить 6{х) в А, перечислив х в В. После удовлетворения требования V мы освобождаем его помощников, подразумевая под этим, что они перестали быть его помощниками. Аналогичным образом преодолевается трудность, когда над одним Р-требованием находится несколько "/^.-требований: мы соответствующее число раз будем перечислять в(х) в А, постепенно увеличивая количество помощников требования V.

Недостаток приведенной стратегии заключается в следующем: если истинным выходом будет выход и), то может оказаться, что каждый цикл г будет скакать некоторое число раз, и таким образом мы будем попадать на выходы г и должны будем по идеологии метода деревьев постоянно инициализировать все вершины, находящиеся справа и, в частности, под со. Для преодоления этого недостатка мы объединили выходы 0,1, 2,., со в один выход inf, т.е. если некоторая 7£-стратегия имеет на некотором шаге один из выходов 0,1, 2,., со, то на этом шаге на дереве стратегий мы покажем выход inf. Таким образом, у нас останется лишь два выхода: конечный (fin) и бесконечный(inf). Наша техника позволяет Р-стратегиям действовать единым образом под выходами 0,1,2,., со, но, прежде чем перейти к конструкции, опишем новые трудности, которые возникают при использовании двух выходов у ^-стратегий. lZ-стратегия с двумя выходами. Опять же будем рассматривать лишь случаи, когда 7£-требоваиия имеют более высокий приоритет, чем Р-требование. Если у нас будет несколько ^-требований и одно V-требование, то трудность будет такая же, как в случае с со + 2 выходами. Требование V контролирует единственный запрещающий цикл всех 7Z-требований, и в отличие от предыдущего случае мы должны учитывать скачки этого цикла. Но скачки этого цикла могут лишь увеличивать запреты, и это не создает дополнительных трудностей. Перейдем к ключевому моменту нашей теоремы и опишем трудности, возникающие при взаимодействии двух Р-требований с одним и двумя ^-требованиями более высокого приоритета.

Требование V\ под требованием Vq, которое в свою очередь под требованием Л. Может оказаться так: требование Vq ожидает и находится в пункте (2), требование V\ завершило ожидание, и в(хо) < в(х±). Требование Vi не может нарушить запрет цикла в(хо), если оказалось, что меньше этого запрета (т.к. требование Vq в любой момент может завершить ожидание и перечислить 9{хо) в Л, и при этом требование 7Z не сможет поправить свой функционал Г в точке 9{хо)). Но х\ будет меньше указанного выше запрета только в том случае, когда после назначения Х\ в качестве свидетеля скакнул цикл с номером в(хо), увеличив свой запрет. Поэтому в момент скачка цикл с номером 9(хi) берет под контроль цикл с номером 9(xq), что означает, что мы увеличиваем use-функцию функционала Г в точке 9(xq) и полагаем ее не меньше, чем ry(9(xi)). То есть теперь, перечислив 9{хi) в А, мы заставляем Г(0(жо)) стать неопределенным (в противном случае произойдет диагонализация и требование 7Z также удовлетворяется), перечисляем х\ в В (и, соответственно, новый 9{х\) перечисляем в А), и, только дождавшись, когда определится <&B®W{9{хо)), определяем Г(0(жо)). Итак, мы смогли удовлетворить требование V\ без вреда для остальной конструкции (т.е. у нас будут удовлетворены и два других требования: Vq и 7Z). Требование V\ под требованием Vq, которое в свою очередь под требованиями 7Z\ и TZq. Пусть у требований Vq и V\ свидетели xq и соответственно, пусть 9{хо) = а[] и 9{хi) = а^, пусть to(k) и t\(k) являются идентификаторами для требований 7Zq и 7Z\, соответственно. Идентификатор для "^.-требования — это неубывающая по шагу функция, которая в начале работы соответствующего "^.-требования тождественна. Позднее некоторый идентификатор будет увеличиваться в точке к при скачке цикла с номером к (а также при его первом открытии), и при увеличении он будет приравнен "большому" числу. Смысл идентификатора для некоторого 7£-требования будет в том, что в первом пункте этого требования мы будем ожидать определенности функционала Ф не только в точке но и

61 на целом интервале [к, t(k)] несмотря на то, что циклы с номерами большими, чем к еще, не открыты. После завершения ожидания мы определяем для функционала Г в точке к wse-функцию равную 7(к) — cp(t(k)). Поэтому теперь, перечислив в множество А любой номер цикла п, где к < п < t(k), мы либо диагонализируем данное 7£-требование, либо заставляем измениться W \ (p(t(k)) (при условии, что соответствующий начальный сегмент множества В будет под запретом), другими словами, при надобности мы можем сделать Г в точке к неопределенным. Это означает, что мы можем на некоторое время снять запреты с соответствующего начального отрезка множества В, запрещенного циклом к. В самой конструкции манипулирование сбрасыванием запретов и позволяет Р-требованиям постепенно преодолевать запреты 7£-требований с более высоким приоритетом. Отметим также, что если каждый цикл некоторого 7£-требования будет скакать лишь конечное число раз, то и идентификатор данного требования в каждой точке перестанет со временем увеличиваться, соответственно, мы сможем корректно определить функционал Г в каждой точке.

Вернемся к нашему частному случаю. Итак, пусть требование Vq удовлетворяется бесконечным ожиданием в пункте (2). Поскольку мы постоянно должны иметь ввиду, что оно может завершить это ожидание, то требование V\ вынуждено учитывать запреты циклов с номером 9(хо) у требований IZq и Предположим, мы уже назначили свидетеля Х\, который больше, чем эти запреты, и начинаем ожидание в пункте (2). При этом у требования IZq цикл с номером 0(хо) либо еще не открывался, либо ожидание в его первом пункте завершилось до назначения свидетеля х\ (т.е. xi больше запрета цикла с номером #(ссо), или в терминах идентификаторов (p(t(9(xо))) < х{), либо это ожидание завершилось после назначения свидетеля Х] (значит, цикл с номером 9(хо) уже находится под контролем цикла с номером 9{хi), или также 9{х\) < t(9(xо))). Если цикл с номером 9(хо) еще не открывался и если он откроется и завершит свое ожидание позднее, то цикл с номером 9(хо) также будет находиться под контролем цикла с номером 9{хi), более того, если у цикла с номером 9(хо) будут в дальнейшем скачки, то он по прежнему будет оставаться под контролем цикла с номером 9(хi). Если же Х\ был больше запрета цикла с номером 9{хо), то в случае скачка этого цикла, запрет цикла может стать большим, чем Х], но при этом сам цикл будет уже под контролем цикла с номером 9(хi). Итак, в любом случае, когда требование V\ завершит свое ожидание и соберется перечислять 9(хi) — а^в А, то либо х\ будет больше запрета цикла с номером 9{хо), либо этот цикл будет под контролем цикла с номером 9{х\). Эти же замечания справедливы и для циклов требования 7^1. Поэтому, завершив ожидание, V\ перечисляет 9{хi) = а^ в А и полагает его равным 9(х{) — а\, где а\ — это некоторое "большое" число. При этом, если требование через некоторое время опять будет иметь выход inf, то начнем опять работать с требованием 7Z\, при этом для TZq сохранят справедливость сделанные выше замечания касательно циклов. Теперь, если у требования 1Z\ цикл с номером 9(хо) не был открыт, или его запрет был больше свидетеля xi, то попав на выход inf, мы начинаем работать с требованием V\, которое объявляет своим помощником (т.е. это не позволит требованию 7Z\ более увеличивать свои запреты) и, перечислив 9(х\) = а} в А, определяет его равным "большому" числу

63 а\. Если же цикл с номером 9{хо) был под контролем цикла с номером 9(хi), то, имея вновь выход inf, мы на этом шаге лишь осуществляем переход от пункта (1) к пункту (2) цикла 9(хо) (Г в этой точке пока не определяем). На этом же шаге мы работаем и с требованием V\, которое объявляет 1Z\ своим помощником и, перечислив 9(xi) = а\ в А, определяет его равным "большому" числу а\. В этом случае требование 1Z\, став помощником, не определяет Г в точке в(хо) до тех пор, пока требование V\ не удовлетворится, перечислив х\ в В. Таким образом, требование Vi как бы преодолевает запрет требования Поэтому, когда 7Zq вновь будет иметь выход inf, мы обязательно на том же шаге начнем работать с требованием V\, которое перечисляет 9(х\) = а\ (без переопределения) в А и перечисляет х\ в В, и эти действия в силу вышеприведенных замечаний относительно циклов 7£-требований не повлияют на требования TZq и Hi. Также требование Vq освобождает всех своих помощников (в данном случае был только одни помощник). Теперь, когда требование IZq (также и для вновь будет иметь выход inf, то Х\ уже будет лежать в В, и если нам необходимо, мы можем определить и Г(0(жо))

Таким образом разрешается конфликт двух V- и двух ^-требований. В случае нескольких ^-требований мы будем постепенно делать их помощниками и здесь можно рассуждать по-индукции. Если будет несколько Р-требований, то рассмотрим для примера описанный выше случай с дополнительным требованием V2, приоритет которого меньше, чем у V\. Каждый раз, как требование V\ будет перечислять 9(хi) в А, оно будет инициализировать требование V2- Поэтому, когда V\ будет удовлетворено, то V2 назначит нового свидетеля, большего, чем запреты 7£-требований,

64 т.е. будет ситуация, когда на одно Р-требование стало меньше. Если же V2 начало удовлетворяться раньше, чем V\, то для простоты конструкции мы можем требование V\ сделать помощником требования V2, получив тем самым случай,когда на одно Р-требование стало меньше.

В случае со + 2 выходов выход к говорит о том, что цикл с номером к скачет на данном шаге, соответственно, запрет этого цикла также сбрасывается. В случае двух выходов inf и fin, запрет также сбрасывается, но проблема в том, что запреты разных ^-требований могут сбрасываться на разных шагах, и поэтому, когда некоторый цикл скачет, то в будущем, используя идентификатор, мы можем заставить его скакнуть еще раз в нужный для нас момент. Таким образом мы как бы синхронизируем скачки циклов для разных ^-требований, если у нас есть подозрение, что соответствующий выход будет истинным.

Модифицированные модули.

Модифицированная стратегия для "/^.-требования с учетом "Р-требований и вышеприведенных замечаний, приобретет следующий вид. При открытии цикла к на шаге s полагаем t(A;)[s] = s + 1.

Работаем по циклам, и в цикле к > 0 совершаем следующие действия:

1) Ждем шага 5: А \ (к + l)[s] = Фтш Г (к + l)[s], и ждем, пока завершится ожидание в пункте (1) в циклах от к до t(k) (причем циклы большие к считаются закрытыми).

2) Определяем Г^/г)^] = A(fc)[s] с use-функцией 7(fc)[s] = ¥>(*(&))[s] и открываем цикл к + 1.

3) Ждем шага si > s, что произошло: либо А: меняется W f на шаге si. либо В: меняется W Г </?(£(к))[s] на шаге s\. либо С: ASl(m) ф As(m) для некоторого т, что к <т < t(k).

Во всех случаях идем к пункту (1) и закрываем все циклы большие к. Кроме этого, в случаях А и С переопределяем t(k) = s\.

Конец цикла.

Данная стратегия имеет выходы:

A. Некоторый цикл начиная с некоторого шага (после которого все меньшие циклы все время ждут в (3)) бесконечно ждет в пункте (1). Это конечный выход, и в этом случае требование будет выполнено ввиду отсутствия равенства в левой части импликации.

B. Некоторый цикл ко бесконечно переходит от пункта (3) к пункту (1). При этом меньшие циклы с определенного шага больше не производят никаких действий. В этом случае требование также будет удовлетворено из-за того, что в левой части импликации будет неравенство.

C. Каждый цикл будет бесконечно ждать в пункте (3). Здесь мы успешно и корректно строим функционал Г. Очевидно, этот выход, как и предыдущие, является возможным и удовлетворяет требование.

Замечание. При выходе В цикл ко периодически будет сбрасывать свои запреты и попадать под контроль все большего числа циклов, что позволит нам сбрасывать запреты цикла ко при помощи этих циклов тогда, когда это нужно.

Удовлетворение требования Ve будет таким же, как в базовом модуле,

66 с той лишь разницей, что мы должны будем обращаться к конструкции, в которой мы опишем все это более детально.

1) Назначаем "большого" свидетеля хе.

2) Ждем шага s: 1= О

3) В зависимости от ситуации в конструкции либо перечисляем 9(хе) в А, полагаем 9(хе) равным новому "большому" числу и остаемся в пункте (3), либо перечисляем хе в В, а 9(хе) в А и говорим, что требование выполнено.

Данная стратегия имеет выходы:

A. Бесконечное ожидание в пункте (2), что означает диагонализацию и удовлетворение требования.

B. Проработав некоторое конечное время в пункте (3), стратегия перечисляет хе в В, и требование удовлетворяется посредством диагонализа-ции.

C. Бесконечная работа в пункте (3).

Выходы А и В конечны, невозможность выхода С обоснуем ниже.

Стратегию для удовлетворения ЛЛтребований мы оставляем без изменений и поэтому здесь приводить ее не будем.

Дерево стратегий.

Пусть А = {0,1} — множество выходов. У V- и Л/"-требований будет лишь один выход, который будет соответствовать выходу О Е Л. У 7Z-требований будут два выхода: выход inf будет соответствовать 0 € Л, а выход fin — 1 Е Л. Дерево стратегий, как обычно, определяем Т = A<w.

67

Каждая вершина a G Т будет ассоциироваться с некоторой стратегий. Пусть |ск| = Зе + г, где г = 0,1, 2. В зависимости от того, чему равно г, вершина а будет версией модифицированного модуля для требования 7Ze, Ve или Ме соответственно.

На каждом шаге мы будем строить вычислимую аппроксимацию 5S истинного пути /, который определим как самую левую бесконечно посещаемую ветвь дерева стратегий, и докажем, что все Л/*-требования удовлетворяются и что каждое V- и ^-требование удовлетворяется некоторой вершиной на истинном пути.

При инициализации вершины будем начинать работу стратегии, удовлетворяющей требование данной вершины, заново (будем делать это для единообразия и в том случае, когда требование данной вершины уже удовлетворено); параметры, функционалы и статусы, которые есть у вершины, становятся такими же, как на шаге s — 0.

Для Р-вершины а Е Т будем рассматривать параметр d — d(a)1 при помощи которого будем отслеживать количество действий, произведенное этой Р-вершиной. За действия будем считать переход из пункта (2) в пункт (3) и любую работу в пункте (3). В конструкции будет еще один параметр р = р(Р), где /3 6 Т. Этот параметр будет у всех типов требований, но в конструкции его будут использовать Р-вершины a D (3. При р((3) = 1 вершина (5 будет являться помощником и при р(/3) = 0 не будет являться. Хотя мы и не говорим, помощником какой вершины будет являться /3, но в конструкции это будет прослеживаться; нам будет достаточно того, что вершина (3 будет помощником какой-нибудь Р-вершины, и в этом случае вершина [3 должна будет показывать тот же выход, который был, когда она стала помощником. При этом стратегия вершины /5 не должна производить какие-либо действия. При инициализации Р-вершины а будем автоматически полагать р({3) = 0 для всех j3 С а таких, что они являются помощниками а.

Поскольку для М-требований мы не строим функционалов и не назначаем свидетелей, то не имеет смысла говорить, что мы работаем с какой-то версией некоторого требования Afe. Поэтому стратегия, удовлетворяющая некоторое требование Л/*е, будет одна, но в конструкции она будет привязываться к вершинам на уровне Зе + 2 дерева стратегий. За привязку будет отвечать параметр StrN(e) £ Т. В процессе конструкции параметр StrN(e) может меняться, и требование J\fe при этом будет привязываться к вершинам, которые на дереве стратегий лежат левее вершины StrNie). При инициализации вершины StrN(e) инициализируется требование Л/*е, и параметр StrN(e) становится неопределенным. Отметим, что не стоит путать параметр требований StrN(e) с параметрами вершин. Будем говорить, что требование Л/*е требует внимания на шаге s, если стратегия этого требования на шаге s завершило ожидание в пункте (1).

В процессе работы с 7£-вершиной будем совершать не более одного перехода из пункта в пункт и не более, чем в одном цикле, и будем искать наименьший цикл, который собирается сделать переход между пунктами. Если стратегии любого типа на данном шаге совершают переход между пунктами, то они уже не выполняют никаких инструкций в пункте. У каждой 7?.-вершины а £ Т будет функция-идентификатор t(k) — t(a, k). При открытии цикла к на шаге s его идентификатор будем полагать ts(k) = s + 1, в процессе конструкции этот идентификатор может воз

69 растать в некоторых точках согласно работе стратегии вершины а. У 7Z-требований мы будем рассматривать лишь те циклы, номера которых мы можем перечислять в А (т.е. эти номера равны 9{х), где х является свидетелем какого-нибудь Р-требования), и, как только мы узнаем, что некоторый номер цикла мы перечислять в А не будем, то определяем в этой точке Г5(а) = 0 и перестаем рассматривать скачки этого цикла. Каждая 7?.-вершина а Е Т будет строить свой функционал Г (а) с соответствующей use-функцией 7(a).

К онстру кция.

Шаг s = 0. Ао = Во = 0, все параметры Го (а),70 (а),а Е Т, StrN(e),e Е со нигде не определены, для всех 7£-вершин а Е Т идентификаторы полагаем to(k, а) = к.

Шаг s + 1. Пусть As, Bs определены, пусть для всех вершин определены 7S, ts, ts(k),пусть для всех е Е со определены StrNs(e). Определим длина которой будет |<5s+i| = s + Действовать будем по индукции. На подшаге п < s + 1, имея некоторый \ п, покажем, как будем определять £(п) (обозначение £ вводим лишь для краткости). Каждый раз будем смотреть какой из следующих случаев в порядке приоритета имеет место.

Случай I.

Если есть ли такие е, что StrN(e) < £ и Ме требует внимания, то находим такую минимальную (в лексикографическом порядке) вершину StrN(e), переводим стратегию требования Л/"е в пункт (2), инициализируем все вершины г) > StrN(e) (кроме rj = StrN(e)) и переходим к следую

70 щему шагу s + 2; если таких е нет, то переходим к случаю II.

Случай II.

Если ps(0 = 1 (вершина £ является на этом шаге помощником) то определяем £(тг) = Ss(n) (а для Л/"-вершин еще полагаем StrNs+i(e) = где п = Зе+2), Функционалы, идентификаторы или параметры оставляем без изменения. Если — 0, то переходим к рассмотрению случаев.

Случай п = 3т (работаем с версией 7^-требования). Действуем согласно работе стратегии, и в случае ожидания (т.е. имеется открытый цикл, который ожидает в пункте (1), причем все меньшие циклы ожидают в пункте (3)) полагаем £(n) = 1, иначе £(тг) = 0. В первом случае функционал и идентификатор оставляем без изменения, а во втором функционал и идентификатор определяются как в описании стратегии.

Инициализируем все вершины 77 >

Случай п = 3т + 1 (работаем с "Р-требованием). Полагаем £(п) = 0, и если вершина £ еще ни разу не работала, то идем в пункт (1) стратегии данной вершины. если вершина удовлетворена или ожидает в пункте (2), то ничего не делаем. если на этом шаге шаге завершилось ожидание в пункте (2), то переходим из пункта (2) в пункт (3) и полагаем = 1. Инициализируем все вершины /3 > если вершина действовала один раз (ds = 1), то стратегия работает, как в описании первого дизъюнкта пункта (3) (перечисляет в8(х) в А и полагает as+i(a;) равным "большому" числу). В этом случае вершина также действует (ds+1 = ds + 1). Инициализируем все вершины /3 >

71 если же вершина £ действовала более одного раза (ds > 1), то полагаем ds+i = ds + 1 и находим для данной стратегии стратегию-помощника наименьшей длины г < п и (если г > 0) говорим, что стратегии [" (г — г), где г = 1, 2, 3 тоже является стратегиями-помощниками (т.е. если ps(Ss+1 \ г) = 1 и ps(£s+i \ г - 1) = 0, то ps+1(5s+1 \ г - i) = 1, где i = 0,1, 2, 3). Если же у вершины еще не было стратегий-помощников, то объявляем помощником вершину 5s+i \ 3т (т.е. если ps(<5s+i \ 3га) = 0, то ps+i(5s+i [" Зга) = 1)). Теперь, если г > 0, то действуем, как в первом дизъюнкте пункта (3) описания стратегии, т.е. перечисляем 0s(x) в А и полагаем 6s+i(x) равным "большому" числу. Если же оказалось, что г = 0, то действуем, как во втором дизъюнкте пункта (3) описания стратегии, т.е. перечисляем 9S(х) в Л, а х в В, и с этих пор #s+i(a;) = 9s(x) и больше не меняется, и освобождаем всех помощников (т.е. полагаем ps+i(a, £) = 0, если ps(o>,£) = 1); причем, если при освобождении некоторый цикл некоторой 7£-вершины будет находится в пункте (2), то мы его переводим в пункт (1). В дополнение ко всему инициализируем все вершины (3 >

Комментарий: вышеприведенный переход цикла из пункта (2) в пункт (1) — это технический момент, и ниже мы докажем, что это существенным образом не влияет на конструкцию. Этот переход необходим для поддержания корректности функционала в соответствующей точке, и без него могло бы оказаться так, что вершина перечислив х в В, портит вычисление в точке ко у своего помощника ого- Теперь, если цикл ко вершины ао находится в пункте (2) и приступает к действиям, то он определяет 7(&o)[si] = ГДе s0 < Si, и so — это шаг последнего перехода от пункта (1) к пункту (2), a Si — это шаг, на котором действуем после

72 перечисления х в В. Поэтому можем получить 7(&o)[si] ф ^(&o)[.Si], что, вообще говоря, может привести к нежелательным последствиям.

То есть использование этого перехода из пункта (2) в пункт (1) и помощников позволяет не только сбрасывать запреты, но и держать появившиеся "окна" открытыми столько, сколько нам нужно.

Случай п — 3т + 2 (работаем с Л/"-требованием). Полагаем £(п) = 0. Если StrNs(m) < то ничего не делаем. Если стратегия JVm находится в инициализированном состоянии, то идем в пункт (1) стратегии и полагаем StrNs+i(m) = Если требование Ыт требует внимания, то переводим стратегию в пункт (2), инициализируем все вершины /3 > полагаем StrNs+1(m) = f.

Верификация.

Истинный путь определяем, как f(n) = liminfs£s(n). Он существует в силу конечности числа выходов каждого требования.

Заметим, что каждая вершина не может быть помощником более, чем у одной "Р-вершины. Действительно, как только некоторая вершина г становится помощником Р-вершины тг, это значит, что г Стги после работы с г мы обязательно попадаем к вершине тг, и при этом вершина тг будет инициализировать все вершины £ такие, что тг С Осталось рассмотреть вершины тгх такие, что г С tti и тг < тгх, но к таким вершинам мы не попадем пока вершина г является помощником вершины тг. Таким образом, вершина т не будет становиться помощником у других Р-вершин, пока она является помощником вершины тг.

Лемма 1. Ни одна вершина на истинном пути не будет являться

73 вечным помощником.

Доказательство. Предположим противное, но это значит, что ро является вечным помощником для некоторого 7г, где ро С 7г. Тогда стратегия 7Г уже больше не инициализируется (т.е. мы больше не работаем на вершинах левее 7Г и т.п.), и при этом все вершины р такие, что ро С р С 7г, тоже являются помощниками 7Г. Другими словами, если мы поработаем с вершиной ро, то обязательно придем на том же шаге к вершине 7Г, которая является Р-требованием. Но при каждом действии вершины 7г (уже имеющей помощников) количество ее помощников увеличивается. Причем длины |т| новых помощников вершины 7Г будут строго меньше, чем длины остальных помощников. Поэтому вскоре появиться помощник с наименьшей возможной длиной, и после этого удовлетворится вершина 7Г, освобождая всех помощников. Если же мы перестанем работать с вершиной Ро, то это означает, что ро не лежит на истинном пути.П

Лемма 2. Никакой цикл никакой lZ-вершины на истинном пути не будет бесконечно переходить из пункта (2) в пункт (1), постоянно минуя пункт (3).

Доказательство. Действительно, если некоторый цикл ко (можем предположить, что циклы, меньшие ко, больше не действуют, т.к. иначе, цикл ко будет закрыт и открыт заново) 7?.-вершииы ро переходит из пункта (2) в пункт (1), то это происходит из-за того, что вершина перестала быть помощником некоторой Р-вершины щ. Теперь, если цикл ко перешел из пункта (1) в пункт (2), то вершина ро имеет на этом шаге выход 0. А для того, чтобы цикл ко опять перешел обратно из пункта (2) в пункт (1), вершина ро на этом же шаге должна стать помощником, но помощником она может стать лишь у тех Р-вершин, которые имеют приоритет выше, чем у щ, но таких лишь конечное число. Поэтому вскоре под выходом 0 не останется Р-вершин таких, что вершина ро должна стать их помощником на том же шаге. А это и означает, что цикл ко попадает в пункт (3).П

То есть лемма 2 говорит о том, что бесконечный переход некоторого цикла из пункта (2) в пункт (1) по сути своей есть то же самое, что бесконечный переход для этого цикла из пункта (3) в пункт (1). Итак, переход из пункта (2) в пункт (1) корректен.

Перейдем к доказательству того, что каждая стратегия на истинном пути инициализируется конечное число раз и удовлетворяет соответствующее требование. Рассуждать будем по индукции. Отметим, что по лемме 1, каждая вершина лежащая на истинном пути может действовать бесконечное число раз.

Лемма 3. Для любого е после некоторого шага s, для всех t > s либо StrN(e)[t] = StrN(e)[s], либо f \ (Зе +2) < StrN(e)[t].

Доказательство. Пусть sq шаг, после которого StrN{e) [so] < 8t \ (3e + 2) для всех t > Sq. Если оказалось, что StrN(e)[so] = / f (3e + 2), то для всех t > So будет S4r./V(e)[so] < StrN(e)[t], и условие теоремы выполнено, поэтому рассмотрим случай когда б^гА^е)^] < / \ (Зе + 2). Теперь требование Мс может быть инициализировано только другими требованиями Mi, что г Ф е и StrN(i)[so] < StrN(e)[so\. Если такой инициализации не будет, то StrN(e)[t] = <StrA7'(e)[so], для всех t > sq. В противном случае, пусть to — это шаг, на котором требование М10 произвело инициализацию. Тогда фиксируем шаг > to, после которого

S,trA7"(e)[si] < St(3e + 2) для всех t > Si. Опять же будем рассматривать случай когда 5ir./V"(e)(si] < / \ (Зе + 2). Если окажется, что 5triV(e)[so] = 5tr7V(e)[si], то будет как в первом случае, но требований Л/i, что i ф е и StrN(i)[si] < StrN(e)[si], станет меньше. Если же окажется, что ^гЛ/^е)^] < StrN(e)[si], то на уровне Зе + 2 на дереве стратегий между вершинами StrN(e)[si] и / \ (Зе -f- 2) других вершин меньше, чем между вершинами StrN(e)[s0] и f \ (Зе + 2). Продолжая аналогичные рассуждения, приходим к тому, что требований Mik, которые на соответствующих шагах tk инициализируют требование Л/*е, лишь конечное число. Пусть tn — шаг последней такой инициализации. Тогда после шага sn+i > tn: что S'triV"(e)[sn+i] < 5t f (Зе + 2) для всех t > su+1, либо StrN(e)[t] = StrN(e)[sn+i] (t > sn+i), либо / \ (3e + 2) < StrN(e)[t] (t > s^+i) в зависимости от <S'tr7V(e)[sn+i] < f \ (Зе + 2) или 5'triV(e)[sn+i] — / \ (Зе + 2), соответственно. Итак, шаг sn+i искомый.□

Лемма 4.Каждое V- и TZ-требование инициализируется конечное число раз и удовлетворяется соответствующей вершиной на истинном пути. Каэюдое ЛГ -требование инициализируется конечное число раз и удовлетворяется, и при этом соответствуюш^я стратегия будет либо на истинном пути, либо левее.

Доказательство. Рассуждать будем по-индукции. Вершина ро ~ f ГО будет отвечать некоторому ^-требованию с наибольшим приоритетом, и, очевидно, она не может быть инициализирована никакой другой вершиной. Докажем, что функционал данного требования будет определен корректно. Действительно, если каждый цикл конечное число раз скачет или работает, то, во-первых, для каждого к перестанет возрастать t{k), и, во

76 вторых, после этого каждый цикл < t(k) также проработает конечное число раз, после чего перестанет меняться use-функция, а Г(/с) будет вычислен правильно. Соответственно, если будет существовать цикл ко, который бесконечно часто скачет и при этом меньшие циклы больше не работают, то по лемме 2 цикл ко будет бесконечно часто переходить из пункта (3) в пункт (1), что означает, что функционал Ф не всюду определен, и поэтому вершина ро будет и в этом случае удовлетворять требование TZq- Отметим, что данная вершина в процессе своей работы вообще не инициализирует другие вершины.

Индукционный шаг. Предположим, что для некоторого п все вершины, лежащие на f \ п больше не инициализируются и удовлетворяют соответствующее требование. Докажем то же для а = f \ (п + 1). Так как а лежит на истинном пути, то она инициализируется конечное число раз вершинами левее. Также а инициализируется конечное число раз вершинами, которых а расширяет, потому что стратегии, лежащие на / \ п либо вообще не инициализируют те вершины, которые их расширяют на истинном пути (это верно для ^-стратегий), либо они уже удовлетворены и вообще ничего не инициализируют (стратегии типа Ve и Л/*е)- Пусть so является шагом, после которого а больше не инициализируется по этим причинам. По лемме 3 можем зафиксировать шаг Si > so, что все для всех е, удовлетворяющим <S'iriV(e)[so] < сг, будут выполнены условия из леммы 3. И после шага si вершина а может быть инициализирована лишь вершинами 5'trAr(e)[so] при упомянутых выше е. Это тоже лишь конечное число инициализаций.

Рассмотрим случаи, когда п — |сг| соответствует стратегиям различных

77 типов.

Случай п = 3т, или а — ро- Данная 1Z-вершина удовлетворяет требование 7Zm согласно работе своей стратегии и не инициализирует те вершины, которые ее расширяют. Остальное доказывается точно также, как в базисе индукции.

Случай п = 3m + 1, или а = щ. Если стратегия 7Го будет постоянно ожидать, то она удовлетворена. Иначе, либо мы перестаем работать с вершиной <т (это может быть только в случае, если она не лежит на истинном пути), либо мы постепенно увеличиваем число помощников, и доходим до корня дерева, делая его также помощником. На следующем шаге мы из-за помощников опять попадаем на вершину щ и, видя, что корень дерева является помощником, согласно конструкции перечисляем свидетеля х в В, и данная стратегия 7Го удовлетворяет требование Vm, которое после этого больше не инициализирует вершины, лежащие на истинном пути.

Случай п = 3т + 2, или а = щ. По лемме 3 параметр StrN(m) после некоторого шага s удовлетворяет для всех t > s либо StrN(m)[t] = StrN(m)[s], либо / f" (3m+ 2) < StrN(m)[t], В случае второго дизъюнкта будет / Г (Зга + 2) = StrN(m)[t] (т.к. s > и требование J\Tm больше не инициализируется). Другими словами, после шага s параметр StrN(m) перестает меняться, причем будет StrN(m) < 770. Если стратегия будет постоянно ожидать, то она удовлетворена. Иначе, согласно конструкции требование N"m может потребовать внимания и, сделав это один раз и оказавшись в пункте (2), удовлетворяется, и после этого больше не инициализирует вершины, лежащие на истинном пути. □

Корректность функционала, сводящего В к А следует непосредственно из конструкции: для каждого свидетеля х для множества В в(х) со временем перестает возрастать, причем если х будет перечислен в В, то 0{х) (согласно работе Р-стратегий) будет перечислен в А.П

Хорошо известно, что низкие степени не образуют верхнюю полурешетку. Поэтому, если у нас есть какая-то формула, при помощи которой мы изучаем теоретико-модельные свойства структуры, образующей верхнюю полурешетку, то при ограничении на низкие степени необходимо избавляться в формуле от "U". Иногда это удается с сохранением нужных свойств формулы для класса низких степеней. Напомним определение почти глубокой в.п. степени, введенной в работе Грожека, Сламана и Чолака [25].

Определение 3.2 В.п. степень b называется почти глубокой, если для любой низкой в.п. степени w степень bUw останется низкой.

Их доказательство существования почти глубокой степени использует метод бесконечного приоритета на деревьях и теорему рекурсии, которая часто используется при работе с низкими в.п. степенями. В их конструкции положительные требования конечного действия как и в теореме 3.1, но там преодолеваются запреты инициированные более сложными требованиями низости. Более детальный анализ показывает, что эти конструкции можно объединить, но тогда получится очень громоздкая конструкция, поэтому приведем следствие теоремы 3.1 в следующем виде.

Следствие 3.1 Пусть существуют невычислимые в.п. степени b < а такие, что b почти глубокая и b сильно недополняема до а. в классе в.п. степеней, тогда существует предложение, отличающее элементарные теории низких в.п. и низких 2-в.п. степеней.

Доказательство. Итак, рассмотрим ф = 3 a, b V w [(0 < b < а)Л[а < w Va ^ bUw]].

Нетрудно видеть, что по условию предложение ф будет истинно для низких в.п. степеней. По теореме Купера, Лемппа и Уотсона получаем, что для любых низких невычислимых 2-в.п. степеней b < а существует низкая 2-в.п. степень d, что а < 0' < b U d. Другими словами, предложение ф не верно для низких 2-в.п. степеней. Наконец, покажем на каком уровне достигается элементарное различие этих частичных порядков. Преобразовав предложение ф, получим (р = За, b V w [(0 < b < а) A {(а < w) V (3 g [а £ g A b < g A w < g])}].

Отсюда получаем, что частичные порядки низких в.п. и низких 2-в.п. степеней не элементарно эквиваленты на уровне S3. Напомним, что следствие 2.1 давало различие на уровне £2. □

Список литературы диссертационного исследования кандидат физико-математических наук Ямалеев, Марс Мансурович, 2009 год

1. Sacks G.E. On the degrees less than 0'. // Annals of Mathematic.—1963.— V.77.—P.211-231.

2. Robinson R.W. Interpolation and embedding in the recursively enumerable degrees. // Annals of Mathematic.—1971-V.93.—P.285-314.

3. Cooper S.B. A splitting theorem for the n-r.e. degrees. // Proceeding American Mathematical Society.—1992.—V.115.—P.461-471. (http://www.amsta.leeds.ac.uk/ pmt6sbc/preprints.html)

4. Cooper S.B., Li A. Turing Definability in the Ershov Hierarchy. // Journal of the London Mathematical Society.—2002.—V.66.—P.513-528. (http://www.amsta.leeds.ac.uk/ pmt6sbc/preprints.html)

5. Arslanov M.M., Cooper S.B., Li A. There is no low maximal d-c.e. degree // Mathematical Logic Quarterly—2000,—V.46.—No.3.—P.409-416. (http://www.amsta.leeds.ac.uk/ pmt6sbc/preprints.html)

6. Arslanov M.M., Cooper S.B., Li A. There is no low maximal d-c.e. degree — Corrigendum // Mathematical Logic Quarterly.—2004.—V.50.—No.6.—P.628-636. (http://www.amsta.leeds.ac.uk/ pmt6sbc/preprints.html)

7. Cooper S.B. The jump is definable in the structure of the degrees of unsolvability. j j Bull. Amer. Math. Soc—1990 —V.23—No.l—P.151-158.

8. Shore R.A., Slaman T.A. A splitting theorem in n — RE A degrees. // Proceedings of the American Mathematical Society.—2001.—V.129.—No.12.— P.3721-3728.

9. Arslanov M.M., Kalimullin I.Sh., Lempp S. On Downey's conjecture. // The Journal of Symbolic Logic. Принято к печати. (http://www.math.wisc.edu/ lempp/papers)

10. Cooper S.B., Lempp S., Watson P. Weak density and cupping in the d-c.e degrees. // Israel Journal of Mathematic —1989.—'V.67.—P. 137-152. (http://www.math.wisc.edu/ lempp/papers)

11. Cooper S.B., Li A. Splitting and cone avoidance in the d.c.e. degrees. // Science in China (Series A).-2002—V.45.—P.1135-1146. (http://www.amsta.leeds.ac.uk/ pmt6sbc/preprints.html)

12. Cooper S.B., Yi X. Isolated d.r.e. degrees // Preprint

13. Ефремов С.С. Изолированные сверху d-в.п. степени, I// Известия высших учебных заведений. Математика. 1998. - №2. - С. 20-28.

14. Ефремов С.С. Изолированные сверху d-в.п. степени, II// Известия высших учебных заведений. Математика. 1998. - №7. - С. 18-25.

15. Wu G. Bi-isolation in the d.c.e. degrees // J. Symbolic Logic. 2004. - V.69. - №2. - P. 409-420.

16. Miller D.P. High recursively enumerable degrees and the anti-cupping property // Lecture Notes in Mathematics, Springer-Verlag, Berlin.—1981.—V.859.— P.230-245.

17. Арсланов M.M. Структурные свойства степеней ниже О' // ДАН СССР.—1985.— Т. 283.- ДО2.-С.270-273.

18. Арсланов М.М. О структуре степеней ниже 0' // Известия ВУЗов, Математика.—1988.— №7.-0.27-33.

19. Downey R.G. D-r.e. degrees and the nondiamond theorem // Bull, of the London Math. Soc.-1989 —V.21.-P.43-50.

20. Downey R.G, Stob M. Splitting theorems in recursion theory. // Ann. Pure Appl. Logic—1993.—V.65.—P. 1-106.

21. Downey R., Yu L. There are no maximal low d-c.e. degree // Notre Dame Journal of Formal Logic.-2004.-V.45.-No.3.-P.147-159.

22. Cooper S.B. The strong anticupping property for recursively enumerable degrees. // The Journal of Symbolic Logic.-1989.-V.54.-No.2.-P.527-539.

23. Slaman T.A., Steel J.R. Complementation in the Turing degrees. // The Journal of Symbolic Logic.-1989.-V.54.-No.l.-P.160-176.

24. Coap Р.И. Вычислимо-перечислимые множества и степени.—Казань: Казанское математическое общество, 2000,—576 с.

25. Cholak P., Groszek М., Slaman Т.A. An almost deep degree. // The Journal of Symbolic Logic.—2001.—V.66.—No.2.—P.881-901.

26. Faizrahmanov M.Kh., Splitting and antisplitting theorems in classes of low degrees. // тезисы международной конференции Logic Colloquium 2009 (София, Болгария, 2009г.).-2009.-P.45-46.

27. Арсланов М.М. Рекурсивно перечислимые множества и степени неразрешимости.—Казань: изд-во КГУ.—1986.—206 с.

28. Арсланов М.М. Локальная теория степеней неразрешимости и Д<]-множества.—Казань: изд-во КГУ.—1987,—140 с.

29. Арсланов М.М. Иерархия Ершова. Спецкурс для студентов мехмата. -Казань: Казанский государственный университет, 2007.—86 с.

30. Роджерс X. Теория рекурсивных функций и эффективная вычислимость.—М.: Мир, 1972.—624 с.

31. Шенфилд Дж. Степени неразрешимости. — Москва: Наука, 1977.—192 с.

32. Работы автора по теме диссертации

33. Ямалеев М.М., Разложимость 2-вычислимо перечислимых степеней с избеганием конусов. // Известия вузов. Математика.—2009.—№6.—С.76-80.

34. Ямалеев М.М., Сильная недополняемость в низких вычислимо перечислимых степенях. // Известия вузов. Математика,—Принято к печати.

35. Ямалеев М.М., n-низкие в.п. и n-низкие 2-в.п. степени не являются элементарно эквивалентными. // Препринт.

36. Ямалеев М.М., 3-е.п. множества и их перечислимость относительно в.п. степеней. // Итоговая научно-образовательная конференция студентов Казанского Государственного Университета 2006 года: Сборник статей.—2006.—С.47-50.

37. Ямалеев М.М., REA-степени и тьюринговые степени неразрешимости. // Итоговая научно-образовательная конференция студентов Казанского Государственного Университета за 2005 год: тезисы докладов. 2005. -С.31-32.

38. Yamaleev М.М., п-с.е. sets СЕА in с.е. degrees. // The Bulletin of Symbolic Logic.—2007.—V.13.—P.291-292.

39. Yamaleev M.M., Low c.e. and low 2-c.e. degrees are not elementarily equivalent. // The Bulletin of Symbolic Logic.—2009 —V. 15,—p. 131.

40. Yamaleev M.M., n-c.e. sets CEA in c.e. degrees. // тезисы международной конференции Logic Colloquium 2006 (Неймеген, Нидерланды, 2006г.). -2006. р.40.

41. Yamaleev М.М., Low c.e. and low 2-c.e. degrees are not elementarily equivalent. // тезисы международной конференции Logic Colloquium 2008 (Берн, Швейцария, 2008г.). 2008. - р.56.

42. Yamaleev М.М., Splitting properties in 2-c.e. degrees. // тезисы международной конференции Logic Colloquium 2009 (София, Болгария, 2009г.). -2009. р.91.