Вычислимость в произвольных областях и базисах

Введение. Распространение ЭВМ и программирования делает математическую логику прикладной наукой. Каста математических логиков — жрецов-хранителей священного огня оснований математики — к своему изумлению, оказывается лицом к лицу с нашествием орд программистов, чья математическая культура близка к варварству, но которые, тем не менее, вдохновляемые своими пророками структурного программирования, стремятся зажечь факел от животворного огня и утащить его к себе, чтобы осветить углы своих подразделений, забитых лампами, инструкциями по ОС/360, фортрановскими бланками и прочими символами идолопоклонства. Тем не менее, для того, чтобы установить союз столь разных культур, каждой стороне — логикам и программистам — необходимо преодолеть свои комплексы неполноценности, выработать способность к взаимопониманию, а главное — увериться в своей интересности для другой стороны.

Эта описательная статья представляет собой персональную реакцию на сложившуюся ситуацию. Когда автор был аспирантом Московского университета в середине 50-х годов, он делил свое время между изучением известной книги С. К. Клини „Введение в математику“ (Клини, 1952) и разработкой трансляторов для машин БЭСМ и ,,Стрела“. Чтение книги заразило автора изумлением, с которым Клини (§62) говорил о необыкновенной устойчивости понятия вычислимости перед лицом самых важных предпосылок и способов его определения. С другой стороны, работа над трансляторами, над методологией программирования, над тем, что стало впоследствии теорией схем программ, — все это постоянно наталкивало автора на мысль, что в программировании надо уметь различать комбинаторную и собственно вычислительную стороны процесса вычислений. Мы то манипулируем с элементарными командами как с символами, то пускаем их в ход как окончательные орудия обработки информации. Ощущалось, что понимание взаимодей- ствия этих двух сторон вычислений является фундаментальной проблемой, требующей более глубокого раскрытия сущности вычислимости.

Прошло, однако, почти двадцать пять лет, прежде чем для автора стало ясным содержание возможной дискуссии. За это время теория вычислимости получила большое развитие, хотя, как не без сожаления констатировал Крайел, 1959, вопрос о сущности вычислимости был скорее периферийной, нежели центральной проблемой. За это же время возникло теоретическое программирование, в котором сложился свой круг понятий и свои модели вычислений (см., например, Манна, 1974; Ершов, 1977; Котов, 1978).

Мы проанализируем обе линии развития, как в теории вычислимости, так и в теоретическом программировании. Этому анализу мы предпошлем сводку тех основных определений вычислимости, которые возникли в связи с главной моделью в конструктивной математике — моделью вычислимых арифметических функций. Мы закончим наш анализ определением вычислимой функции, которое, как мы надеемся, обладает следующими достоинствами:

• —    оно определяет вычислимость в любой предметной области и любой системе базовых операций;

• —    оно четко разделяет комбинаторную и „исполнительную¹¹ стороны вычислимости;

• —    оно не опирается на какие бы то ни было специфические синтаксис программ и механизм их выполнения.

В заключении мы изложим ряд аргументов в пользу такого определения и некоторые построения теории вычислимости, основанной на этом определении. Существенным будет синтетический характер этих аргументов, взятых как из логики, так и из программирования.

В обзорной части работы автор ссылается, по возможности, на оригинальные работы. Однако, в ряде случаев реальными источниками были обобщающие трактаты, из которых нужно, прежде всего, назвать уже упомянутую книгу Клини, 1952, и недавно изданный компендиум по математической логике: Барвайз, 1977.

Часть 1. Вычислимость арифметических функций. Везде ниже мы будем рассматривать частичные однозначные функции, берущие свои аргументы и принимающие значения на множестве N, то есть на натуральном ряде, включающем нуль {0, 1,2,...}. Эти функции, образующие пространство А, мы будем называть арифметическими. Говоря об арифметических функциях вообще, мы не будем себя ограничивать абстракциями конструктивной математики. В классе А мы с помощью различных определений будем выделять подклассы арифметических функций, которые будут называться „вычислимыми функциями по XX“, где XX — имя одного из авторов данного определения. В дальнейшем окажется, что все эти подклассы совпадают, образуя класс вычислимых арифметических функций С. В классе С выделяется подкласс всюду определенных как тотальных вычислимых функций. Какой-либо из классов „вычислимых функций по ХХ“ может иногда именоваться особым термином, получившим распространение в литературе.

С понятием вычислимой функции тесно связаны понятия эффективно порождаемых (перечислимых) и эффективно выделяемых (разрешимых) множеств. Множество называется перечислимым, если оно или пусто или является областью значений тотальной вычислимой функции. Множество называется разрешимым, если его характеристическая функция является тотальной вычислимой функцией. Предикат называется вычислимым, если его область истинности является разрешимым множеством, и полувычислимым, если область его истинности перечислима.

В некоторых теориях понятие перечислимого множества является первичным, в таких случаях понятия вычислимой функции и разрешимого множества вводятся путем следующих определений. Функция называется вычислимой, если ее график перечислим. Множество называется разрешимым, если перечислимы как оно, так и его дополнение.

Представляется уместным расклассифицировать определения вычислимости по четырем классам: логические, функциональные, алгоритмические и арифметические определения. Логические определения выделяют в формальных логических системах класс вычислимых функций с помощью некоторых формул, обладающих определенными дедуктивными свойствами. Функциональные определения выделяют класс вычислимых функций в функциональном пространстве с помощью замыкания некоторых операций. Алгоритмические определения задают вычислимые функции описанием алгоритма, вычисляющего значение функции по указанному аргументу и по заданной программе. Наконец, арифметическое определение задает перечислимые множества как множества, возникающие при решении простейших арифметических уравнений.

Логические определения.

Изобразимость по Геделю. Рассматривается арифметическое исчисление предикатов S, например, по Клини, 1952, гл. IV, содержащее одну предметную константу 0, один предикатный знак =, три функциональных знака 0, +, •ив качестве нелогических аксиом аксиомы Пеано и рекурсивные определения для сложения + и умножения •. Исчисление содержит счетное множество предметных переменных (их метаобозначения x,y,x1,y1,.. .\

Функция ^(ту..... п^ пзобразпма в У если имеется формула P(xi .....з_п-у) такая, что

^(xi, ...,Xn)= у О 1 - P (cxi,. . . , CXn, cy), где ex- терм, изображающий натуральное число х (можно всегда считать, что он имеет вид 0 / ... / раз. Множество арифметических функций, изображаемых в арифметическом

x исчислении предикатов, образует класс вычислимых функций (по Геделю, 1936, формулируется по Клини, 1952, §59, 62).

Рекурсивная определимость по Эрбрану и Геделю. Рассматривается формальное исчисление уравнений над счетными множествами переменных для натуральных чисел х, у, х1, yi, ... и функциопальных букв f, g, h, f 1, g1, h1, ..., содержащее одну предметную константу 0 и один функциональный символ ‘, а также разделители =, (, ) и ,. Термами являются 0, переменные, г’, где r — терм, и f(r1, ... , rn), где f — функциональная буква, a r1 rn (n>0) — термы. Уравпенне имеет вид r = s. тле ii r. ii s — термы. Система уравнений — это конечная последовательность уравнений E ={e₀, ..., es}. Самая левая функциональная буква в последнем уравнении es называется главной буквой. Даны два правила вывода.

R 1 (коикретцзация): e(y) |-e(c). где е(у) — уравнение, содержащее переменную у. a c — любая цифра, т. е. терм 0 или 0/"^./;

R 2 (замсна): r = s(h(c1, ..., cp)), h(c1,.. .,cp) = c| — r = s(c). г,те s(h(c1 cp)) — терм, содержащий вхождение терма h(c1, ..., cp), в ко тором h — функциональная буква, c1, ..., cpc — цифры.

Функция ^(х1,.. .,xn) рекурсивно определима, естi имеется система, уравнений E. такая, что

^(xi, . . . , Хп) = у О E | — f (cxi,..., cxn) = cy, где f — главная буква в Е, сж - цифра, изображающая число х. Множество рекурсивно определимых арифметических функций образует класс вычислимых функций (по Эрбра-ну, 1931, Геделю, 1934, сформулировано по Клини, 1952, § 55).

А-опрсделимыс функции по Черчу. Над счетным алфавитом переменных V строится множество термов T: а) VET б) xEV, tET ^(Ах 1)ЕТ(рассмотрение терма t как функции от х); в) tET(npHMeneHHe терма-функции t к терму-аргументу u). Из термов строится множество формул F: a) s. tEV^ (s^l) EF (s редутщруется к l): б) s. LEV ^(s=1)eF(s равно t). Для сокращения числа скобок используются следующие упрощения: (1) t1t₂... tn= (... (1 112)... tn) и (2) Ах1... xn. 1== (Ах 1 (Ах 2.. . (Ахnt)...)). Последнее сокращение одновременно подсказывает, как в языке „вычисляются" функции многих переменных: 1x1x2.. .xn вычисляются так, что применяется f к х 1, затем 1x1 применяется к х₂ и т. д.

Над формулами строится А-исчисление со следующими аксиомами и правилами вывода.

• I.    1. (Ах.s)t^s[x/t] (правая часть редукции означает терм s, в котором все свободные

вхождения х заменены на терм 1); 2. s>s: 3. s^t, t >u  s^u; 4. (a) s ^ t | — us ^ ut; (b)

s ^ I | — su ^ tu: (c) s ^ I | — Ах.s ^ АхД:

• II.    1. s ^ I |— s = I: 2. s ^ I | — I = s: 3. s = t. I =u | — s = ir: 4. (a) s =t | — us = ut: (b)

s =t | — su = tu: (c) s=t |— Ахл=АхД.

Натуральные числа можно изображать в виде термов А-исчисления. Вот один из способов (n- изображение числа, n): n= А1х.fnx. где f°x = х. fn+1x = f(fnx). Арифметическая функция ^(х1, ..., жп) А-определима, если существует такой замкнутый (т. е. без свободных переменных) терм 1, что

^(xi, . . . ,Хп) О | — fxi, . . . , Xn = y.

Множество А-определимых функций образует класс вычислимых функций по Черчу (Черч, 1936, 1941); сформулировано по Барендрегту, (Барендрегт, 1977).

Функциональные определения.

Частичная рекурсивность по Клини. Берется счетный базис арифметических функций:

• 1)    функции счета S(х)=’;

• 2)    функции-константы Сⁿ(х₁, ..., ж_п) = с, где с— натуральное число;

• 3)    функции выбора аргумента Uin(х₁, ..., ж_п)=ж^ Далее, рассматриваются три типа операторов, т. е. схем определения новых функций через данные:

• 4)    оператор подстановки ^ = Sm(^, Х1, • • •, Xm), Д^ля которого

^(xi, . . . ,Xn) = ^(X1(xi, • • • ,Xn), . . . ,^m(xi, . . . ,Xn));

5)оператор примитивной рекурсии ^ == Rn(^х), Для которого

^(0,Х2, . . . ,Хп) = ^(Х2, . . . ,Xn),

^(y0,Х2,... ,Xn) = х(у,^(у,Х2,... ,Xn),X2,... ,хД;

6)ц-опсратор. пли оператор упорядоченного поиска ^ = Mn (х). для которого ^(xi,... ,xn) = цу[х(х1,... ,xn,y) = 0],

