Сводимости табличного типа тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Введение

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

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

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

§3. olh{LM)JULc)nl^Lt)

§4. оТ£(1и)иТftc^itO.

§5. oT£(Lp) иТЦЬа)

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

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

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

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

§ 9. Об {.-полных множествах

Глава 3. СООТНОШЕНИЯ МЕВДУ СТЕПЕНЯМИ

§ 10. О 6tt- и I- степенях внутри it-степени.

§ II. Об степенях внутри '{.-степени.

§ 12. Об т-степенях внутри степени.

§ 13. Об одной гипотезе Ю.Ершова.

Глава 4. ОБ 1- И ГП-СВОДИМОСТИ

§ 14. Об {-степенях внутри m-степени.

§ 15. Один пример решетки L(X).

§ 16. Три теоремы об wi-степенях.

§ 17. Разрешимость V3 -теории LM

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

Результаты и методы теории алгоритмов быстро нашли своё применение в различных областях математики. Выяснилось, что многие из известных проблем являются неразрешимыми. Такими будут, например, проблема распознавания тождественной истинности формул исчисления предикатов, проблемы тождества слов конечно определённых групп и полугрупп, 10-я проблема Гильберта и другие. Часто неразрешимость одной проблемы доказывается как раз посредством сведения к ней другой, о которой заранее известно, что она неразрешима. Эта последняя проблема в большинстве случаев является проблемой разрешимости подходящего р.п. множества.

Наряду с Т-сводимостьго для исследования множеств уже в 1944 году Э.Пост [зз] ввёл некоторые специальные виды сводимостей -такие, как m-сводимость, табличная (it-) и ограниченная табличная сводимости. Именно, множество Л КП-сводимо к множеству В (А^В), если существует всюду определённая на Л вычислимая функция Т такая, что для всех XCfsl . Множество A tt -сводимо к tti-7, если существует алгоритм, который для каждого Х£|\1 даёт набор чисел ta0o> и булеву функцию ^X^i^av^^ такие» что

УхХХ^РхС^ЗС^,.,/^^):= i, где 1 ? если

U Б и ^ ("(:) = {), если ив . В частности, если П(Х) для всех Х не больше некоторого фиксированного числа, то говорят, что А 1й-сводимо к Ясно, что Пг\-сводимость - частный случай 4Й-сводимости, которая в свою очередь является частным случаем tt-сводимости. Вообще R„~ сводимость слабее Г-сводимости, если А ^.В влечёт А<6КВ> для всех А,В 4Mb

От произвольной сводимости Y- на подмножествах !\1 по крайней мере требуют, чтобы отношение т было бы предпорядком.

Если положить то =г будет являться отношением эквивалентности, отдельный класс которой называется Т-степеньго (и р.п. Y-степенью, если ей принадлежит р.п. множество). На множестве всех (или только р.п.) Т-степеней естественным образом также определяется отношение частичного порядка ^ г, вместе с которым оно образует верхнюю полурешетку, как только Y1-сводимость слабее т-своди-мости. В этом случае верхнюю полурешетку р.п. х-степеней будем обозначать через Ллг , а её элементарную теорию через Хорошо известно [4], что все эти полурешетки имеют наименьший элемент 0 и наибольший элемент И .Р.п. множества, принадлежащие наибольшей Y-степени Ц полурешетки /дг , называются V- полными.

Сводимости, промежуточные по своей силе между ГУЧ- и tt-сводимостью, называются сводимостями табличного типа (иногда сильными сводимостями). Наиболее прямолинейным способом получения какой-либо сводимости табличного типа является требование, чтобы булева функция , участвующая в определении "tt-сводимости, принадлежала для всех X некоторому замкнутому классу булевых функций. В частности, этот класс, соответствующий 171-сводимости ( tt-сводимости), есть (класс всех булевых функций). Именно таким образом постепенно были определены и начали исследоваться дизъюнктивная конъюнктивная ^С-4) , позитивная (р-) , fett^ и линейная ((-) сводимости. Как выяснилось [б], по этому пути новых сводимостей получить нельзя, и поэтому перечисленные выше семь сводимостей естественно назвать основными. В то же время по аналогии с (?)tt-сводимостью можно определить и другие ограниченные сводимости табличного типа, такие, как

Ы-, к-, bp-, и Wi-сводимость. Однако они фактически не изучались и занимают пока среди других сводимостей второстепенное место. Кроме' того, и ina-сводимость на р.п. множествах совпадают с т-сводимостью и поэтому ниже не рассматриваются. Главное внимание в диссертации будет уделено классу основных сводимостей вместе с fett-сводимостью - наиболее важной и интересной из ограниченных сводимостей, то есть классу tJt- {Mt-.tt-.t-, p-.d-.c-, m-V

Соотношения между этими сводимостями по силе указаны на диаграмме I.

К началу 70-х годов "tt-сводимость (и другие сводимости табличного типа) по сравнению с 1- и ГП-сводимостыо оказалась наименее изученной. Это, по-видимому, объясняется тем, что понятие tt-сводимости не отличается такой простотой, как |т-сводимости, и такой общностью, как понятие ~Тсводимости. Более того, её свойства существенно отличаются от свойств ~Т~ и ЩП-сводимости, что потребовало от её исследователей привлечения новых идей и методов. В то же время в изучении различных сводимостей явно выделились три направления. Одно из них, наиболее раннее, заключается в том, чтобы охарактеризовать Y-полные множества и выяснить соотношения, например, по включению, между классами Y-полных множеств для тех или иных сводимостей Другое связано с вопросами строения полурешеток Г-степеней, в особенности р.п. Т- степеней. Третье - с вопросами, сколько Y-степеней имеется и как они расположены в степенях, относительно более слабой сводимости. Именно решению трёх проблем для класса сводимостей относящихся к этим трём направлениям, а также некоторым естественным вопросам, примыкающим к ГО-сводимости, посвящена настоящая диссертация.

Перейдём к более подробному изложению результатов. Диссертация состоит из введения, четырёх глав, объединяющих семнадцать

1. Дёгтев А.Н., Захаров Д. А. Перечислимые множества. Новосибирск, 1979. - 92 с.

2. Ерщов Ю.Л. Теория нумераций. М.: Наука, 1977. - 416 с.

3. Мальцев А.И. Алгоритмы и рекурсивные функции, М.: Наука, 1965. - 392 с.

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

5. Булитко В.К. Сводимость линейными по Жегалкину таблицами. -Сиб.матем.ж., 1980, т.21, №3, с. 23-31.

6. Денисов С.Д. Об m-степенях рекурсивно-перечислимых множествах. Алгебра и логика, 1970, т. 9, М, с.422-427.

7. Денисов С.Д, Три теоремы об элементарных теориях и "tt-сво-димости. Алгебра и логика, 1974, т. 13, № I, с.5-8.

8. Дёгтев А.Н. О гиперпростых множествах с ретрасеируемыми дополнениями, Алгебра и логика, 1971, т.10, № 3, с,235-246,

9. Дёгтев А.Н. Об степенях простых множеств. Алгебра и логика, 1972, т. II, № 2, с. 130-139.

10. Дёгтев А.Н. О it- и па-степенях. Алгебра и логика, 1973, т.12, № 2, с.143-161.

11. Ершов Ю.Л. Гипергиперпростые yyi-степени. Алгебра и логика, 1969, т. 8, № 5, с.523-552.

12. Ершов Ю.Л. Позитивные эквивалентности. Алгебра и логика, 1971, т. 10, № 6, с.620-650.

13. Ершов Ю.Л., Лавров И.А. Верхняя полурешетка L(^), Алге-' бра и логика, 1973, т. 12, № 2, с.167-189.

14. Каллибеков С. О степенях рекурсивно-перечислимых множеств. -Сиб.матем. ж., 1973, т.14, № 2, с. 421-426.

15. Каллибеков С. О табличных степенях рекурсивно-перечислимых множеств. Матем. заметки, 1973, т. 14, № 5, с.697-702.

16. Кобзев Г.Н. О fctt-сводимости, 2. Алгебра и логика, 1973, т. 12, № 4, с.433-445.

17. Кобзев Г.Н. О полной Ш. -степени. Алгебра и логика, 1974, т. 13, № I, с.22-25.

18. Кобзев Г.Н. О V- отделимых множествах. В сб.: Исследования по матем. логике и теории алгоритмов. - Тбилиси, 1975, с.19-30.

19. Кобзев Г.Н. Максимальные м«степени, Сообщ. АН ГССР,1977, т. 85, № 2, с.325-327.

20. Кобзев Г.Н, 0 полурешетке it-степеней. Сообщ. АН ГССР,1978, т. 90, № 2, с,281-283.

21. Кобзев Г.Н, 0 it-степенях рекурсивно-перечислимых тьюрин-говых степеней. Матем. сб., 1978, т. 106, № 4, с.507-514.

22. Марченков С.С. К сравнению верхних полурешеток рекурсивно-перечислимых табличных степеней и т-степеней. Матем. заметки, 1976, т. 20, № I, с. 19-25.

23. Марченков С.С. О табличных степенях максимальных множеств. -Матем. заметки, 1976, т. 20, № 3, с, 373-381.

24. Марченков С.С. О рекурсивно-перечислимых минимальныхfelt -степенях. Матем.сб., 1977, т.103, №4, с.550-562.

25. CleavT.P. Some properities of recursively unseparable sets*-Z.Math. Logik und Grundl.Math.,1970, v.16,N2,p.187-200.

26. Fischer P.O. A note on bounded-truth-table reducibility. -Proc. Amer.Math.Soc. ,1963, v.14, Ш 6, p.875-677.27» Jockusch 0. Semirecursive sets and positive reducibility. -2rans.Amer.Math.Soc., 1968, v.131, Ш 2, p.420-436.

27. Jockusch C. Relationships between reducibilities Trans. Amer.Math.Soc., 1969, v.142, N8 1, p.229-23729* Lachlan A.H. A note on uneversal sets. J.Symb. Logic,1966, v.31, p.573-574.

28. Lachlan A.H. On the lattice of recursively enumerable sets. -Trans.Amer.Math.Soc., 1968, v.130, 1, p.1-37.

29. Lachlan A.H. Two theorem on many-one degrees of recursively enumerable sets. Алгебра и логика, 1972,т.И,№2,с.216-226.

30. Shoenfield J.R. Quasicreative sets. Proc.Amer.Math.Soc., 1957» v.8, № 5, p.964-967.

31. Ullian J.S. Splinters of recursive functions. J.Symb. Logic, 1960, v.25, Hi 1, p.33-38.

32. Yates C.E.M. Recursively enumerable sets and retracing functions. Z.Math.Logic und Grundl.Math., 1962, v.8, № 4, p.331-345.

33. Young P.R. Linear ordering under one-one reducibility. -J.Symb.Logic, 1966, v.31, N2 1, p.70-85.РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИЙ

34. Дёгтев А.Н. О частично упорядоченных множества i-степеней, содержащихся в рекурсивно-перечислимых m-степенях. -Алгебра и логика, 1976, т.15, № 3, с. 249-266.

35. Дёгтев А.Н. О минимальных i-степенях и табличной сводимости. Сиб.матем. ж., 1976, т. 17, № 5, с. I0I4-I022.

36. Дёгтев А.Н. Об т-степенях надмножеств простых множеств. « Матем.заметки, 1978, т. 23, № 6, с. 289-293.

37. Дёгтев А.Н. Три теоремы о -It-степенях. Алгебра и логика, 1978, т.17, № 3, 270-281.

38. Дёгтев А.Н. О сводимостях табличного типа в теории алгоритмов. Успехи матем. наук, 1979, т.34, № 3, с. 137-168.

39. Дёгтев А.Н, Несколько результатов о верхних полурешетках и т-степенях, Алгебра и логика, 1979, т.18, № 6,с. 664-679.

40. Дёгтев А.Н. Соотношения между полными множествами. Изв. вузов, Математика, 1981, № 5, с. 50-56.

41. Дёгтев А.Н. Сравнение линейной сводимости с другими своди-мостями табличного типа. Алгебра и логика, 1982, т. 21, $ 5, с. 511-529.

42. Дёгтев А.Н. Соотношения между степенями табличного типа. -Алгебра и логика, 1983, т.22, № I, с.35-52.

43. Дёгтев А.Н. Соотношения между сводимостями табличного типа.-Алгебра и логика, 1983, т.22, Ю, с.243-259

44. Degfcev A.N. Small degrees in ordinary recursion theory. -Ini Proc. VI ICLMPS. Amsterdam, t North-Holland Pabe. Co. and РШ, 1982, p.237-2^-0.