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

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

Наш опрос Как Вы оцениваете работу нашего сайта? Отлично Не помог Результаты опроса Реклама   Мнение авторов может не совпадать с мнением редакции сайта Перепечатка материалов без ссылки на наш сайт запрещена