• т. с. ^(х₁..... х_Т^ равно на:шеньшему у. для которого х(х₁..... n_n- y)=0. и для всех у’<уА(х₁, ..., п_п, у)=0, и неопределенно, если такого у не существует.

Указанные операторы позволяют рассматривать замыкания базисных функций этими операторами и их комбинациями. При этом интересно выделить три класса функций:

• а)    замыкание оператором подстановки создает класс прямо вычислимых функций;

• б)    замыкание операторами подстановки и примитивной рекурсии создает класс примитивно рекурсивных функций (Гедель, 1931);

• в)    замыкание всеми тремя операторами создает класс частично рекурсивных функций, образующих класс вычислимых функций по Клини (Клини, 1938), сформулировано по Клини (Клини, 1952, § 63).

Наименьшие неподвижные точки рекурсивных программ по Маккарти. Рассматривается формальный язык функциональных уравнений, содержащий счетные множества переменных для натуральных чисел х, у, х_1; у_1; ... и функциопальных букв f, g, h, fi, gi, hi. одну предметную константу 0, один функциональный символ 0, один предикатный символ = (равенство), а также разделители ^ (,) и , . Каждой функциональной букве f сопоставляется ее арность: целое число p(f)>0. Именами функций являются выражения f (х1,... ,x_p(f )), где f— функциональная буква, а x_i,... ,x_p(f ) — разные переменные. Функциональными термами являются 0, переменные, г⁰, где r — функциональный терм, и f (r_i,..., r_p(f)), г де f — функциональная буква, a r_i,..., r_p(f ) — функциональные термы. Предикатные термы имеют вид х = у, где х и у — переменные. Условные термы имеют вид (p|r|s), где — предикатный терм, a r и s — функциональные или условные термы. Значение val условного терма определяется по правилу разбора случаев:

val(p|r|s) =

