Статья: Структура рекурсивных m-степеней в полях

И.В. Ашаев, Омский государственный университет, кафедра математической логики 

Обычная теория алгоритмов изучает вычислимость над конструктивными объектами, которые допускают эффективное кодирование натуральными числами. При этом многие процессы в математике, имеющие интуитивно алгоритмическую природу, но работающие в неконструктивных областях (например, в вещественных числах), не являются алгоритмами с формальной точки зрения. Новый подход, именуемый далее - обобщенная вычислимость, трактует алгоритм как конечный, дискретный, целенаправленный и детерминированный процесс, но работающий с элементами некоторой фиксированной алгебраической системы Структура рекурсивных m-степеней в поляхсигнатуры Структура рекурсивных m-степеней в полях. При этом элементарными шагами обобщенного алгоритма являются вычисления значений констант, функций и предикатов системы Структура рекурсивных m-степеней в полях(см. [1,2,5,6]).

В качестве формализации обобщенной вычислимости будем использовать машину над списочной надстройкой из [1]. Эта машина представляет из себя конечный связный ориентированный граф с узлами четырех типов: входной узел, выходные, вычислительные и ветвления. Узел ветвления имеет две выходные дуги, с ним ассоциирована атомарная формула сигнатуры Структура рекурсивных m-степеней в полях, от истинности которой зависит выбор одной из этих дуг в процессе вычислений. Узлы остальных типов (кроме выходных) имеют одну выходную дугу, с такими узлами ассоциированы термы сигнатуры Структура рекурсивных m-степеней в полях. На входной узел машины подается набор элементов системы Структура рекурсивных m-степеней в полях, который передается от узла к узлу по дугам графа; в узлах элементы изменяются под действием ассоциированных термов. При достижении выходного узла работа машины прекращается, полученные элементы системы выдаются как результат. Подробности см. в [1].

Имея машину, можно определить понятие функции, вычислимой в системе Структура рекурсивных m-степеней в полях. Однако при этом полученный класс вычислимых функций будет достаточно мал (обоснование см. в [1,2]), поэтому предложенная формализация нуждается в улучшении. Один из возможных способов решения данной проблемы - усилить определение машины, разрешив машины со счетчиками, стеками и массивами (см. обзор [2]). Другой подход состоит в использовании списочной надстройки, введенной в [3]. Пусть A - множество, определим множество Структура рекурсивных m-степеней в полях, состоящее из всевозможных списков (конечных последовательностей) элементов A, включая пустой список Структура рекурсивных m-степеней в полях. Положим по индукции L0 = A, Структура рекурсивных m-степеней в полях, Структура рекурсивных m-степеней в полях. Множество HL(A) называется cписочным расширением множества A. Списочная надстройка системы Структура рекурсивных m-степеней в поляхесть система Структура рекурсивных m-степеней в полях, где Структура рекурсивных m-степеней в полях. Константа Структура рекурсивных m-степеней в поляхинтерпретируется как пустой список, операции Структура рекурсивных m-степеней в поляхи Структура рекурсивных m-степеней в поляхесть взятие первого элемента списка x и удаление из списка x первого элемента соответственно, Структура рекурсивных m-степеней в полях.

Функция Структура рекурсивных m-степеней в поляхназывается вычислимой в системе Структура рекурсивных m-степеней в полях, если f вычисляется некоторой машиной, примененной к списочной надстройке Структура рекурсивных m-степеней в полях. Множество Структура рекурсивных m-степеней в поляхназовем рекурсивным в Структура рекурсивных m-степеней в полях, если его характеристическая функция Структура рекурсивных m-степеней в поляхвычислима в Структура рекурсивных m-степеней в полях. Множество Структура рекурсивных m-степеней в поляхрекурсивно перечислимо (р.п.) в Структура рекурсивных m-степеней в полях, если оно является областью определения вычислимой функции, X - выходное в системе Структура рекурсивных m-степеней в полях, если оно есть множество значений некоторой вычислимой функции. В общем случае классы р.п. и выходных множеств различны (примеры см. в [1]).В дальнейшем, если ясно, о какой системе идет речь, слова "в системе Структура рекурсивных m-степеней в полях", будем опускать.

Справедлив аналог теоремы Поста: множество Структура рекурсивных m-степеней в поляхрекурсивно Структура рекурсивных m-степеней в поляхX и его дополнение Структура рекурсивных m-степеней в поляхрекурсивно перечислимы. Доказательство в [1].

Вычислимость в системе Структура рекурсивных m-степеней в поляхсовпадает с классической вычислимостью, определяемой с помощью машины Тьюринга.

Лемма 1. Всякое рекурсивно перечислимое множество Структура рекурсивных m-степеней в поляхопределяется дизъюнкцией вида

Структура рекурсивных m-степеней в полях

(1)

