Структура рекурсивных 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.
Для
подготовки данной работы были использованы материалы с сайта http://www.omsu.omskreg.ru/