{val r, var s,

если p если —p

Уравнением называется выражение вида f (x_i, ... ,x_p(f )) ^ t, где t — функциональный или условный терм с переменными, принадлежащими множеству {x_i,... ,x_p(f )}• Система уравнений е _iv .. ,en (n>0) называется совместной, если она не содержит уравнений с одинаковыми функциональными буквами и для любой функциональной буквы, входящей в правую часть какого-либо уравнения, есть уравнение с именем, содержащим эту букву. Рекурсивной программой называется совместная система уравнений, в которой выделено одно главное уравнение. Неподвижной точкой системы совместных уравнений е 1, ... ,en называется совокупность частичных функций ^1, ... ,^n, обращающих систему уравнений в тождественные равенства (если заменить ^ па ). Существует эффективное доказательство существования для любой совместной системы уравнений наименьшей неподвижной точки, т. е. такой совокупности функций ^1*, . .. ,^n*, что для любой другой неподвижной точки ^1, . ^ np_n имеет место ^i* C^i (i=l,...,n). Наименьшей неподвижной точкой рекурсивной программы является таковая для главного уравнения. Класс наименьших неподвижных точек рекурсивных, программ образует класс вычислимыхфункций по Маккарти (Маккарти, 1961) и Манне (Манна, 1974, гл. IV).

Примечание. Рассмотрим уравнение f (xi,... ,xn) ^ t(xi, ...,xn, f; gi,... ,gk), где gi, ... ,gk — другие функциональные буквы, входящие в t. Сопоставим этим буквам некоторые арифметические функции Ai, ... ,Ak и рассмотрим наименьшую неподвижную точку ^(xi xn) получившегося ура,висиия относительно f. Тогда, выражение t можно рассматривать как оператор у = Lubn[t, Ai, ... ,Ak] взятия неподвижной точки. Замыкание пустого множества функций оператором взятия наименьшей неподвижной точки также образует класс вычислимых функций по Маккарти.

Алгоритмические определения.

Машины Тьюринга. Рассматривается язык программ для машин Тьюринга. Машина Тьюринга работает с бесконечной в обе стороны лентой, разделенной на клетки, в каждой из которых может находиться или быть записанным пустой символ или „единица “. Машина, может находиться в отюм из конечного числа, состояний q₀. q1 q^. одно из которых q₀ является пассивным, заключительным, а остальные — активными. Одно из активных состояний q1 считается начальным. В любом состоянии машина обозревает некоторую клетку ленты. Машина может выполнять следующие операции: определить содержимое обозреваемой клетки, записать в клетку пустой символ или единицу, сдвинуться вдоль ленты на одну клетку вправо или влево или остаться на месте, перейти из одного состояния в другое (в том числе в то же самое). Программа для машины Тьюринга с к активными состояниями имеет вид матрицы порядка kx2. В позиции матрицы (i. j) указывается, что делает машина, находясь в i-м состоянии и обнаруживая в обозреваемой клетке j-й символ ( j = 1 пусто, j = 2 единица). Действие указывается набором aeY- где а — символ, который пишется на обозреваемую клетку, в — характер движения вдоль ленты (влево, на месте, вправо), y — состояние, в которое переходит машина.

Для каждой программы указывается, от какого числа n аргументов зависит функция, вычисляемая данной машиной (n>0). Задание набора аргументов х1, ..., х_n на ленте выглядит так: Х1+1 единиц, пусто, х₂+1 единиц, пуст о и т. д. — до ж_п+1 единиц. По обе стороны от части, занимаемой аргументами, лента предполагается пустой. Машина, находясь в начальном состоянии, обозревает крайнюю слева, единицу в записи аргументов, после чего начинается работа, по программе до тех пор, пока машина не перейдет в конечное состояние. Если при этом на ленте останется блок из у + 1 единиц и машина будет в заключительном состоянии обозревать крайнюю слева единицу, то в этом и только в этом случае у будет считаться значением функции, задаваемой данной машиной Тьюринга (более точно, ее программой). Множество частичных арифметических функций, задаваемых машинами Тьюринга, образует класс вычислимых функций по Тьюрингу (Тьюринг, 1936); сформулировано по Клини (Клини, 1952, § 67).

Операторные алгоритмы по Ершову. Рассматривается язык программ для операторных алгоритмов, содержащий счетное множество переменных для натуральных чисел х, у, х 1, у1,..., одну предметную константу 0, один функциональный символ ’, один предикатный символ = (равенство), а также разделитель := (знак присваивания). Термами являются 0, переменные и г’, где г — терм. Присваивание имеет вид х:= г, где х — переменная иг — терм. Условие имеет вид х = у, где х и у — переменные. Графом переходов является ориентированный граф с выделенными входной и выходной вершинами. Все вершины (кроме выходной) в графе делятся на две категории — преобразователи, имеющие ровно одного преемника, и распознаватели, имеющие ровно двух преемников (плюс-преемник и минус-преемник). Операторным алгоритмом А(х1, ... ,xn,y) называется граф переходов, в котором каждому преобразователю сопоставлено некоторое присваивание и каждому распознавателю — некоторое условие, а выходной вершине — переменная у. Выполнение операторного алгоритма, состоящее в вычислении значения у как некоторой функции ^(х1 nn\ состоит в следующем. Все пер*змеиные. входящие в программу A. образуют память этой программы. Задаются начальные значения х1, ... ,хn переменных х 1, ... ,xn, и управление передается начальной вершине графа переходов. Если управление передано преобразователю с присваиванием х:=г и аргумент терма г определен, то значение этого терма присваивается переменной х, и управление передается единственному преемнику преобразователя. Если управление передается распознавателю с условием х = у, то в случае заданности х и у управление передается плюс- или минус-преемнику в зависимости от истинности или ложности предиката х = у. Если управление передано на выход с переменной у и у имеет значение у, то оно берется в качестве значения функции ^(xi, .. • ,жп). Множество функций, вычисляемых операторными алгоритмами, образует класс вычислимых функций по Ершову (Ершов, 1958).

Арифметическое определение.

Арифметические определения задают перечислимые множества, возникающие при рассмотрении системы уравнений, построенных из термов в некотором базисе простых арифметических функций и содержащих неотрицательные константы, параметры и неизвестные. В качестве множеств, представимых уравнениями, рассматриваются множества значений параметров, при которых уравнения разрешимы в целых (неотрицательных, положительных) числах.

Диофантова вычислимость по Матиясевичу. Рассматриваются обычные полиномы с целыми коэффициентами и переменными у₀, у1,... ,уn x1, .. . ^l , пробегающими натуральное значение. Множество M ={(д₀, Щ, • • •, Д_п)} является диофантовым, если существует полином P(y₀, у1,... щ_п, х1, .. . Ду), такой что (д₀, щ, ..., ^n)eM тогда и только тогда, когда уравнение

р(Д0, Д1, . . . , Дп,Х1, ... ,xi ) = 0

имеет решение. Множество функций, графики которых являются диофантовыми множествами, образует класс вычислимых функций по Матиясевичу (Матиясевич, 1970).

Общая теория вычислимости.

Устойчивость. Одним из самых замечательных и удивительных достижений современной математики является постепенное обнаружение того факта, что все эти определения вычислимости, а также ряд других, им родственных* задают один и тот же класс С арифметических функций (рис. 1), которые мы и будем называть вычислимыми (неважно, на основе какого определения). Мало того, каждая теория вычислимых функций и/или перечислимых множеств, строящаяся над каждым определением, обнаруживала в себе ряд фундаментальных свойств, выглядящих по сути своей сходно с построениями „параллельной “ теории. Естественно, что со временем это сходство стали выискивать сознательно, как бы желая, чтобы каждый новый вариант теории вычислимости был бы похож на остальные. Однако к моменту наступления такого периода насыщения теория вычислимости накопила некоторую систему фундаментальных фактов и закономерностей, проливающих свет на сущность вычислимости, а также позволяющих работать с этим понятием в других областях математики и ее приложений.

Не претендуя на полноту, дадим краткий очерк общей теории вычислимости, имея в виду ее так называемую элементарную часть. Существенно более полный обзор теории вычислимости и ее применений можно найти у В. А. Успенского и А. Л. Семенова (Успенский, Семенов, 1981).

Универсальный алгоритм. Для каждой вычислимой функции (перечислимого множества) существует конечный источник (программа) исчерпывающей информации об этой функции (множестве), являющийся эффективно определимой конструкцией некоторого формального языка. Существует процедура, удовлетворяющая неформальным критериям эффективности (кодировка), взаимно-однозначно отображающая множество программ во множество натуральных чисел. Это отображение может быть распространено на весь натуральный ряд (нумерация). Существует универсальная процедура, удовлетворяющая неформальным критериям эффективности, гарантирующая для любой программы функции у II любого набора. x1,..., xn аргументов пола’чепие 'значения ^(x1,..., xn) при условии, что это значение ^(x1,...,xn) определено. Эффективность этой процедуры находит свое подтверждение в том, что при подходящей нумерации универсальная функция Un(z,x1,..., xn). т. с. такая, что д.ля любого номера пф вычислимой функции у от n аргументов

Un(z,xi,... ,Xn) = ^(xi,... ,Xn), сама оказывается вычислимой функцией.

Относительная вычислимость. Всем определениям вычислимости с той или иной степенью естественности может быть придан индуктивный характер, где в качестве базиса индукции постулируется вычислимость некоторых элементарных арифметических функций. Определение класса, вычислимых функций может быть релятивизировано к конечному набору Д1, .. ^ ^i произвольных арифметических функций (оракулов), значения которых ищутся, вообще говоря, внешним по отношению к теории вычислимости способом. Класс функций, вычислимых относительно набора Д1, ..., Д, называется вычислимым замыканием функций Д1, ..., ^l.

Если в формализме относительной вычислимости рассмотреть некоторую программу P(Д1, ..., Д), то при разных исходных функциях Д,..., Д мы будем получать либо разные функции, задаваемые этой программой, либо разные значения (если зафиксированы числовые аргументы программы). Таким образом, с каждой программой можно связать вычислимый оператор или вычислимый функционал.

Замкнутость. Очень важным свойством класса. С, в значительной степени объясняющим его устойчивость, являются его замкнутость по отношению к самым разнообразным операциям над функциями (и теоретико-множественным операциям над их графиком). Отметим сначала свойства, композиционной замкнутости: замкнутость относительно суперпозиции, связывания аргументов константой или ограниченным квантором, перестановки и отождествления аргументов, итерации и разветвления (в смысле языков программирования). Для множеств аналогичная замкнутость имеет место относительно операций объединения, пересечения, прямого произведения и проектирования. Далее, вычислимые замыкания любых наборов вычислимых функций принадлежат классу С, в частности, замыкания относительно любого вычислимого оператора.

Для каждого вычислимого оператора R(Д можно определить его наименьшую неподвижную точку, которая также оказывается вычислимой функцией (первая теорема, о рекурсии). Наконец, класс С замкнут относительно диагонализации, т. е. для любой нумерации ДД вычислимьIX функций n аргументов функция ^*(x1 х_п) =^xi (x1 .x₂ х_п) вычислима.

Вычислимость универсальных функций также является выражением определенных свойств замкнутости класса С.

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

Программы. Значительное место в общей теории вычислимости занимает изучение программ вычислимых функций. Важно заметить, что все „языки программирования¹¹ создают избыточный запас изобразительных средств: каждая вычислимая функция имеет бесконечное множество задающих ее программ. Мало того, программы, задающие функции, настолько разнообразны, что для любой тотальной вычислимой функции f (х) можно найти такую точку ее графика (n, f(n)),что указанные числа n и f(n), трактуемые как программы, будут задавать одну и ту же вычислимую функцию (вторая теорема о рекурсии). Наряду с этим имеет место принципиальный и, на первый взгляд, парадоксальный факт: программа, задавая исчерпывающую информацию, позволяющую получать значения функции по заданным аргументам, в то же время не говорит ничего об общих свойствах функции: каково бы ни было нетривиальное свойство вычислимой функции (т. е. свойство, которым обладают не все функции из С), не существует алгоритма, который по программе обнаруживал бы, обладает ли функция, вычислимая по этой программе, указанным свойством. В частности, по программе нельзя определить, задает ли она тотальную функцию; для двух программ нельзя определить, задают ли они одну и ту же функцию, и т. и.

Нормальные формы. Естественной реакцией на такую неинформативность общего понятия программы является выделение классов вычислимых функций и различных „нормальных форм“ для программ. Классы функций обычно выделяются с помощью тех или иных структурных ограничений на задающие их программы, однако впоследствии эта классификация иногда подтверждается установлением внутренних свойств класса, например, по скорости роста и т. и.

В первом приближении рассматриваются следующие классы: класс С (синоним — частично рекурсивные функции), тотальные вычислимые функции (синоним — общерекурсивные функции), примитивно рекурсивные функции, различные субрекурсивные классы, прямо вычислимые функции. Среди субрекурсивных классов выделяются такие, которые, будучи как можно более узкими, сохраняют способность порождать любое перечислимое множество.

Первым источником нормальных форм является программа универсальной функции, которая фиксирует в своей структуре тот запас действий и минимум организации вычислений, которые обеспечивают выполнение любой программы. Рисунок нормальной формы сильно зависит от конкретного способа программирования, однако для многих из них характерно разделение „комбинаторной“ и „поисковой“ стадий выполнения алгоритма с возможной концентрацией последней в одной части программы. Слова поисковый и комбинаторный — это типичные примеры математических эпитетов, которые никогда не определяются, используясь главным образом в предисловиях и в комментариях, но в которых зачастую сидит вся суть математического рассуждения. Мы понимаем под комбинаторной стадией манипуляции, связанные с элементами конечного множества, причем объем этих манипуляций имеет достоверную верхнюю оценку, известную до начала стадии. Поисковая стадия связана с обозреванием элементов бесконечного множества, причем без гарантии того, что нужный нам элемент у принадлежит множеству, и без оценки числа шагов, которые надо сделать, прежде чем добраться до цели.

В геделевых изображениях вычислимых функций существует целая иерархия нормальных форм в виде общерекурсивных предикатов, предваренных разными комбинациями кванторов (иерархия Клини). В частично рекурсивных функциях существует нормальная форма с единственным вхождением оператора поиска. Для рекурсивных программ аналогом является нормальная форма с одним рекурсивным уравнением, а для операторных алгоритмов — с одним оператором цикла. Диофантовы множества сами по себе образуют нормальную форму, в которой комбинаторным шагом является вычисление полинома, а поиск заключается в переборе параметров и неизвестных.

Программные процессоры. Существенное место в классе вычислимых функций занимают некоторые конкретные функции, смысл которых состоит в том, что они работают, с программами, т. е. с номерами вычислимых функций. Программистам естественно называть такие функции программными процессорами. Самым первым из них следует назвать универсальную функцию — интерпретатор языка программирования, запрограммированный в нем самом. Не менее фундаментальную роль играет так называемая s- m-n-функция, или смешанный вычислитель s_n^m(p^m+n, х 1,.. _тх_т\ который по программе р, задающей функцию n+m переменных ^( х 1,... ,ж_п, n_{+ +1},... ,х _n+_m), и по заданным аргументам х 1,... ,х_п вычисляет (генерирует) программу px, ..., х_п задающую функцию ф( n₊₊i Пп^т) ==^(-О Пп- п+11 -O^m)- Важную роль играют „трансляторы" — функции, переводящие образы функций из одной нумерации в другую. К ним примыкают перестановки — тотальные функции, переводящие взаимно однозначно N в N. С их помощью выделяются инвариантные свойства функций и множеств, т. е. такие, которые сохраняются при всевозможных перестановках координатных множеств. Ни одна развитая теория вычислимости не обходится без библиотеки стандартных процедур, связывающих функции и множества: тотальные функции, перечисляющие график вычислимой функции, частичные функции, представляющие перечислимое множество своей областью определения, и т. и. Общим для всех этих служебных функций является стремление представить их в некоторой стандартной форме или отнести их к как можно более простому классу. Для тотальных функций стандартным является класс примитивно рекурсивных функций, а также всюду, где возможно, — субрекурсивные классы. Для нумераций нужно уметь сворачивать взаимно однозначно последовательности чисел в одно число; базовой конструкцией является функция пересчета пар, фактически представляющая собой семейство трех функций z=x^^i х=а\^ и у = a₂(z), удовлетворяющих следующим тождествам

Vz = x(Mz),^2(z));

Сложность. В последние годы с общей теорией вычислимости начинает смыкаться теория сложности вычисления функций. В ее основе лежат абстракции разных форм физической реализации вычислений во времени и в пространстве, а также оценки объема той информации, которую надо задать в программе. Теория сложности рассматривает обычно только тотальные функции и является принципиально релятивизированной теорией, исчисляя сложность вычислений по отношению к фиксированному набору элементарных средств обработки и хранения информации (функциональный базис). Исходным понятием в теории сложности является понятие протокола или истории вычислений, или просто вычисления: организованная совокупность элементарных шагов, реализующих функциональную зависимость, т. е. приводящая от х 1, ..., пп к ^(ж1, ..., пп\ Организованность выглядит как (частичный) порядок на элементарных шагах, отражающий логические и информационные связи между ними. Этот порядок отчасти индуцируется программой, отчасти — универсальным алгоритмом исполнения.

На протоколах задается некоторая мера, отражающая затраты времени и пространства на вычисления, выполняемые согласно данному протоколу. Затем вводится некоторый способ ”Интегрированпя“ мер сложности отдельных вычислений, позволяющий сопоставить некоторую сложность данной программе. Навешивание кванторов на сложности множества функционально эквивалентных программ дает оценки сложности решения задачи в данной вычислительной модели. Квантор всеобщности дает нижнюю оценку (какова ни была бы программа, она будет не проще чем...); квантор существования дает верхнюю оценку (существует программа со сложностью не более...). Поскольку затраты ресурсов существенно зависят от объема входной информации, сложность обычно указывается как некоторая функция параметра, характеризующего объем.

Вклад разных моделей в общую теорию.

Формирование общей теории вычислимости и ее применение обогатили математику серией принципиальных достижений. Некоторые модели вычислений играют важную роль в информатике и программировании. Ряд понятий и утверждений теории вычислимости имеют глубокую методологическую и философскую Интерпретацию. Не претендуя ни на полноту, ни на глубину анализа, охарактеризуем вклад разных моделей вычислимости в общую теорию и ее приложения.

Классические модели. Изобразимость некоторых конкретных вычислимых функций, охватываемых классом примитивно рекурсивных функций, в логическом исчислении формальной арифметики позволила Геделю (Гедель, 1931) установить свой знаменитый результат о неполноте формальных теорий. Очень важную роль для Теории вычислимости и математики вообще сыграла концепция геделевой нумерации, т. е. отображения конструкций формального языка в предметную область, в данном случае — в N. Выделенный при этом класс примитивно рекурсивных функций на долгие годы стал основной ”системой программирования “ разных служебных функций теории вычислимости и был подвергнут детальному изучению — в частности, расчленен на иерархию субрекурсивных классов, задаваемую рисунком формального представления и градуируемую шкалой оценок скорости роста (Гжегорчик, 1953).

Понятие рекурсивной функции по Эрбрану позволило нащупать объем класса тотальных вычислимых (общерекурсивных) функций, распространить на них понятие изобразимости (Мостовский, 1947), установить первую эквивалентность с независимым определением вычислимости (А-определимостью) (Клини, 1936а), дать первые формулировки теорем о нормальной форме (Клини, 1936) и о нумерации (Клини, 1943). Уже в последние годы в виде так называемых базовых трансформаций (rewritingrules) этот подход к определению вычислимости вошел в программирование под названием трансформационного подхода (см., например, Дарлингтон, 1978).

Теория А-определимости менее распространена, нежели другие модели вычислимости, если не считать А-нотации Черча, ставшей одним из фундаментальных обозначений в математике. В то же время эта модель сыграла большую роль в становлении теории вычислимости. Будучи весьма абстрактной моделью, А-исчисление интуитивно выделило в качестве исходных понятий следующие наиболее важные универсальные конструкции класса вычислимых функций: отображение функций в предметную область (способность одного и того же терма употребляться и в роли функции, и в роли аргумента), нахождение значения функции от заданного аргумента с помощью универсальной операции (операция (tn)

применения t к п), s-m-n-функцию (способ вычисления функции нескольких аргументов путем поочередного применения). Необходимость экспликации этих понятий в конкретных вычислительных моделях была, возможно, толчком к нахождению соответствующих конструкций в теории рекурсивных функций. Аналогично, теорема о неподвижной точке в A-исчислении привела к нахождению теорем о рекурсии.

Изучение свойства A-исчисления позволило впервые доказать алгоритмическую неразрешимость конкретной проблемы, состоящей в следующем. Терм в A-исчислении называется вызовом функции, если он имеет вид (Ax.f)t. Терм является нормальной формой, если он не содержит вызовов функции. Терм t имеет нормальную форму и, если |—t^u. Например, терм (Ax.xx)y имеет нормальную форму уу, а терм (Ax.xx) (Ах.хх) нормальной формы не имеет (действительно, если редуцировать этот вызов, то он перейдет сам в себя). Проблема, неразрешимость которой была установлена Черчем (Черч, 1936), состоит в требовании определить для любого терма, имеет ли он нормальную форму.

Совпадение A-определимости с общерекурсивностью (Клини, 1936а) позволило Черчу сформулировать свой тезис о том, что общерекурсивные (и A-определимые) функции отвечают и полностью охватывают интуитивное понятие вычислимой функции.

Мы еще будем говорить о роли A-исчисления в абстрактной вычислимости, а пока заметим, что внимание к этой модели возросло в связи с развитием программирования. Язык Лисп (Маккарти, I960) почти буквально содержит в себе формализм A-исчисления; Лэндин (Лэндин, 1965) указал на связь конструкций языка Алгол 60 с A-исчислением; совсем же недавно Бэкус (Бэкус, 1978) выдвинул функциональное или аппликативное программирование как альтернативу сложившемуся стилю составления детерминированных императивных программ.

Машины Тьюринга оказались в высшей степени убедительной моделью, демонстрирующей механический характер вычислений, однозначно предписываемых программой и состоящих из элементарных шагов, каждый из которых обладает свойством непосредственной очевидности. В машинах Тьюринга работа с количествами полностью сводится к работе со знаками. Для машин Тьюринга был построен универсальный алгоритм, была доказана алгоритмическая неразрешимость проблемы остановки и введено понятие относительной вычислимости (Тьюринг, 1936). Характеризации A-определимых функций машинами Тьюринга и наоборот оказались весьма веским подтверждением тезиса Черча. В дальнейшем машины Тьюринга благодаря крайней элементарности своих шагов стали популярной моделью в работах по сложности алгоритмов (см., например, Трахтенброт, 1967). Введение различных ограничений на манипулирование с лентой привело к развитой классификации машин Тьюринга, получивших в области субрекурсивных функций название автоматов и образовавших свою развитую теорию.

Понятие частично рекурсивной функции позволило осознать свойства замкнутости класса вычислимых функций, в частности, по отношению к диагонализации, получить в окончательной форме теорему об универсальной функции (Клини, 1943), s-m-n-теорему, первую (Клини, 1952, § 66) и вторую (Клини, 1938) теоремы о рекурсии, установить в общей форме нераспознаваемость нетривиальных свойств вычислимых функций но программам (Райс, 1953), полностью разработать понятие относительной вычислимости и ввести на его основе вычислимые функционалы и операторы (Клини, 1952, ч. III).

Программистские модели. Операторные алгоритмы и рекурсивные программы возникли в теоретическом программировании и до сих пор являются моделью вычислений, периферийной для общей теории вычислимости. Их роль возрастет, когда мы продолжим их обсуждение в разделе абстрактной вычислимости. Однако уже сейчас можно заметить, что наличие механизма произвольного доступа к памяти (по адресу или индексу) сделало некоторый подкласс операторных алгоритмов одной из основных вычислительных моделей в теории сложности (Ахо и др., 1976). Выделение в качестве отдельной конструкции графа переходов позволило классифицировать программы по структуре графа переходов (бесцикловые, структурированные программы), в частности, обнаружить, что уже весьма регулярной и простой структуры достаточно, чтобы запрограммировать любую функцию (Петер, 1958; Бем, Якопини, 1966), а также подтвердить иерархию субрекурсивных функций (Констебль, Бородин, 1972). Аналогом теоремы о нормальной форме для рекурсивных функций здесь служит теорема о нормальной форме с единственным оператором цикла (Харел, 1980). Поскольку правила программирования операторных алгоритмов заданы относительно базиса элементарных предикатов и операций, они позволяют изучать критерии алгоритмической полноты базиса, т. е. возможности задать операторными алгоритмами любую вычислимую функцию (Непомнящий, 1972).

Рекурсивные программы позволили охарактеризовать класс вычислимых функций как неподвижные точки уравнений, в которых допускаются прямые вычисления и простейшие определения разбором случаев. Это сочетание конкретной программной конструкции со столь абстрактным определением результата вычислений оказалось очень удобным методологическим средством для описания смысла программ, т. е. для описания вычисляемой программой функции некоторыми средствами, отличными от универсального алгоритма. Соответствующая техника под названием денотационной семантики получила распространение в теоретическом программировании (Манна, 1974).

Операторные алгоритмы и рекурсивные программы стали в последние годы доминирующими моделями в теории доказательства свойств программ. Как известно, изобразимость вычислимой функции ф в логическом языке формальной арифметики позволяет средствами логического вывода доказывать принадлежность отдельных точек графику функции ^, но не дает никакого подхода к доказательству общих свойств произвольной вычислимой функции. По программе примитивно рекурсивной функции в ее определении по Геделю можно извлечь доказательство теоремы существования (Клини, 1952, § 49), но этого уже нельзя сделать для общерекурсивной функции, поскольку ее программа неотличима от программ частично рекурсивных функций, для, которых справедлива уже упомянутая теорема Райса о нераспознаваемости нетривиальных функциональных свойств.

Теория доказательств свойств программ под воздействием практических потребностей стремится разными методами преодолевать этот барьер неразрешимости. Один из методов — работа с так называемыми аннотированными программами. Суть его состоит во введении своеобразного программно-логического исчисления, основанного на языке, объединяющем формулы исчисления предикатов и программные конструкции. Аннотация — это логическая формула (утверждение), отнесенная некоторой точке программы. Аксиомы программно-логического исчисления позволяют провести индуктивное рассуждение, управляемое структурой программы. Это рассуждение, отправляясь от аннотаций, как от посылок, выводит некоторое общее утверждение о программе, например, тотальность вычисляемой ею функции или ее равенство другой, независимо определенной функции (задача о правильности программы). Успех дела состоит в искусстве выбора аннотаций. Это, естественно, творческая задача, но ее решению часто способствует то или иное априорное знание о программируемой задаче. Используемые при этом смешанные программно- логические исчисления образуют то, что называется логической семантикой языка программирования (Флойд, 1967; Хоар, 1967; Берсталл, 1969).

Ситуация выглядит по-иному при взгляде на связь между логикой и программированием с другой стороны. В ряде случаев априорная информация о задаче, выраженная в некотором языке спецификаций, дает возможность получить из этой спецификации программу вычислений путем систематического синтеза программы. В основе этой возможности лежит фундаментальный факт извлекаемости рекурсивного описания вычислимой функции по доказательству теоремы существования в конструктивной логике (Клини, 1945; 1952, § 82). Построение аналогичных синтезаторов для других вычислительных моделей с дополнительными требованиями, удовлетворяющими разным критериям эффективности, составляет один из центральных разделов теоретического программирования.

Недавно выяснилось, что программные процессоры типа s-m-n-функции, или смешанного вычислителя, играют фундаментальную роль в трансляции и других прикладных вопросах программирования (Ершов, 1977). Это привело к задаче строгого описания этих программных процессоров в моделях операторных алгоритмов и рекурсивных программ (Ершов, 1978, 1980).

Диофантовы множества. Характеризация перечислимых множеств и вычислимых функций диофантовыми множествами была найдена совсем недавно (Матиясевич, 1970). Изложение соответствующей теории еще в значительной мере отражает путь ее становления (Матиясевич, 1972). Движущей силой в развитии вопроса был вызов Гильберта, сформулировавшего в качестве своей десятой проблемы следующую: найти алгоритм, позволяющий для полиномиальных уравнений с целыми коэффициентами (диофантовых уравнений) определить их разрешимость в целых числах. Огромные и безуспешные усилия, затраченные на попытки позитивного решения этой проблемы, в сочетании с накапливающимися к этому времени примерами алгоритмической неразрешимости приучали к мысли видеть в десятой проблеме Гильберта просто еще один пример неразрешимой массовой проблемы, однако гипотеза Дейвиса (Дейвис, 1953) о том, что эта проблема может быть неразрешима из-за гораздо более фундаментальной причины, а именно — из-за диофантовости перечислимых множеств, сразу придала этой проблеме дополнительную глубину.

Не отвлекаясь на историю окончательного установления диофантовости перечислимых множеств, заметим лишь, что построение теории вычислимости в рамках этой модели еще продолжается (Дейвис и др., 1976) . Найден универсальный многочлен, т. е. обладающий параметром, варьирование которого позволяет получать любые перечисленные множества фиксированной размерности. Степень и число переменных полинома оказались удобными параметрами, характеризующими сложность представления его диофантова множества. С привязкой к этим параметрам был установлен ряд теорем редукции (например, что достаточно рассматривать диофантовы уравнения не более чем четвертой степени), а также получены оценки сложности конкретных множеств. Пожалуй, наиболее загадочной теоремой о нормальной форме является представление любого перечислимого множества из N в виде положительных значений некоторого полинома. Это значит, что полиномы обладают определенной универсальной способностью кодирования информации. Эксплуатация этих способностей доступна пока что лишь нескольким экспертам, и они время от времени поражают воображение остальных математиков магическими формулами многочленов, вычисляющих, например, все простые числа, или — как этот простенький полином, найденный Джоунзом (цит. по Манину, 1980, гл. 2, §8),

2a4b + a3b2 - 2a2b3 - a5 - ab4 + 2a,

— все числа Фибоначчи и только их.

Абстрактная вычислимость.

Преданализ. Знакомство с теорией вычислимости во всем разнообразии образующих их вычислительных моделей оставляет смешанное впечатление, даже если оставаться строго в рамках арифметических функций. Естественно, первое, к чему нас приучают, — это ”Железная“ круговая порука взаимной сводимости. Далее мы можем усмотреть контуры — но не более — инвариантной теории, утверждения которой можно выразить в любой вычислительной модели и доказать в любом языке программирования. Для того чтобы воплотить контуры в реальность, мы имеем, грубо говоря, следующие альтернативы: (1) провести все построения в данной модели, используя понятия и стиль рассуждений и конструкций, характерный для ее языка программирования, или (2) ,,украсть“ результат из другой теории, применив дважды трансляцию из одной модели в другую. Можно также предаться оппортунизму и заниматься то заимствованиями, то собственными построениями в зависимости от того, что ,,удобнее“.

В каком-то смысле никакой из этих способов не хорош. Первый подход превращает науку в монологи глухих, оставляя каждого исследователя наедине со спецификой выбранной модели и ее языка программирования, как правило, весьма неудобного и искусственного. Второй подход заведомо сужает взгляд на теорию вычислимости, ставит в особое положение какую-то одну специфическую версию этой теории, подрывает интерес к поискам независимых характеризаций вычислимых функций и перечислимых множеств1. Третий подход, обеспечивая сосуществование и взаимную дополнительность разных моделей, представляется самым просвещенным, но он уводит от ответа на простой вопрос: почему? Почему все вычислительные модели создают один и тот же класс вычислимых функций? С одной стороны, понятие вычислимости демонстрирует непоколебимую устойчивость, нося, по мнению многих математиков, абсолютный характер (см., например, Роджерс, 1967, § 1.6), а, с другой стороны, сущность вычислимости ускользает от нас под покровом столь непохожих друг на друга одежд конкретных вычислительных моделей и их языков программирования.

Естественно, автор — далеко не первый, кто ставит этот вопрос, и нам предстоит рассмотреть серию очень интересных работ, в той или иной мере пытающихся на этот вопрос ответить. Однако представляется полезным немного порассуждать заранее по поводу того, как можно подходить к ответу на вопрос о сущности вычислимости, какой парадигмой при этом пользоваться. Здесь нам придется преодолевать традиционный замкнутый круг развития теории: говорить наперед о том, чего еще не знаем; мы разомкнем этот круг, развернув его в три витка анализа: предобзорный, постобзорный и заключительный.

Сущность вычислимости — это нечто, находящееся в равном положении по отношению к любой конкретной вычислительной модели. Идеальной является некоторая абстрактная теория, по отношению к которой любая конкретная вычислительная модель является моделью в смысле, предлагаемом теорией доказательств. Выполнимость аксиом абстрактной теории проверяется в конкретном языке программирования данной модели. Уже на этом уровне возникает много вопросов: от каких свойств конкретных моделей следует абстрагироваться, какие объекты следует сделать параметрами абстрактной теории, какими свойствами их следует наделить аксиоматически.

Уже в начале размышлений по поводу этих вопросов возникает вопрос следующего уровня: можно ли в принципе построить абстрактную теорию вычислимости, оставаясь в пределах натурального ряда N и пространства арифметических функций А? Забегая несколько вперед, заметим, что это один из самых противоречивых вопросов теории вычислимости. Некоторые современные пифагорейцы считают, что все научное как раз и сконцентрировано в N, А, С, и нумерациями остальных теорий можно получить все утверждения, интересные для математики. Этому противопоставляется такой взгляд, что на практике вычисления встречаются в самых разных предметных областях и с самым разным запасом элементарных вычислительных средств и поэтому мы обязаны уметь развивать теорию вычислимости в любых областях.

Заметим, что вопрос о выходе за пределы N, А и С может иметь еще и чисто методологическое значение, поскольку сущности, лежащие в основе понятия вычислимости, слишком плотно упакованы или просто слиты в понятии натурального числа. Выход же на более абстрактные объекты позволит разделить и, стало быть, эксплицировать эти сущности.

Анализ сущностей — это в высшей степени тонкое дело, поэтому мы только наметим некоторые особенности натуральных чисел и их использования в теории вычислимости.

• 1.    Натуральное число является простейшим конструктивным объектом с одной константой 0 (нуль) и единственным конструктом ’ (счет).

• 2.    Для конструктивных объектов очень важной является связь между объектом как некоторой абстрактной индивидуальностью (,, количеством “ для числа) и его знаковым выражением или представлением. Для объекта хED и его представления aEW(W - пространство символических выражений) необходимы две функции х- D^W и 5: W^-D со свойствами х(^ж) =сх, 5(сх)=х, 11=22 ^сх1=сх₂. Для натуральных чисел связь между количеством и его представлением с помощью операции счета предельно симметрична и проста: п оО (заметим, что это одно из самых ,,коварных“ для анализа свойств натурального числа).

• 3.    Любое множество из N линейно упорядочено. Любое множество имеет минимальный элемент; любое конечное множество имеет максимальный элемент (это также очень сильное свойство, вырождающее многие алгоритмические операции над числами, особенно поиск).

• 4.    Основные арифметические операции сложения и умножения, используемые в теории вычислимости для функций кодирования, образуют на целых числах кольцо, обладающее богатым запасом тождеств. Эти тождества иногда используются случайным образом, иногда в комбинаторной (знаковой) части вычислений, иногда во время работы с количествами, затемняя тем самым логическую структуру вычислительного процесса.

При выходе за пределы N, А и С возникает еще одна альтернатива: говоря о вычислимости в произвольных областях можно ли позволить себе опираться на теорию вычислимости в N? Для пифагорейцев этот вопрос не возникает, поскольку они выражают произвольную вычислимость в терминах арифметической вычислимости. Автору, однако, представляется, что абстрактная теория вычислимости должна строиться без явных или косвенных ссылок на концепции арифметической вычислимости.

Рассуждая об абстрактном определении класса вычислимых функций над произвольными областями, с самого начала можно выделить два альтернативных подхода. Их можно называть вычислимостью в большом и вычислимостью в малом. Первый подход, рассматривая абстрактные функциональные пространства, выделяет класс вычислимых функций (над неуказанными областями) в целом, постулируя свойства замкнутости и существование определенных универсальных функций. Истоки этого подхода можно усмотреть в абстрактных системах Черча (Черч, 1941) и Карри, (Карри, 1930). Второй подход более конструктивен: постулируя некоторые свойства предметной области D, он связывает с ней набор (базис) „элементарных¹¹ операций, т. е. предикатов П == {п1, ... ,nm) и функций Ф == {^1,... ,^n), превращая тем самым D в алгебраическую систему h И^П, Ф). Константы достаточно рассматривать как нульместные операции. Если необходимо, операции также наделяются некоторыми свойствами. Класс вычислимых функций, грубо говоря, задается с помощью некоторой системы программирования в репертуаре команд П, Ф. Сразу заметим, что в такой подход вкладываются без особых трудностей все вычислительные модели арифметической вычислимости с базовой алгебраической системой hN,=,O,0).

В заключение заметим, что следует различать понятие абстрактной и обобщенной вычислимости. Не вдаваясь в детали, мы проводим водораздел между ними в зависимости от тех или иных абстракций бесконечного. В нашем понимании абстрактная вычислимость, рассматривая функции в произвольных областях и базисах, остается в пределах абстракции потенциальной бесконечности и строгого понимания конечного. Мы приходим к обобщенной вычислимости, если допускаем ординалы и теории высших порядков. Вопросы обобщенной вычислимости в нашем обзоре не рассматриваются, хотя требования обобщений такого рода во многих работах сильно влияли на способы построения абстрактной теории. Более широкий и богатый идеями анализ обобщенной и абстрактной вычислимости был проделан Крайзелом (Крайзел, 1969). Автор позволил себе использовать в обзорной части некоторые выдержки из другой своей работы, посвященной этому же вопросу (Ершов, 1981).

Абстрактная вычислимость в большом.

Униформно вычислительные структуры по Вагнеру. В работах (Вагнер, 1963, 1969) автор рассматривает в качестве исходной предметной области абстрактное множество U. Он постулирует существование геделизации, т. е. однозначного отображения G: U^lU. образ которого задает искоторый запас унарных функций типа [7^[/. Обозначая G(u) = [и], Вагнер определяет n-местные функции по схеме Шенфинкеля (Шенфинкель, 1922):

II [ «] 1 = [«]

и определяет для заданной пары 1=hU^G') функциональное пространство F(I) ={[? z]np«GO.п> 1}.

Пара h^G^ называется униформно рефлексивной структурой (УРС), если в U можно указать три разных элемента * (индекс неопреде ленной функции), а (функция смешивания — один из комбинаторов Карри (Карри, 1930), также восходящий к Шенфинкелю (Шенфинкель, 1922) и ф (хорошо известная программистам конструкция если-то-иначе), удовлетворяющие следующим аксиомам:

• 1.    [_м](*)=*=[*](«,):

• 2-    [ ^аШ, =**, [Ы (/, 9)] (ж) = [/](t[q](t));

  a, x = c, b, x c.

  
  

• 3.    [[^] (с. Ь. о)] (ж) =

Вагнер показывает, что из этих аксиом вытекает существование многих „стандартных" вычислимых функций (константы, тождественные функции, функции выбора аргумента), наличие мощных теорем замыкания и другие свойства, обычно адресуемые вычислимым функциям и их классам. Показывается далее, что в N существуют рекурсивные конструкции, которые обеспечивают на нем выполнение аксиом УРС. Возникающий на этой структуре класс функций в точности совпадает с частично рекурсивными функциями. Вагнер далее показывает, что в произвольной УРС можно естественным образом задать 1-1-образ натурального ряда (сплинтер). Если потребовать, чтобы сплинтер как подмножество в U имел бы в F(I) всюду определенную характеристическую функцию, то тогда F(iy рассматриваемое на сплинтере, совпадает с С в некотором естественном изоморфизме.

Базисные теории рекурсивных функций. Униформно рефлексивные структуры 1=hU, i) постулируют наличие некоторой геделизации G. Все свойства класса F(I) доказываются (хотя и равномерно) относительно уже заданной G. Стронг (Стронг, 1968) и Фридман (Фридман, 1969), рассматривая пространство функций F = {/}/: Dⁿ^D (п>0) отдельно от предметной области D, выписывают дополнительные аксиомы, которым должно удовлетворять F, чтобы на D можно было бы задать некоторую УРС, образующую то, что эти авторы называют базисной теорией рекурсивных функций (BRFT).

Аксиоматика Стронга:

• (1)    F содержит константные функции для любого элемента из D и функции выбора аргумента от любого числа аргументов;

• (2)    F содержит характеристическую функцию проверки равенства константе;

• (3)    F замкнуто относительно подстановки;

• (4)    Для каждого т >0 в F имеется универсальная функция для функций из F от т

аргументов;

• (5)    для каждых т^ >0 в F имеется s-m-n-функция (универсальная функция для смешанных вычислений).

Аксиоматика Фридмана:

• (1)    D имеет не менее двух элементов;

• (2)    F содержит не более чем двуместные функции над Р;

• (3)    F замкнуто относительно подстановки;

• (4)    F содержит тождественную функцию и функции пересчета пар;

• (5)    F содержит все одноместные функции-константы;

• (6)    F содержит характеристическую функцию равенства;

• (7)    F содержит универсальную функцию для одноместных функций.

В последней аксиоматике отсутствует функция смешанного вычисления, а ее отсутствие компенсируется тонкими отличиями в других аксиомах. Фридман далее доказывает, что аксиомы BRFT обладают свойством категоричности (относительно фиксированной D\. любые две геделизации, удовлетворяющие аксиомам BRFT, создают изоморфные классы функций.

Итеративные комбинаторные пространства. Скордев (Скордев, 1976, 1980) рассматривает абстрактные функциональные пространства в виде частично упорядоченных полугрупп, т. е. содержащих тождественную функцию, замкнутых относительно композиции и с отношением частичного порядка: /6до-(график/) С(график у). Функциональное пространство F называется комбинаторным итеративным пространством, если оно:

• 1)    содержит константные функции, образующие множество С, содержащее два выделенных элемента (истина и ложь);

• 2)    на F задана операция пересчета пар, при этом функции взятия элементов пары принадлежат F;

• 3)    С замкнуто относительно пересчета пар;

• 4)    на F задана операция если-то-иначе;

• 5)    на F задана операция взятия неподвижной точки уравнения ^ — если х то / иначе ^^, где I — тождественная функция (итерация).

Если Ф — конечный набор элементов из F, то любой элемент из F, который получается из Фи (тождественная функция, взятие элементов пары, истина, ложь) с помощью применения конечного числа операций, заданных на F, называется функцией, рекурсивной в Ф. Для этих функций можно построить теорию рекурсии, включающую аналоги теорем о нормальной форме, первой и второй теоремам о рекурсии и теореме о нумерации.

Вычислительные теории. Московакис (Московакис, 19696Д предложил новый подход к аксиоматизации вычислимости, использующий понятие вычисления. Он требует, чтобы предметная область D была бы „вычислительной областью“, т. е. содержала бы в себе множество С программ функций (индексов), в свою очередь содержащее в себе образ N натурального ряда N, а на С был бы задан пересчет пар. Затем Московакис вводит центральное понятие вычисления как набора элементов из D вида (е, ж 1, ..., х_п, у). где с ЕС, а набор объявляет, что программа с вычисляет -у по ад..... х_п. Для некоторого множества 0 функцня /(ж1, ..., ж_п) называется 0-предвычислимой, если существует такое еЕС, что для любой точки ж1, ..., х_п, у графика / вычисление (е, ж1, ..., ху, у) принадлежит 0. Благодаря постулированному свойству рефлективности, тотальным функционалам и операторам можно сопоставить функции и, стало быть, перенести на них понятие 0-предвычислимости. Множество вычислений 0 называется предвычис-лительной теорией, если следующие функции, функционалы и операторы оказываются 0-предвычислимыми:

• 1)    константы, тождественная функция и функция ,,счета“ в N,

• 2)    характеристическая функция множеств С и N,