где Структура рекурсивных m-степеней в полях- рекурсивно перечислимое по Тьюрингу множество бескванторных попарно несовместных формул сигнатуры Структура рекурсивных m-степеней в полях. Обратно, любая р.п. дизъюнкция бескванторных формул сигнатуры Структура рекурсивных m-степеней в поляхопределяет рекурсивно перечислимое множество Структура рекурсивных m-степеней в полях.

Это вариант леммы Энгелера для вычислимости в списочной надстройке, ее доказательство можно найти в [1]. Из леммы 1 и теоремы Поста следует, что если Структура рекурсивных m-степеней в полях- бескванторная формула, то множество Структура рекурсивных m-степеней в поляхрекурсивно.

Определение 2. Множество X m сводится к Y (Структура рекурсивных m-степеней в полях), если существует всюду определенная вычислимая функция Структура рекурсивных m-степеней в полях, что Структура рекурсивных m-степеней в полях

Множества X и Y m-эквивалентны (Структура рекурсивных m-степеней в полях), если Структура рекурсивных m-степеней в полях

m-степень множества X есть множество Структура рекурсивных m-степеней в полях.

m-степень рекурсивна (р.п.), если она содержит хотя бы одно рекурсивное (р.п.) множество.

Так же, как и в классической теории алгоритмов, доказывается следующая лемма (см., например, [4]).

Лемма 3. Справедливы следующие утверждения:

1) отношение Структура рекурсивных m-степеней в поляхрефлексивно и транзитивно;

2) рекурсивная m-степень состоит только из рекурсивных множеств;

3) Структура рекурсивных m-степеней в полях.

Известно [4], что в арифметике существует только три рекурсивные m-степени: Структура рекурсивных m-степеней в полях, Структура рекурсивных m-степеней в поляхи степень всех остальных рекурсивных множеств. В данной работе описывается структура рекурсивных m-степеней в полях с трансцендентными элементами.

Итак, пусть Структура рекурсивных m-степеней в полях- поле, рассматриваемое в сигнатуре Структура рекурсивных m-степеней в полях- его простое подполе. Предполагаем, что Структура рекурсивных m-степеней в поляхсодержит трансцендентные над Структура рекурсивных m-степеней в поляхэлементы.

Лемма 4. Множество Структура рекурсивных m-степеней в поляхрекурсивно Структура рекурсивных m-степеней в поляходно из множеств X или [Структура рекурсивных m-степеней в полях] состоит из конечного набора алгебраических над Структура рекурсивных m-степеней в поляхэлементов и вместе с каждым элементом содержит все алгебраически сопряженные с ним (т.е. корни того же самого минимального многочлена).

Доказательство. Пусть Структура рекурсивных m-степеней в полях, Структура рекурсивных m-степеней в полях- минимальные многочлены для элементов X, причем вместе с каждым ai множество X содержит и все остальные корни fi(x). Тогда Структура рекурсивных m-степеней в полях- рекурсивное отношение.

Пусть Структура рекурсивных m-степеней в поляхрекурсивно над Структура рекурсивных m-степеней в полях'. Тогда X и [Структура рекурсивных m-степеней в полях] определяются рекурсивными дизъюнкциями бескванторных формул Структура рекурсивных m-степеней в поляхи Структура рекурсивных m-степеней в поляхвида (1).

Случай 1. Одна из Структура рекурсивных m-степеней в поляхесть конечная конъюнкция неравенств вида Структура рекурсивных m-степеней в полях. Такой Структура рекурсивных m-степеней в поляхбудут удовлетворять все элементы поля Структура рекурсивных m-степеней в полях, за исключением конечного числа алгебраических элементов, т.е. X есть множество требуемого вида.

Случай 2. Все Структура рекурсивных m-степеней в поляхсодержат хотя бы одно равенство вида t(x) = 0. Тогда множество X не содержит ни одного трансцендентного элемента, следовательно, существует Структура рекурсивных m-степеней в полях, которой удовлетворяют трансцендентные элементы, но тогда Структура рекурсивных m-степеней в поляхсодержит только одни неравенства Структура рекурсивных m-степеней в полях. Таким образом, мы приходим к случаю 1 с заменой X на его дополнение.

Лемма 5. Если функция Структура рекурсивных m-степеней в поляхвычислима в системе Структура рекурсивных m-степеней в полях, то для любых Структура рекурсивных m-степеней в поляхСтруктура рекурсивных m-степеней в поляхпринадлежит подсистеме системы Структура рекурсивных m-степеней в полях, порожденной элементами Структура рекурсивных m-степеней в полях.

Доказательство. См. в [1].

Теорема 6. Пусть Структура рекурсивных m-степеней в полях, Структура рекурсивных m-степеней в поляхрекурсивные множества. Тогда Структура рекурсивных m-степеней в поляхкаждое поле Структура рекурсивных m-степеней в поляхсодержит одно из полей Структура рекурсивных m-степеней в полях.

