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

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