• 3)    функции пересчета пар на С,

• 4)    подстановка и примитивная рекурсия по N,

• ■5 ) универсальные функции вычисления, частичного вычисления (s-m-n-функция) и вычисления с перестановкой аргументов.

Для того чтобы охарактеризовать класс вычислимых функций, Московакис постулирует, что каждое вычисление обладает длиной, т. е. ординалом (конечным или бесконечным). При переходе от предвычислительной теории к вычислительной возникает различие между функциями и функционалами. Предвычислимая функция является вычислимой всегда, а предвычислимый функционал F объявляется вычислимым, только если длина вычисления F, грубо говоря, не меньше длины вычисления функций, индексы которых являются аргументами вычисления функционала. Кроме того, чтобы предвычислительная теория была вычислительной, требуется — по определению — чтобы длина вычисления по универсальной функции была бы, как скажут программисты, меньше длины частичного вычисления и последующего вычисления по остаточной программе, ср. (Ершов, 1980).

Московакис показал, что вычисления на машинах Тьюринга образуют вычислительную теорию, и установил справедливость первой теоремы о рекурсии для вычислительных теорий.

Фенстад, (Фенстад, 1974), рассматривая множество вычислений 0= { ест} }, г де ст — набор аргументов, вводит вместо длины вычисления транзитивное отношение „быть подвычислением “, т.е. (ест7/)<(е’ст’т/’) значит, что вычисление у из ст по программе е является частью вычисления у¹ из ст’ по программе е’. Множество вычислений с указанным отношением (0, <) называется вычислительной структурой, если для любого вычисления множество его подвычислений конечно. Вычислительная структура объявляется вычислительной теорией, если она удовлетворяет определениям Московакиса (Московакис, 19696), где вместо неравенств между длинами вычислений постулируются соответствующие отношения быть подвычислением .

