Сводимости табличного типа

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

Глава I. О ВЕРХНИХ ПОЛУРЕШЕТКАХ РЕКУРСИВНО-ПЕРЕЧИСЛИМЫХ

СТЕПЕНЕЙ ТАБЛИЧНОГО ТИПА

§ I. Сводимости табличного типа и счетчики

§ 2. О минимальных степенях

§3. oTk/O.TIicLc) K~T^{Lt)

§4. оТй(/^)иТh^it{)

§5. oT'R(iLp') иТ^

Глава 2. СООТНОШЕНИЯ МЕЖДУ ПОЛНЬШИ МНОЖЕСТВАМИ

§ 6. Предварительные результаты

§ 7. Основная лемма

§ 8. О Ы!-полных множествах

§ 9. Об 1- полных множествах
Глава 3. СООТНОШЕНИЯ МЕЖДУ СТЕПЕНЯМИ
§ 10. О ett- и ( ■ степенях внутри it-степени
§ II. Об уп-степенях внутри i- степени
§ 12. Об т-степенях внутри Ш. - степени
§ 13. Об одной гипотезе Ю.Ершова
Глава 4. ОБ {- И т-СВОДИМОСТИ
§ 14. Об {-степенях внутри m-степени
§ 15. Один пример решетки
§ 16. Три теоремы об т-степенях
§ 17. Разрешимость V3-теории L m
Литература

Теория алгоритмов (рекурсивных функций) является одним из современных и бурно развивающихся разделов математической логики. Её появление обусловлено формализацией в середине 30-х годов интуитивного понятия вычислимой функции. Важным моментом этой теории является рассмотрение и классификация подмножеств множества натуральных чисел КІ = {0,1,2 } с алгоритмической точки зрения, а также исследование структур, возникающих в результате такой классификации. Для каждого множества А, А ькі, можно сформулировать следующую проблему: существует ли алгоритм, позволяющий для любого X € ГЧІ ответить на вопрос о принадлежности X к Д. Множества, для которых данная проблема разрешима, были названы рекурсивными. Однако скоро выяснилось, что существуют различные по своей "сложности" рекурсивно перечислимые (р.п.) множества, не являющиеся рекурсивными, которые стали особым объектом изучения. Инструментом для классификации подмножеств [1 по их "сложности" служит понятие сводимости, являющееся одним из центральных в теории алгоритмов. На интуитивном уровне множество А сводимо к множеству В , если существует алгоритм, который решал бы проблему вхождения элементов для А при условии, что есть возможность пользоваться информацией о принадлежности тех или иных элементов множеству В . Такая сводимость в самом общем виде называется тьюринговой (Т*) сводимостью.

Результаты и методы теории алгоритмов быстро нашли своё применение в различных областях математики. Выяснилось, что многие из известных проблем являются неразрешимыми. Такими будут, например, проблема распознавания тождественной истинности формул исчисления предикатов, проблемы тождества слов конечно определённых групп и полугрупп, 10-я проблема Гильберта и другие.
Часто неразрешимость одной проблемы доказывается как раз посредством сведения к ней другой, о которой заранее известно, что она неразрешима. Эта последняя проблема в большинстве случаев является проблемой разрешимости подходящего р.п. множества.
Наряду с "Т-сводимостыо для исследования множеств уже в 1944 году Э.Пост [зз] ввёл некоторые специальные виды сводимостей -такие, как М-сводимость, табличная (И-) и ограниченная табличная №-) сводимости. Именно, множество А УП-сводимо к множеству В (А^^В), если существует всюду определённая на. (4 вычислимая функция Т такая, что для всех
Х€.к1. Множество А "Ы-сводимо К В (А^-^В), если существует алгоритм, который для каждого Х£(1 даёт набор чисел
П(х^ И булеву функцию такие,

(УхХхеА4^ (О,/(•£?) /а п«>) = 4,
где ^(1) = 1, если 1 £ В , и ^ (1) = 0, если 1Ф В . В частности, если П(Х) для всех X не больше некоторого фиксированного числа, то говорят, что А 1>11-сводимо к В (А ^ щ В). Ясно, что пц-сводимость - частный случай Ш-сводимости, которая в свою очередь является частным случаем 11-сводимости. Вообще Я,-сводимость слабее Г-сводимости, если А А-В влечёт
А^В для всех А;В — г4!, А>В Ф {0>^}•
От произвольной сводимости V- на подмножествах 11 по крайней мере требуют, чтобы отношение 4.г было бы предпорядком.

и С^($слА)~ рП>-эквивалентные подмножества А. По уело- ■ вию (а) имеем: ^^-А^ ^(ТсЛА)» а так как ^($0ЧА'} - ЕД, , то ЙОЛС^А>0. Аналогично, Я^(В1"А^0 * Учитывая, что^0и^=к), приходим к противоречию с рекурсивной неотделимостью множеств
Во''А и ЬлА.
Теорема доказана.
В теореме 3.3 с-сводимость можно заменить на любую сводимость, которая по свей силе является промежуточной между 1с- и И-сводимостью. Отсюда, вместе со следствием из теоремы 3,2, получаем
СЛЕДСТВИЕ. для Те [Ш-ДМр-,Ы-, (кНе являются дистрибутивные и верхние полурешетки р.п. Т- степеней, где Т-сводимость по своей силе является промежуточной между или А Асводимостью и 41-сводимостью. Действительно, пусть А - произвольное гиперпростое множество с ретрассируемым дополнением, а Ь0 и его разбиение на два р.п. Т- несравнимых множества ^25]. Тогда, как и в теореме 3.2, Ь«ТтА> А И А-е4с^В0ФЬ1. Предположим, что А0ФД,=,А;Ао^Ли для некоторых р.п. нерекурсивных множеств А0 и Аа . По лемме 2.4, А0=тА=тА1}а с другой стороны А0^ТЬ/-ТД и А^Ь^А.
Это противоречие и доказывает, что р.п. множеств А0 и АЛ с указанными выше свойствами не существует.
Перейдём теперь к рассмотрений ТА (А ^), Как доказал С.Марчен-ков [22], предложение (3.1) является истинным в А^. для
с4‘Т Но оно является ложным не только в , но и в
А^. Действительно, пусть А - произвольное р.п. нерекурсивное и не (.-полное множество. Из работы [23] следует существование максимального множества В такого, что В*ЦА , а по лемме 2,2 степень В является минимальной. Однако эти рассуждения не позволяют различить ТА (А А) и ТАдДщ). Поэтому сейчас будет (