Структура рекурсивных m-степеней в полях
Структура рекурсивных m-степеней в полях
И.В. Ашаев, Омский государственный университет, кафедра математической логики
Обычная теория алгоритмов изучает
вычислимость над конструктивными
объектами, которые допускают эффективное
кодирование натуральными числами. При
этом многие процессы в математике,
имеющие интуитивно алгоритмическую
природу, но работающие в неконструктивных
областях (например, в вещественных
числах), не являются алгоритмами с
формальной точки зрения. Новый подход,
именуемый далее - обобщенная вычислимость,
трактует алгоритм как конечный,
дискретный, целенаправленный и
детерминированный процесс, но работающий
с элементами некоторой фиксированной
алгебраической системы
сигнатуры
.
При этом элементарными шагами обобщенного
алгоритма являются вычисления значений
констант, функций и предикатов системы
(см.
[1,2,5,6]).
В качестве
формализации обобщенной вычислимости
будем использовать машину над списочной
надстройкой из [1]. Эта машина представляет
из себя конечный связный ориентированный
граф с узлами четырех типов: входной
узел, выходные, вычислительные и
ветвления. Узел ветвления имеет две
выходные дуги, с ним ассоциирована
атомарная формула сигнатуры
,
от истинности которой зависит выбор
одной из этих дуг в процессе вычислений.
Узлы остальных типов (кроме выходных)
имеют одну выходную дугу, с такими узлами
ассоциированы термы сигнатуры
.
На входной узел машины подается набор
элементов системы
,
который передается от узла к узлу по
дугам графа; в узлах элементы изменяются
под действием ассоциированных термов.
При достижении выходного узла работа
машины прекращается, полученные элементы
системы выдаются как результат.
Подробности см. в [1].
Имея машину,
можно определить понятие функции,
вычислимой в системе
.
Однако при этом полученный класс
вычислимых функций будет достаточно
мал (обоснование см. в [1,2]), поэтому
предложенная формализация нуждается
в улучшении. Один из возможных способов
решения данной проблемы - усилить
определение машины, разрешив машины со
счетчиками, стеками и массивами (см.
обзор [2]). Другой подход состоит в
использовании списочной надстройки,
введенной в [3]. Пусть A - множество,
определим множество
,
состоящее из всевозможных списков
(конечных последовательностей) элементов
A, включая пустой список
.
Положим по индукции L0 = A,
,
.
Множество HL(A) называется cписочным
расширением множества A. Списочная
надстройка системы
есть
система
,
где
.
Константа
интерпретируется
как пустой список, операции
и
есть
взятие первого элемента списка x и
удаление из списка x первого элемента
соответственно,
.
Функция
называется
вычислимой в системе
,
если f вычисляется некоторой машиной,
примененной к списочной надстройке
.
Множество
назовем
рекурсивным в
,
если его характеристическая функция
вычислима
в
.
Множество
рекурсивно
перечислимо (р.п.) в
,
если оно является областью определения
вычислимой функции, X - выходное в системе
,
если оно есть множество значений
некоторой вычислимой функции. В общем
случае классы р.п. и выходных множеств
различны (примеры см. в [1]).В дальнейшем,
если ясно, о какой системе идет речь,
слова "в системе
",
будем опускать.
Справедлив
аналог теоремы Поста: множество
рекурсивно
X
и его дополнение
рекурсивно
перечислимы. Доказательство в [1].
Вычислимость
в системе
совпадает
с классической вычислимостью, определяемой
с помощью машины Тьюринга.
Лемма 1. Всякое
рекурсивно перечислимое множество
определяется
дизъюнкцией вида
|
(1) |
где
-
рекурсивно перечислимое по Тьюрингу
множество бескванторных попарно
несовместных формул сигнатуры
.
Обратно, любая р.п. дизъюнкция бескванторных
формул сигнатуры
определяет
рекурсивно перечислимое множество
.
Это вариант
леммы Энгелера для вычислимости в
списочной надстройке, ее доказательство
можно найти в [1]. Из леммы 1 и теоремы
Поста следует, что если
-
бескванторная формула, то множество
рекурсивно.
Определение
2. Множество X m сводится к Y (),
если существует всюду определенная
вычислимая функция
,
что
Множества X и
Y m-эквивалентны (),
если
m-степень
множества X есть множество
.
m-степень рекурсивна (р.п.), если она содержит хотя бы одно рекурсивное (р.п.) множество.
Так же, как и в классической теории алгоритмов, доказывается следующая лемма (см., например, [4]).
Лемма 3. Справедливы следующие утверждения:
1) отношение
рефлексивно
и транзитивно;
2) рекурсивная m-степень состоит только из рекурсивных множеств;
3)
.
Известно [4],
что в арифметике существует только три
рекурсивные m-степени:
,
и
степень всех остальных рекурсивных
множеств. В данной работе описывается
структура рекурсивных m-степеней в полях
с трансцендентными элементами.
Итак, пусть
-
поле, рассматриваемое в сигнатуре
-
его простое подполе. Предполагаем, что
содержит
трансцендентные над
элементы.
Лемма 4. Множество
рекурсивно
одно
из множеств X или [
]
состоит из конечного набора алгебраических
над
элементов
и вместе с каждым элементом содержит
все алгебраически сопряженные с ним
(т.е. корни того же самого минимального
многочлена).
Доказательство.
Пусть
,
-
минимальные многочлены для элементов
X, причем вместе с каждым ai множество X
содержит и все остальные корни fi(x). Тогда
-
рекурсивное отношение.
Пусть
рекурсивно
над
'.
Тогда X и [
]
определяются рекурсивными дизъюнкциями
бескванторных формул
и
вида
(1).
Случай 1. Одна
из
есть
конечная конъюнкция неравенств вида
.
Такой
будут
удовлетворять все элементы поля
,
за исключением конечного числа
алгебраических элементов, т.е. X есть
множество требуемого вида.
Случай 2. Все
содержат
хотя бы одно равенство вида t(x) = 0. Тогда
множество X не содержит ни одного
трансцендентного элемента, следовательно,
существует
,
которой удовлетворяют трансцендентные
элементы, но тогда
содержит
только одни неравенства
.
Таким образом, мы приходим к случаю 1 с
заменой X на его дополнение.
Лемма 5. Если
функция
вычислима
в системе
,
то для любых
принадлежит
подсистеме системы
,
порожденной элементами
.
Доказательство. См. в [1].
Теорема 6. Пусть
,
рекурсивные
множества. Тогда
каждое
поле
содержит
одно из полей
.
Доказательство.
Пусть
.
Тогда найдется вычислимая функция f(x),
что
.
По лемме 5, f(ai), есть значение некоторого
терма сигнатуры
т.е.
рациональной функции с коэффициентами
из поля
.
Значит,
,
т.е.
.
Обратно, пусть
,
,
т.е. ti(ai) = bi для некоторого набора
рациональных функций
.
Тогда
посредством
вычислимой функции
Непосредственно
из определения следует, что
для
любого конечного Y.
Следствие 7. Справедливы следующие утверждения:
1) если X конечное
рекурсивное множество и
,
то любое конечное рекурсивное Y сводится
к X;
2) для рекурсивного
X имеем:
и
;
3) среди рекурсивных m-степеней существует наибольшая, это степень множества X из п.2.
Доказательство. 1. Следует из теоремы.
2. По лемме 4
можно считать, что множество X конечно,
а
конечно.
Тогда существует a
.
Если
и
f сводящая функция, то
,
но по лемме 5 f(a) есть значение некоторой
рациональной функции с коэффициентами
из
,
т.е.
.
Обратно, если существует
,
то X и [
]
сводятся друг к другу посредством
функции
3. Пусть X
конечное рекурсивное множество и
.
Пусть Y произвольное рекурсивное. Если
Y конечно, то
по
п.1. Если Y коконечно, то
по
лемме 3, но
.
Таким образом, упорядочение рекурсивных
m-степеней в поле
имеет
вид:
Если в поле
достаточно
много алгебраических элементов, например,
если
алгебраически
замкнуто, то существует бесконечное
число рекурсивных m-степеней.
Следствие 8.
Пусть поле
алгебраически
замкнутое характеристики 0, a рекурсивная
m-степень,
и
не является наибольшей среди рекурсивных.
Тогда:
1) существует счетное число рекурсивных степеней, несравнимых с a;
2) существует
счетное число попарно несравнимых
степеней
,
таких, что
;
3) существует
счетное число попарно несравнимых
степеней
,
таких, что
;
4) порядок на рекурсивных m-степенях плотный.
Доказательство.
Пункты 1) - 3) следуют из теоремы 6 и свойств
алгебраических расширений полей. Для
доказательства 4) рассмотрим рекурсивные
множества
.
Можно считать, что
и
,
причем X и Y не содержат элементов из
.
Тогда
,
где
,
,
но
.
Список литературы
Ашаев И.В., Беляев В.Я., Мясников А.Г. Подходы к теории обобщенной вычислимости // Алгебра и логика. 32. N 4 (1993). С. 349-386.
Кфури А. Дж., Столбоушкин А.П., Ужичин П. Некоторые открытые вопросы в теории схем программ и динамических логик // УМН. 1989. Т.44. Вып.1 (265). С. 35-55.
Гончаров С.С., Свириденко Д.И.
-программирование//
Логико-математические проблемы МОЗ
(Вычислительные системы. Вып. 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.
Для подготовки данной применялись материалы сети Интернет из общего доступа