Фенстад, (Фенстад, 1978) строит множество ,,рекурсивных“ функций в абстрактном функциональном пространстве в виде замыкания R _ш (Ф), где Ф — базовое (опорное) множество функций, как наименьшее множество функций, замкнутое относительно операторов композиции, взятия неподвижной точки, содержащее правило определения функции если-то-иначе и следующие ,, комбинаторы “ — термин, восходящий к Карри (Карри, 1930):7(/) =/ К У д) = / и Sy,g,h) =f(h)(g(h)\ Он показывает, что R.(Ф) представимо в виде вычислительной теории.

Вычислимость над алгебраическими системами. Ниже мы будем использовать одни и те же обозначения для абстрактных алгебраических систем А= (D,С,Ф, П, К), где R: ФиП^Х. Здесь R — тип алгбрапческой системы. Ф= {^1 ^m} (7/z>0) — функциональные символы, П= {п1,... ,nn} (п>0) — предикатные символы, образующие в совокупности сигнатуру системы Л; D - носитель (предметная область), С - константы носителя. При этом С и/или Ф могут отсутствовать. Систему без Ф будем иногда называть реляционной системой, оставляя слово модель для теоретико-модельного употребления. Обозначение типа, т. е. R, будем для краткости, как правило, опускать. Суперпозиции операций из Ф с аргументами-константами и переменными будут называться функциональными термами. Предикатный символ с функциональными термами в качестве аргументов называется предикатным термом. В некоторых случаях отдельным операциям и предикатам будет придан конкретный смысл, например, тождественная функция или предикат равенства. Саму систему мы будем иногда называть базовой для создаваемого ею класса функций. Поскольку большинство определений абстрактной вычислимости имеют прототипы, среди арифметических функций, группировка разных определений будет аналогичной.

Нумерационная вычислимость. Идея определять абстрактную вычислимость, опираясь непосредственно на арифметические вычислимые функции, принадлежит Мальцеву (Мальцев, 1961). Рассматривая произвольную алгебраическую систему (D ,Ф, П), Мальцев постулирует существование для D нумерации а, т. е. отображения a: N^D, которое позволяет связать произвольную функцию/: Dr^D с некоторой арифметической F: Nr ^N с помощью соотношения

f(αx1, . . . , αxr) = αF (x1, . . . , xr).

Наличие нумерации позволяет переносить на функции / свойства вычислимости их прообразов F. Эту идею развил Лакомб (Лакомб, 1969), рассматривая абстрактную вычислимость в реляционных системах с равенством (D,П, =), где D - нумерованный носитель. Предикат Р(х 1, ..., хг) абстрактно вычислим в П, если он рекурсивен для любой нумерации D. Для целей нашего анализа важно подчеркнуть, что Лакомб получил чисто символическую характеризацию вычислимого предиката Р(х 1, ..., хг) посредством примитивно рекурсивного множества булевых формул в алфавите Пи{Р, =, предметные переменные х 1, ..., хТ1 конечный набор предметных констант}. Корректность определения абстрактной вычислимости по Лакомбу подтверждается тем, что в hN, 0, =, ’i его вычислимость совпадает с обычной относительной вычислимостью.

Инвариантная определимость является обобщением изобразимости в формальной арифметике. Ее применение к определению абстрактной рекурсивности было предложено Крайзелом, (Крайзел, 1963). Более конкретные определения были даны Фрассе (Фрассе, 1959). Рассматривается (для простоты) реляционная система hD ,П). В язык исчисления предикатов вводятся в качестве предикатных символов n_1v . . ,nn, символ определяемого предиката Р, а также индивидуальные константы сх для каждого элемента хED. Пусть Ф(Р) — формула исчисления предикатов и пусть С^ф (ДП) — класс всех моделей формулы Ф, получаемых всевозможными расширениями базовой системы с сохранением носителя. Тогда предикат Р^х 1, ..., х_п\ который сохраняет свои значения на каждом расширении из С_Ф(О, П), есть предикат, инвариантно определимый посредством Ф(Р). Поскольку в реляционной системе hN, П, =i инвариантная определимость совпадает с относительной вычислимостью, естественно считать ее определением вычислимости в hD, П^

