Структура рекурсивных 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. Всякое рекурсивно перечислимое множество определяется
дизъюнкцией вида