Доказательство. Пусть Структура рекурсивных m-степеней в полях. Тогда найдется вычислимая функция f(x), что Структура рекурсивных m-степеней в полях. По лемме 5, f(ai), есть значение некоторого терма сигнатуры Структура рекурсивных m-степеней в поляхт.е. рациональной функции с коэффициентами из поля Структура рекурсивных m-степеней в полях. Значит, Структура рекурсивных m-степеней в полях, т.е. Структура рекурсивных m-степеней в полях.

Обратно, пусть Структура рекурсивных m-степеней в полях, Структура рекурсивных m-степеней в полях, т.е. ti(ai) = bi для некоторого набора рациональных функций Структура рекурсивных m-степеней в полях. Тогда Структура рекурсивных m-степеней в поляхпосредством вычислимой функции

Структура рекурсивных m-степеней в полях

Непосредственно из определения следует, что Структура рекурсивных m-степеней в поляхдля любого конечного Y.

Следствие 7. Справедливы следующие утверждения:

1) если X конечное рекурсивное множество и Структура рекурсивных m-степеней в полях, то любое конечное рекурсивное Y сводится к X;

2) для рекурсивного X имеем: Структура рекурсивных m-степеней в поляхи Структура рекурсивных m-степеней в полях;

3) среди рекурсивных m-степеней существует наибольшая, это степень множества X из п.2.

Доказательство. 1. Следует из теоремы.

2. По лемме 4 можно считать, что множество X конечно, а Структура рекурсивных m-степеней в поляхконечно. Тогда существует a Структура рекурсивных m-степеней в полях. Если Структура рекурсивных m-степеней в поляхи f сводящая функция, то Структура рекурсивных m-степеней в полях, но по лемме 5 f(a) есть значение некоторой рациональной функции с коэффициентами из Структура рекурсивных m-степеней в полях, т.е. Структура рекурсивных m-степеней в полях. Обратно, если существует Структура рекурсивных m-степеней в полях, то X и [Структура рекурсивных m-степеней в полях] сводятся друг к другу посредством функции

Структура рекурсивных m-степеней в полях

3. Пусть X конечное рекурсивное множество и Структура рекурсивных m-степеней в полях. Пусть Y произвольное рекурсивное. Если Y конечно, то Структура рекурсивных m-степеней в поляхпо п.1. Если Y коконечно, то Структура рекурсивных m-степеней в поляхпо лемме 3, но Структура рекурсивных m-степеней в полях. Таким образом, упорядочение рекурсивных m-степеней в поле Структура рекурсивных m-степеней в поляхимеет вид:

Структура рекурсивных m-степеней в полях

Если в поле Структура рекурсивных m-степеней в поляхдостаточно много алгебраических элементов, например, если Структура рекурсивных m-степеней в поляхалгебраически замкнуто, то существует бесконечное число рекурсивных m-степеней.

Следствие 8. Пусть поле Структура рекурсивных m-степеней в поляхалгебраически замкнутое характеристики 0, a рекурсивная m-степень, Структура рекурсивных m-степеней в поляхи не является наибольшей среди рекурсивных. Тогда:

1) существует счетное число рекурсивных степеней, несравнимых с a;

2) существует счетное число попарно несравнимых степеней Структура рекурсивных m-степеней в полях, таких, что Структура рекурсивных m-степеней в полях;

3) существует счетное число попарно несравнимых степеней Структура рекурсивных m-степеней в полях, таких, что Структура рекурсивных m-степеней в полях;

4) порядок на рекурсивных m-степенях плотный.

Доказательство. Пункты 1) - 3) следуют из теоремы 6 и свойств алгебраических расширений полей. Для доказательства 4) рассмотрим рекурсивные множества Структура рекурсивных m-степеней в полях. Можно считать, что Структура рекурсивных m-степеней в поляхи Структура рекурсивных m-степеней в полях, причем X и Y не содержат элементов из Структура рекурсивных m-степеней в полях. Тогда Структура рекурсивных m-степеней в полях, где Структура рекурсивных m-степеней в полях, Структура рекурсивных m-степеней в полях, но Структура рекурсивных m-степеней в полях.

Список литературы

Ашаев И.В., Беляев В.Я., Мясников А.Г. Подходы к теории обобщенной вычислимости // Алгебра и логика. 32. N 4 (1993). С. 349-386.

Кфури А. Дж., Столбоушкин А.П., Ужичин П. Некоторые открытые вопросы в теории схем программ и динамических логик // УМН. 1989. Т.44. Вып.1 (265). С. 35-55.

Гончаров С.С., Свириденко Д.И. Структура рекурсивных m-степеней в полях-программирование// Логико-математические проблемы МОЗ (Вычислительные системы. Вып. 107). Новосибирск, 1985. С. 3-29.

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

Blum L., Shub M., Smale S. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines //Bull. Amer. Math. Soc. 1989. V.21. N1. P.1-46.

Friedman H. Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory //Logic Colloquium'69 (R.O. Gandy and C.E.M. Yates, eds). North Holland, 1971. Р. 361-390.

©2007—2016 Пуск!by | По вопросам сотрудничества обращайтесь в contextus@mail.ru