Полнота исчисления предикатов позволяет дать инвариантной определимости следующую эквивалентную и чисто символическую форму. С каждым г-местным предикатным символом п связывается счетное множество формул А (п) вида п(сж1, ..., С.Z’r)lLЛИ п(('.Щ.....слу) в зависимости ОТ ИСТIIIIIIOCTII пли ложности п(яд.....лу). Пусть А(П) =А(п1)U... UA(п_п). Это множество называется диаграммой алгебраической системы hD ,П). Тогда для любого вычислимого в hD ,П) предиката Р(ж1, ..., лд) справедливо

Р(х 1..... х_т )^А(П) и{Ф(Р) }|-Р( слу.....сл_т

и

Р(х 1.....лу )оА(П) и{Ф(Р) }|-Р( сад.....слу).

Простая и поисковая вычислимости. Московакис (Московакис, 1969) приходит к абстрактной вычислимости в произвольном множестве D путем обобщения определения частично рекурсивных функций по Клини. Расширяя D выделенным элементом 0, он постулирует существование функции пересчета пар z= (х, у), отображающей D*xD*^D*^D* — замыкание DU{0} относительно (ж, у)), а также функций разбора пары. Предполагается далее существование предикатов равенства элементу 0 и принадлежности элемента из D* множеству D. После этого в D* выделяется образ N натурального ряда (сплинтер) 0, 1, 2,...в виде объектов 0, (0, 0), ((0, 0), 0) и т.д. с образом функции счета в виде (п+1)~(п, 0). С использованием этого сплинтера Московакис описывает класс „примитивно рекурсивных“ функций со значениями и аргументами из D* относительно некоторого списка Ф={р1, . р тр_т } произвольных функций над D*. Характерной особенностью построения является то, что Ф может содержать многозначные функции и что построение класса функций сопровождается построением их программ-индексов — последовательностей натуральных чисел, сохраняющих информацию о строении функции и упакованных с помощью пересчета пар в объекты из N. Показывается, что так определенные „примитивно рекурсивные “ функции относительно пустого Ф моделируют арифметические примитивно рекурсивные функции.

Московакис приходит к „частично рекурсивным“ функциям, постулируя вычислимость универсальной функции над D*. При этом, однако, эта функция оказывается определенной лишь в том случае, если первый аргумент этой функции оказывается индексом, построенным в соответствии с заданными индуктивными правилами. Необходимость ”синтаксического анализа“ индекса требует допущения операций поиска (аналогичных поиску в ^-операторе для арифметических функций) во множестве, которое может быть как упорядоченным, так и нет. В первом случае получается класс PC или так называемая простая вычислимость, а во втором случае — класс SC или поисковая вычислимость.

Для так определенных классов вычислимых функций Московакис строит элементарную теорию, включающую теоремы о нормальной форме, теоремы о рекурсии, теоремы о замкнутости и т. и.

Скордев (Скордев, 1980) находит алгебраизированную характеризацию простой и поисковой вычислимостей для случая бинарных отношений в D*xD* (т. е. многозначных функций одного аргумента), которая более четко устанавливает связь с частично рекурсивными функциями, представленными в виде алгебры Робинсона. Пусть F — множество всех бинарных отношений в D*xD*. Для любых двух бинарных отношений у и v определяются три базовых операции: обычная композиция, сочетание {(р, s): 3q3r((p, q) Е^к (щг) ЕДР(д r)=s} ii итерация (грубо говоря, композиция у с самим собой, пока Д рассматриваемая как функция, не окажется равной нулю на очередном звене возникающей цепочки значений). Пусть, далее, даны произвольные бинарные отношения ^1,..., ^_т и три базовых отношения L = ”р есть первый элемент пары q“, R = ”р есть второй элемент пары q“ ii „максимальное" отиошсиис U = D*xD*. Тогда, 'замыкание ^1 ^_т. L ii R тремя указанными операциями дает F ПРС, а то же замыкание ^1,... ,q?_m,L, R и U дает F П

Тьюринговы вычисления в произвольной области. Фридман (Фридман, 1969а) описал модель вычислений Т, которая обобщает понятие машины Тьюринга на произвольную алгебраическую систему (D, Ф,Ф, П). Обобщение носит весьма прямолинейный характер: на одну клетку ленты помещается один элемент из D или вспомогательный символ. Все функции, вычисляемые Т-машинами, называются T-рекурсивными. Фридман вводит важную характеризацию Т-рекурсивных функций с помощью модели Д так называемых эффективных определений, которая обобщает определение функции разбором случаев на бесконечное, но перечислимое (в смысле арифметической перечислимости, подразумевающей некоторую нумерацию) множество случаев. Отдельным случаем у Фридмана является „клауза" вида p^t, где р — либо пусто, либо — непротиворечивая конъюнкция предикатных термов или их отрицаний, a t — функциональный терм. Отсутствие р означает тождественную истину. Роль эффективного определения играет перечислимое множество клауз, такое, что конъюнкция условий двух разных клауз всегда, противоречива. Таким образом одна клауза „отвечает" за одну точку графика функции: для того чтобы вычислить Дж1, ..., п_п\ перечисляем клаузы, пока не найдем такую p^t, что р(ж1, ..., хn). Тогда Дж1, ..., х_п)= Дад, ..., п_п\ Фридман показывает, что каждое вычисление в Т-модели создает протокол, совокупность которых образует эффективное определение. Обратное доказательство Д^Т апеллирует к тезису Черча (в применении к модели Т) и к перечислимости эффективного определения.

Фридман изучает, каким дополнительный свойствам должны удовлетворять Т-рекурсивные функции для выполнения основных теорем элементарной общей теории вычислимости. Этих свойств оказывается три:

• (1)    Т-рекурсивность предиката равенства,

• (2)    Т-рекурсивность пересчета пар,

• (3)    конечная порождаемость D с помощью Т-рекурсивных тотальных функций.

Операторные алгоритмы и рекурсивные программы. Эти модели с самого начала были введены для определения вычислимости в любой алгебраической системе (Ершов, 1960; Маккарти, 1961). В операторных алгоритмах класс вычислимых функций над алгебраической системой hD, С,Ф, П) — это все функции, программируемые в „системе команд “ (Ф, П). В рекурсивных программах класс вычислимых функций — это наименьшие неподвижные точки рекурсивных программ, строящихся из условных термов в сигнатуре базовой системы. В операторных алгоритмах рассматриваются классы программ, включающих некоторые действия в натуральном ряду. Наиболее частые варианты — это схемы со счетчиками, т. е. с операциями ж+1, ж—1 и предикатом ж=0. Счетчики используются либо для кодирования, либо в программах с массивами — односторонними лентами с прямым доступом в любую клетку по ее номеру.

Общая теория вычислимости в этих моделях практически не развивалась, однако в интересах теоретического программирования в этих моделях внимательно изучались инвариантные, или абстрактные, свойства программ, т. е. такие, которые выполняются в любой алгебраической системе с данной сигнатурой. Такие свойства естественно приписывать не функциям, вычисляемым программам, а самим программам, или, более точно, их схемам, т. е. синтаксическим конструкциям, выражающим программы в соответствующем языке программирования.

Для определенности остановимся на схемах операторных алгоритмов. Эти схемы впервые рассмотрены Криницким (Криницкий, 1959, 1970) и получили впоследствии в литературе название стандартных схем или граф-схем с памятью. Распространим их конструкцию на случай произвольных систем hD, С, Ф, П). Роль логических условий играют произвольные предикатные термы и их булевы композиции; операторы присваивания имеют вид у:= t, где t — функциональные термы с операциями из Ф. Важнейшим отношением для схем программ является отношение функциональной эквивалентности: две схемы S 1и б^в сигиатуре Ф, П функционально эквивалентны, если они вычисляют одну и ту же функцию для любой алгебраической системы с данной сигнатурой. Для некоторых сигнатур и классов схем это отношение оказывается разрешимым. Янов (Янов, 1957) и Ратледж (Ратледж, 1964) установили это для сигнатур с унарными операциями и схем, использующих только одну переменную и предикатные термы без функциональных символов. В случае произвольных сигнатур это отношение разрешимо только для схем без циклов или непосредственно к ним сводящихся (Криницкий, 1959; Игараши, 1968). В общем же случае отношение функциональной эквивалентности оказалось неразрешимым (Патерсон, 1968; Летичевский, 1969).

Помимо этого, изучение схем программ позволило сделать одно весьма интересное наблюдение. Придадим в схеме программы предикатным символам произвольные истинностные значения. В этом случае из текста программы непосредственно извлекается конкретная вычислительная последовательность, протокол, или прокрутка, как говорят программисты. При этом с непосредственной очевидностью обнаруживаются три альтернативных возможности: либо этот протокол значим, т. е. по нему в некоторой конкретной алгебраической системе может быть проведено вычисление, либо он логически противоречив, либо он бесконечен. Такие протоколы можно с той или иной степенью детальности свернуть в один или несколько термов в сигнатуре (Ф, П), используя употребленные в программе символы констант и переменных. Заметим, что эти термы не содержат констант, обозначающих значения входных переменных, но содержат приписанные предикатным символам значения. Заметим, что в общем случае значения приписываются не вхождением предикатных символов в программу, а вхождениям их в протокол. Таким образом, у нас появляется порождающий процесс, управляемый выбором значений предикатов, результатом которого является бесконечное множество термов в сигнатуре (Ф, П). Это множество назовем формальной разверткой схемы программы. Слово формальный подчеркивает то, что при его построении не используется какая бы то ни было интерпретация функциональных и предикатных символов. Чисто символический характер формальной развертки позволяет говорить о языке, воспринимающем это множество.

Некоторые классы формальных разверток продемонстрировали два принципиально важных свойства:

• (2)    Некоторые детерминанты воспринимаются субрекурсивными языками, существенно более простыми, нежели языки, воспринимающие перечислимые множества.

Первый пример такого детерминанта привел Янов, (Янов, 1957.) для указанного выше подкласса схем, получивших название схем Янова. Для его сигнатуры Ф == {А.1, ... ,Ап}и П = {Pi, • • • ,pm} детерминант был образован последовательностями вида

(ai(0)... ffm(0)) A io ... (ai(k)... (^)) Aik где aj— это pj-или pj, и воспринимался конечным автоматом. Это, в частности, означало, что свойство схем Янова иметь одинаковый детерминант оказывается разрешимым, поскольку разрешима эквивалентность двух конечных автоматов.

Детерминант для произвольных схем программ был построен Иткиным (Иткин, 1972). Его протоколы строились следующим образом: брался произвольный путь от входа до выхода из схемы программы. Каждому вхождению предикатного символа в этот путь присваивалось значение, предписанное данным путем (выходная вершина формально считалась предикатным символом, аргументами которого были все переменные программы). В аргументы каждого предикатного символа ставилось его „термальное значение“ — функциональный терм с аргументами из констант и входных переменных, полученный путем замыкания подстановок, вызываемых операторами присваивания, попавшими на выбранный путь. Этот детерминант воспринимается двухленточным конечным автоматом и, стало быть, тоже разрешим.

Постанализ. Прежде всего, заметим, что в работах по абстрактной и обобщенной вычислимости, равно как и в теоретико-программных работах, содержится гораздо больше идей и тонкостей, нежели те, которые автор в состоянии был усмотреть и обсудить. Приходится сожалеть, что такой интересный материал рассеян, в основном, по трудам конференций и журналам и в целом с трудом доступен одному читателю. Поэтому и критика, и апология, которые содержатся в этом разделе, будут неизбежно поверхностными.

Объем класса абстрактно вычислимых функций. На рис. 2 показана схема эквивалентностей и сводимостей разных определений абстрактной вычислимости. Автор не уверен, что схема исчерпывающая. Сделаем к ней некоторые замечания.

Определения абстрактной вычислимости имеют разные формальные параметры, создавая конструкции равной общности и часто при несовпадающих предпосылках. Некоторые эквивалентности доказываются при дополнительных условиях.

Униформные рефлексивные структуры (УРС) и базисная рекурсивных функций теория (БРФТ) — это системы разной степени общности. В первой нумерация задана изначально, построение второй обеспечивается более подробными аксиомами. Связь вычислительных теорий с БРФТ лишь только обозначена Фенстадом (Фенстад, 1974). Не исключено, однако, что такая связь изучается в книге Фенстада (Фенстад, 1978а), которая была автору недоступна. От себя добавим, что должен существовать сравнительно прямой способ вложения простой и поисковой вычислимостей (ППВ) в БРФТ в силу явного построения индексов и постулирования вычислимости универсальной функции. Вариант вычислительной теории, предложенный Фенстадом (Фенстад, 1978), сближается с теорией комбинаторных пространств.

Думается, что треугольники сводимостей НВ ППВ ИО и ТВ (ОА, РП)—ЭО на рис. 2 достоверно и интуитивно убедительно формируют объем класса функций, вычислимых в некоторой алгебраической системе hD, С, Ф, П, П). При связи ППВ-ИО и ППВ—НВ (Московакис, 1969а) включает со стороны ППВ в сигнатуру П предикат равенства. Во всех трех моделях — ППВ, РЮ и НВ — определение абстрактной вычислимости может быть релятивизировано к любому набору констант С из D. При изучении сводимостей оказывается весьма удобным наличие для нумерационно-вычислимых функций примитивно рекурсивного детерминанта из булевых формул (мы можем использовать этот термин, так как эта характеризация, установленная Лакомбом, вполне соответствует определению детерминанта).

Эффективные определения Фридмана (Фридман, 1969а) — это просто задание абстрактно вычислимой функции ее перечислимым детерминантом. Связи ТВ^ЭО и О А ^ЭО устанавливаются простой демонстрацией того факта, что протоколы вычислений в тьюринговых вычислениях и операторных алгоритмах непосредственно транслируются в перечислимый детерминант, образованный клаузами Фридмана. При доказательстве ЭО^ТВ Фридман апеллирует к тезису Черча (в применении к модели Т) и к перечислимости ЭО-детерминанта. В изучении операторных алгоритмов Фридман использует свой вариант модели ОА и отмечает, что программисты обратили его внимание на связь его модели с моделью граф-схем с памятью в варианте Патерсона (Патерсон, 1968). В связи ТВ->-ОА Фридман использует схемы программ со счетчиками, поскольку ОА-программы могут использовать только ограниченное, независимое от вычислений, число ячеек памяти, а также постулирует наличие предиката равенства. Счетчики моделируют перебор и вычисление по геделевым номерам клаус детерминанта. Операторные алгоритмы (ОА) и рекурсивные программы (РП) без дополнительных требований к сигнатуре обладают разной силой вычислимости: О А сводится к РП в той же сигнатуре, однако, как показали Патерсон и Хьюитт (Патерсон, Хьюитт, 1970), существует РП, для которой нет эквивалентного О А в той же сигнатуре (на самом деле доказывается отсутствие О А с тем же детерминантом).

Связь эффективной определимости и нумерационной вычислимости аккуратно не прослежена, но трансляция клауз Фридмана в булевый детерминант Лакомба при наличии предиката равенства очевидных трудностей не обнаруживает.

Вложимость арифметических моделей. Практически во всех моделях абстрактной вычислимости демонстрируется буквальная вложимость той или иной модели арифметической вычислимости, но не каждой. Мы ограничимся констатациями, хотя более глубокий анализ был бы весьма интересен.

Изобразимость по Геделю находит свое прямое обобщение в инвариантной определимости.

Рекурсивная определимость по Эрбрану-Геделю допускает тривиальное обобщение на систему вида hD, Ф, =), если ввести в исчисление равенств в виде аксиом счетное множество равенств, представляющее диаграмму системы hD, Ф, =), т. е. равенств вида ^i(c Xi_v . . ,ca;_ri)=ct/, выражающих ин формацию о том, что ^i( х 1,.. .iXTi^y.^ литературе по программированию (например, Дарлингтон, 1978) рассматривается исчисление равенств для произвольной системы hD, Ф,П,=), в которой рекурсивное описание записывается в синтаксисе условных термов (Маккарти, 1961), а правила вывода называются „переписываниями “. Теория этой модели пока небогата: в близких формализмах доказана теорема о неподвижной точке (Манна, 1974), схема смешанных вычислений, или аналог s-m-n- теоремы (Ершов, 1978).

Лямбда-определимость по Черчу сама по себе является абстрактной моделью, в которую вкладывается арифметическая вычислимость путем отождествлений выделенных термов с элементами системы hN,0, =, ф Автор не нашел, однако, аналогичного прямого вложения произвольных систем в тот или иной вариант A-исчисления. Следует, однако, отметить очевидную связь A-исчисления с теориями абстрактной вычислимости в большом (УРС, БРФТ). Стронг (Стронг, 1968) рассматривает свою теорию как вариант комбинаторной логики (Карри, 1930, Карри и Фейс, 1958).

Частично рекурсивные функции по Клини непосредственно обобщаются в простую и поисковую вычислимости.

Машины Тьюринга со временем были обобщены на теорию вычислимости в алфавитных функциях (ср. Марков, 1951). Обобщение на Т-модель (Фридман, 1969а) следует признать весьма прямолинейным.

Операторные алгоритмы и рекурсивные программы с самого начала были определены для произвольной алгебраической системы.

Пока что нет никакого подхода к тому, чтобы определить какой-то аналог диофантовых множеств для произвольных предметных областей. В то же время такое обобщение было бы весьма интересно, так как диофантовы множества в очень чистой форме отделяют, три основных стороны эффективных вычислений: комбинаторный перебор (аргументов и параметров многочлена), прямое вычисление (значение многочлена) и отождествление (проверка на равенство). Кроме того, такое обобщение позволит, по-видимому, лучше разобраться в кодирующих свойствах многочленов.

Несколько слов о полноте воспроизведения общей теории вычислимости. В той или иной модели найдены разные формулировки всех основных теорем, особенно в базисных теориях, теории комбинаторных пространств, простой и поисковой вычислимостях и тьюринговых вычислениях. Производит большое впечатление доказательная сила аксиом униформных рефлексивных структур. В то же время бросается в глаза некоторая произвольность исходных посылок в построении абстрактной теории вычислимости. В теории, если можно так выразиться, преобладает наблюдательный подход.

Абстрагированность от арифметической вычислимости. Анализ этого обстоятельства обнажает самые чувствительные места большинства работ по абстрактной вычислимости. Многие авторы (например, Крайзел, 1969; Фридман, 1969а; Грильо, 1974) обращают внимание на большую трудность отстраниться от явной или скрытой опоры на арифметическую вычислимость. Наблюдая цитированные работы, можно найти два главных употребления арифметической вычислимости. Одно из них — это выделение в предметной области образа натурального ряда (сплинтера) как средства обеспечения свойств рефлексивности (нумеруемости) или как средства пересчета предметной области. Второе — это определение абстрактно рекурсивных функций с использованием понятия перечислимого множества (см. перечислимость детерминантов у Лакомба в нумерационной вычислимости и у Фридмана в эффективной определимости). Оба использования, по мнению автора, скрывают сущности. Первое уводит в сторону от выяснения абстрактных условий кодируемости программ и представления количеств в символической форме. Второе — вообще отбрасывает поиски сущности вычислимости на исходные позиции.

Если не говорить о теории абстрактной вычислимости в большом (УРС, БРФТ), наиболее фундаментальным подходом представляется инвариантная определимость. Правда, из соображений скорее философского, нежели технического характера, этой точке зрения может быть противопоставлено предпочтение какой-нибудь чисто алгоритмической модели типа ОА или ТВ (см., например, Цейтин, 1981). В любом варианте, однако, остается пока что открытая проблема обеспечения рефлексивности или — более общо — придания предметной области свойства быть носителем информации, свойства, выраженного в терминах сигнатуры базовой системы.

Абстрагированность от синтаксиса программ. До последнего времени эта задача в ее математическом выражении, похоже, даже не возникала. Как ни странно, впервые обратили внимание на внепрограммное представление программных сущностей сами программисты. В теоретическом программировании постепенно созрел взгляд на программу как на упаковку множества вычислений, возникающих при исполнении программы для разных ее входных данных. Это множество вычислений оказывалось более устойчивым объектом, нежели разные обличья программы. В то же время некоторые свойства программы находили в этом множестве более явное выражение, нежели в ее конкретном тексте. Так появились понятия разных программных инвариантов, в том числе и уже упомянутые детерминанты. В рассмотренных статьях по абстрактной вычислимости мы находим аналогичные конструкции только в двух моделях: клаузы Фридмана в ЭО и булевы характеризации Лакомба в НВ. Естественно, не надо забывать и о перечислении графика вычислимой функции элементарными функциями по Кальмару (Кальмар, 1943).

Другую форму абстрагируемости от программ мы находим в вычислительных теориях. Эта абстракция имеет свои преимущества, однако она не позволяет говорить об индивидуальных функциях.

Еще один подход к абстрактной вычислимости. После всего сказанного нам очень легко выразить основную идею: взять понятие детерминанта за определение вычислимой функции. Вторая часть основной идеи — строить детерминант для сигнатуры, а не для конкретной алгебраической системы, т. е. не привлекая интерпретации операционных символов. Дадим более точную схему определения.

Пусть дана алгебраическая система А = (D, ОД, П, R¹). Пусть Xn= {х1, ... ,xn} — символы переменных. Определим множество ТAn вычислительных термов (п>0). Любая константа, с ЕС ii любая перемеппая xiGXn — это вычислите, лытый терм. Если ^i — (функциональный символ и R(^i)=r и 11, ... ,tr — вычислительные термы, то ^i( 11, ... ,tr) — вычислительный терм. Если nj — предикатнь 1Й символ и Rjjv^=s и 11, .. .,1s — вычислительные термы, то nj-( 11, ... ,1s) -предикатный терм. Если р — предикатный терм и t вычислительный терм, то (р:1) и (р:1)-вычислительные термы. Определим для вычислительных термов функцию оценки val. Если ж — значение константы сж или переменной х, то valcж=ж, ма1х=ж. Далее val ^i( 11, ... ,tr) = ^i(v alt1, ... ,valtr); valn j-( 11, ... ,1s) =nj-(v alt1,

... ,valt s). Наконец, val(p:t)=ecaii valp, то valt иначе не определен, are(p:t) ==если valp, то неопределен, иначе valt. Значение любого из термов не определено, если какой-либо из его аргументов не определен,

Схема определения. Функция f.Dn^D называется вычислимой в А, если существует конечно порожденное множество DetfС Та^п (детерминант функции/), такое, что

• (1)    V (Жх..... х_п. y)GF3^(Х1.....xj gD etF :val t (жх.....жД =y;

• (2)    V (Ж1..... x_n . у) Vt 1ii.....x_n) GDetF va It (жх..... x_n) = y^(жх.....ж_п. y)GF.

Заметим, что это определение не исключает многозначных функций.

Естественно, главный пробел в этой схеме определения — это неуказанность способа порождения детерминанта. Опираясь на результаты, из теории схем программ, мы надеемся, что это может быть какой-либо автоматный язык, благодаря чисто комбинаторному способу порождения детерминанта. Напомним, что для ОА детерминантом может быть конечный двухленточный автомат. Для рекурсивных программ Розен (Розен, 1975) показал, что детерминант, весьма похожий на наш, описывается контекстно-свободным языком. Этот результат, однако, еще не может считаться окончательным: КС-грамматики имеют неразрешимую проблему эквивалентности, а разрешимость детерминантов рекурсивных программ — открытая проблема с шансами на успех (см. последний результат Сабельфельда (Сабельфельд, 1981)).

Заметим, что это определение — чисто синтаксическое. Оно задает пучок вычислимых функций, которые для разных интерпретаций операционных символов будут иметь один и тот же детерминант, а рисунок графиков будет, помимо конкретных значений, различаться еще и областями определения. Даже в рамках одной интерпретации каждый детерминант может воплощаться в бесконечном разнообразии программ.

Самым твердым орешком для такого рода определения будет реализация свойств рефлексивности. До сих пор не ясно, можно ли будет найти схемное доказательство теоремы о вычислимости универсальной функции. Один из возможных подходов к этому — это использование понятия универсальных грамматик в теории формальных языков.

Другой подход — это аксиоматизация предметной области как множества конструктивных объектов. Такая аксиоматика, по-видимому, создаст на носителе некоторую присущую ему систему отношений и конструкторов, образующих систему операций, которая через то или иное определение вычислимости будет создавать на данном носителе некоторый „абсолютный11 класс вычислимых функций, и этот носитель уже потом можно будет релятивизировать к любой системе с данным носителем.

Такой подход, однако, оставляет в стороне случай произвольных областей, для которых требование их конструктивности будет избыточным. В таком случае операции базовой сигнатуры становятся для нас оракулами по существу, и нам не остается ничего другого, как чисто аксиоматически попробовать выразить их кодирующие свойства.

Автору представляется весьма интересным изучить вопрос порождения детерминантов из инвариантных определений вычислимых функций логическими средствами.

Заключение. Абстрактная теория вычислимости представляет интерес по многим показателям. Мы не будем повторять глубокий анализ Крайзела (Крайзел, 1969) и лишь добавим к его аргументам, что одно из серьезных употреблений такой теории будет лежать в программировании, где релятивизация свойств программы к заданной „системе команд“ составляет один из основных принципов. Другим принципом системного программирования является как можно более полное изучение схемных, т. е. инвариантных свойств программы.

Мы уже отмечали, что объем понятия абстрактно вычислимой функции уже нащупан. Однако логический анализ предпосылок абстрактной вычислимости может быть продолжен. Абстрактная теория вычислимости может сыграть свою роль в усилении позитивной стороны теории. Действительно, не так уж интересно разыскивать абстрактное обобщение неразрешимой арифметической задачи, хотя и здесь возможен познавательный прогресс благодаря разделению сущностей. Другой, совершенно не затронутой стороной теории является разработка методов синтеза программ из разных форм априорного значения о задаче в разных предметных областях. Эта сторона проблемы, однако, требует своего анализа.