Рекурсивные функции

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Лекции

по теории вычислимости

Рекурсивные функции

Бухараев Н.Р.

Казань, КГУ 1999

Теория алгоритмов. Основные результаты

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

Программы как данные

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

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

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

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

Кодирование программ

(Эффективной) нумерацией, или перечислением множества А назовем произвольное эффективное отображение f :N A, f(N)=A; таким образом, мы допускаем, что в перечислении {f(1),f(2),f(3),....} множества А каждый его элемент может встретиться несколько (но - хотя бы один!) раз. Множества, для которых существует эффективная нумерация, назовем (эффективно) перечислимыми.

Множество A эффективно счетно, если существует эффективное кодирование элементов А натуральными числами, т.е. взаимно-однозначное эффективное отображение f множества А наN. Заметим, что в этом случае обратное отображение f -¹ также эффективно, т.е. существует возможность эффективного декодирования.

Наконец, множество А эффективно, если оно конечно или эффективно счетно. кодирование параметризация семантика математический

Теорема 1. Класс FD-программ эффективно счетен.

Доказательство.

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

Для реализации этой схемы нам понадобитьсяследующая

Лемма (о декартовом произведении).

Если А - эффективное множество, то

для любого эффективного множества B AB эффективно (и, следовательно, любое декартово произведение A1A2...Аn эффективных множествэффективно);

множество A*, A*=_{n N} Aⁿ, всех конечных последовательностей элементов А эффективно счетно.

Если B - эффективно счетно, то утверждение тривиально следует из показанного в лекции 1 факта эффективной счетности NN. Если же B - конечно, то пусть f1:NA - эффективное кодирование, а f2 - 1-1 конечное отображение N в B, B={f(1),...,f(k)}. Тогда

F(n)= < f1(n div k), f2(n mod k) >

где n div k, n mod k - соответственно, целая часть и остаток от деления n на k, -1-1 отображение N на AB.

По основной теореме арифметики, для любого числа n, n N, существует единственное разложение на произведение степеней простых чисел :

n=p(1)ⁿ⁽¹⁾* p(2)ⁿ⁽²⁾*... *p(k)^n(k)=_i=1,k p(i)ⁿ⁽ⁱ⁾

(где p(i) - i-ое простое число), что и дает требуемое 1-1 отображение N на N*:n<n(1),n(2),...,n(k)> и, следовательно, на A*.

Замечания и упражнения

Закончите доказательство, построив FD-программы вычисления функций n div k, n mod k и разложения числа на простые множители и показав, тем самым, эффективность выбранных кодировок.

Взятое нами из процедурного программирования понятие (конструктивного) типа данных (в терминологии объектного программирования - классов, в терминологии универсальной алгебры - алгебраических систем) подразумевает рассмотрениенекоторого множества А значений данных совместно со средствами их обработки, т.е. наличия некоторых вычислимых функций на А. Если f: AN эффективное кодирование и g:AA, то g естественно считать вычислимой тогда и только тогда, когда вычислима соответствующая функция на кодах - образ g при отображении f, т.е.функция f(x)fg(x).

Покажите, что для любого эффективного счетного множества A

операция конкатенации ( соединения, приписывания ) последовательностей вычислима;

операции

Элемент_n-ки(<a(1),a(2),...,a(n)>,i)=a(i), i N,

Элемент_последовательности(<a(1),a(2),...,a(n)>,i)=a(i), i N,

взятия проекции Aⁿ, для любого n N, и A* на заданную координату вычислима.

с) Заметим, что операции взятия проекции можно трактовать как операции “выборки компоненты по индексу”, что открывает нам путь к неявному употреблению статических и динамических массивов в языке FD-программ. Действительно, можно завести обычную (числовую) переменную - скажем, с именем ArrayCode, полагая, что она содержит код некоторой конечной числовой последовательности Array и моделируя нужные операции над элементами массива функциями над их кодами. Скажем, присваивание ArrayCode:= ArrayCode*p_i ,будет моделировать присваивание Array[i]:=S(Array[i]). Таким образом, мы можем без опасения расширить синтаксис FD-программ введением индексных переменных, полагая операторы работы с массивами просто иной формой записи операторов работы с их кодами.

Приступим теперь к построению нумерации программ. FD-программы, по определению, есть конечные последовательности пар вида <k: op> k, k N - числовая метка, а op - оператор. Мы уже научились строить кодирования конечных последовательностей и пар, для этого достаточно построить эффективное кодирование всех возможных операторов.

Каждый оператор однозначно характеризуется следующей парой - тип (название) оператора (stop, if-then-else, приваивания) и список параметров оператора <y_1, y_2,..., y_m>, среди которых - метки операторов, переменные, функциональные и логические выражения. Оператор start стоит всегда в начале FD-программы и может быть задан только списком своих параметров. Типам других операторов нетрудно сопоставить числовые коды - скажем, перенумеровать в приведенном выше порядке. Остается закодировать числами каждое из возможных значений параметров оператора.

Метки операторов не нуждаются в особом кодировании - это уже натуральные числа. Без ограничения общности, можно полагать, что каждая из переменных имеет вид x_i, iN-поставим каждой из переменных x_i в соответствие ее номерi. Наконец, перенумеруем все функциональные и предикатные символы (скажем, ноль-функцию 0 - нулем, функцию следования S - единицей и предикат равенства - двойкой) и закодируем функциональные и логические выражения, имеющие вид f(x_1, x_2,..., x_n) кодом пары <i,j>, где i - номер функционального или предикатного символа f,j - код n-ки < j_1, j_2,..., j_n >, j_1, j_2,..., j_n - коды имен переменных x_1, x_2,..., x_n.

(конец доказательства)

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

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

Поскольку каждая программа вычисляет некоторую функцию, введенная нумерация программ порождает некоторую нумерацию функций. Через Pk обозначим программу с кодом k,а через _k - (одноместную) функцию, вычисляемую программойPk (для n-местных функций будем употреблять обозначение _k⁽ⁿ⁾ ). Очевидно,

_{1, 2, 3,....}

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

Правда, в отличие от нумерации программ, у нас нет никаких оснований считать эту нумерацию эффективным кодированием. Заметим пока, что, как минимум, это нумерацияне взаимно-однозначна. Действительно, мы кодировали синтаксис программ, и любые синтаксически различные программы имеют разные коды. С другой стороны, каждая вычислимая функция вычисляется бесконечным классом программ. Скажем, если P - одна такая программа, то программа, полученная дописыванием к ней “фиктивного” оператора x:=x, вычисляет ту же функцию.

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

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

A={f_1, f₂,..., f_i,...}

Даже если каждая из функций f_i вычислима (некоторым алгоритмом P_i), это не гарантирует существование единого алгоритма вычисления всех функций. Назовем класс A равномерно перечислимым, если это действительно так, т.е. существует двуместная вычислимая функция F, что класс А состоит в точности из функций вида F(n,x), для некоторых n из N; функцию F назовем универсальной функцией класса A.Ясно (пусть пока, быть может, лишь на интуитивном уровне), что nF(n,x) - эффективная нумерация класса А, которую мы также назовем равномерной.

Наша ближайшая цель - показать, что

Определенная нами геделева нумерация вычислимых функций равномерна (теорема об универсальной функции),

Она уникальна по отношению к другим равномерным нумерациям - по номеру вычислимой функции в заданной равномерной нумерации можно эффективно найти его номер в геделевой нумерации (теорема о параметризации).

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

Теорема о параметризации

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

Для явного разделения аргументов и параметров в математике обычно применяют т.н. -нотацию А.Черча, выписывая аргументы после символа ; по умолчанию, все остальные имена переменных, входящие в определение, - имена параметров определяемой функции. Так, например, k x^k - степенная, а x x^k - показательная функция.

Понятно, чтопараметрические определения определяют в реальности классы функций, полученных при разных значениях параметров (так, например, при разных значениях k мы получим различные показательные функции - 1^k , 2^k , 3^k и т.д.)

В программировании схожий смысл имеют глобальные переменные программы (процедуры) - это переменные, входящие в текст программы, но не определяемые явно в ней самой; при этом предполагается, что смысл таких переменных определяется внешним, по отношению к программе контекстом. Так, например, при определении FD-программ мы, вообще говоря, не предполагали, что значения входящих в программу переменных обязательно инициализированы вводом (оператором start) или оператором присваивания. Текст P такой программы мы можем рассматривать как параметрическое определение, задающие класс программ P(x₁,x₂,...,x_n) в зависимости от конкретных значений параметров x₁ ,x₂ ,...,x_n.

Пусть, для простоты, AnyProgram='start(x,y);Rest' -некоторая программа с двумя входными переменными x и y, с некоторым геделевым номером е, вычисляющая, соответственно некоторую двухместную функцию _e(x,y). Пусть, далее, AssignX - программа, присваивающая некоторое значениепеременной x, AssignX='x:=O(x);x:=s(x);...x:=s(x)'. Очевидно,функция f1(x), выдающая по значению x код программы P2 - вычислима ( в нашей нумерации f1(x)=c1*_i=1,x p(i)^c2 , для некоторых констант с1,с2 - кодов операторов x:=O(x) и x:=s(x), соответственно).

Геделев номер программы P,P=`start(y);AssignX;Rest' , которая имеет уже одну входную переменную y, - некоторая вычислимая функция s от аргументов e и x. По построению, для каждых значений e и x программа P, для каждого входа y, вычисляет то же значение, что и исходная программа AnyProgram. Такимобразом, мы доказывает важный и часто используемый в теории алгоритмов результат:

Теорема о параметризации.

Любую часть x1,x2,...,xn входных значений можно породить программно, более того - существует алгоритм, который генерирует по x1,x2,...,xn текст соответствующей программы. Более формально, существует тотальная вычислимая функция s такая, что

e N x Nⁿy Y^m (_s(e,x)(y)=_e(x,y) )

Замечание.

Выше, при доказательстве теоремы, мы полагали n=1 и m=1; общий случай получается тривиальным обощением приведенного построения.

Для перехода к формулировке теоремы в терминах нумераций, упомянутой ранее, положите F(x,y)= _e(x,y) для универсальной функции класса и некоторого e; по определению F вычислима - следовательно, такой геделевский номер найдется.

Универсальные функции

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

Назовем универсальной, для одноместных вычислимых функций, двухместную функцию u, u(e,x)=_e(x); аналогично вводиться понятие функции u⁽ⁿ⁾, универсальной для n-местных вычислимых функций. Теоретическое обоснование понятию компьютера как универсального интерпретатора дает

Теорема об универсальной функции

Для любого n, nN, универсальная функция u⁽ⁿ⁾ вычислима.

Доказательство.

При доказательстве мы можем ограничиться случаем N=1. Действительно, программу, вычисляющую n-местную функцию от аргументов x1,...,xn нетрудно конструктивно преобразовать впрограмму от одной переменной x - кода n-ки <x1,...,xn>. Поэтому, если вычислима функция u, универсальная для одноместных вычислимых функций, то вычислима ифункцияu⁽ⁿ⁾, для любого n.

Для того, чтобы четче выявить основную идею алгоритма, не перегружая изложение техническими деталями, приведем программу вычисления функции u в расширенном синтаксисе FD-программ, допускающем динамические массивы, обращения к вычислимым функциям, циклы с предусловием и условные операторы (см. данное выше замечание 3 и предыдущую лекцию), а также будем допускать кириллические имена переменных и функций. На вход этой программы будет подаваться код интерпретируемой программы - в стандартном синтаксисе; снова, без ограничения общности, полагаем, что все переменные входных программ имеют имена вида xi, i N.

Заметим, что употребляемые в программе функции Элемент_последовательности, выдающая значение проекции последовательности с кодом e на заданную координату, а также функции Элемент_пары и Элемент_Четверки, выдающие проекций для нумерации пар и четверок чисел, вычислимы согласно замечанию 2. Доказательство вычислимости функции Значение_выражения, выдающей по коду выражение его значения в текущем состоянии программы, оставляем читателю в качестве упражнения - очевидно, соответствуюшая программа должна разбирать структуру выражения точно также, как приведенная ниже программа разбирает структуру операторов программы.

{первый аргумент универсальной функций - код программы, второй - “собственно” данные}

start(Код_программы, Аргумент);

{массив Состояние содержит на 0-м месте метку текущего оператора}

{ на остальных - все используемые в интепретируемой программе}

{ значения переменных x1,...,xn} ;

Состояние[0]:=2; {метка первого, после start, оператора}

Номер_входной_переменной:=Элемент_последовательности(Код_программы,1)

Состояние[Номер_входной переменной]:=Аргумент;

Код_оператора:=Элемент_последовательности(Код_программы, 2);

{код текущего оператора}

Код_типа_оператора:=Элемент_пары(Оператор,1);

while Код_типа_оператора1 {текущийоператора - не оператор stop} do

begin {начало тела цикла}

Аргументы:=Элемент_пары(Оператор,2); {код списка аргументов}

{разбор случаев различных значений типа операторов}

if Код_типа_оператора=3 { это оператор присваивания}

then

begin

{обработка оператора присваивания}

Номер_переменной:=Элемент_пары(Аргументы,1);

Код_выражения:=Элемент_пары(Аргументы,2);

Состояние[Номер_переменной]:=Значение_выражения(Код_выражения);

{следующим выполняется оператор со следующим номером}

Состояние[0]:=S(Состояние[0]) {метка следуюшей команды}

end

else {это оператор if then else}

begin

{обработка if then else}

Номер_первой_переменной:=Элемент_четверки (Аргументы,1);

Номер_второй_переменной_в_сравнении:= Элемент_четверки (Аргументы,2);

Первая_метка:= Элемент_четверки (Аргументы,3);

Вторая_метка:= Элемент_четверки (Аргументы,4);

if Состояние[Номер_первой_переменной]=

Состояние[Номер_второй_переменной]

then Состояние[0]:=Первая_метка

elseСостояние[0]:=Вторая_метка

end

{переход к выполнению следующего оператора}

Код_оператора:=Элемент_последовательности(Код_программы,Метка_оператора); Код_типа_оператора:=Элемент_пары(Код_оператора,1);

end {конец тела цикла}

Номер_выходной_переменной:=Элемент_пары(Код_оператора,2)

Результат:= Переменная[Номер_выходной_переменной];

stop(Результат);

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

Теорема Клини о нормальной форме

Напомним, что в предыдущей лекции состоянием программы мы назвали пару <l,Val>, Val - распределение значений переменных, а l - метка оператора, исполняемого вслед за текущим. В нашей программе состояние исходной интерпретируемой программы Pe задается массивом Переменная и переменной Метка_оператора. Структура нашей программы-интепретатора проста - она имеет вид

start(e,x);

Привести_программу_в_ начальное_состояние;

while Не_попали_в_конечное_состояние do Перейти_к_следующему_состоянию;

По_конечному_состоянию_определить_значение_функции;

stop(y)

т.е. эта программа перечисляет состояния интерпретируемой программы.

Как отмечалось в предыдушей лекции, все привычные нам явные методы определения функций дают примитивно рекурсивные функции. Интуитивно, примитивно рекурсивные функции - функции, вычисляемые программами поиска гарантированного решения, без возможности зацикливания. Так, нетрудно проверить, что использованные нами выше функции Элемент_последовательности, Элемент_пары, Элемент_четверки, Значение_выражения и, следовательно, функции на состояниях Привести_программу_в_ начальное_состояние и Определить_текушее_состояние - не только вычислимы, но примитивно рекурсивны. Предикат неравенства Не_попали_в_конечное состояние тоже примитивно рекурсивен или, пользуясь традиционной терминологиейтеории алгоритмов, примитивно разрешим.

Более формально, предикат P(x₁, x₂,...,x_n) (примитивно) разрешим, если он (примитивно) вычислим как булевская функция, т.е. (примитивно) вычислима двузначная функция p: Nⁿ{0,1},

p(x₁, x₂,...,x_n)=1 P(x₁, x₂,...,x_n)

Соответственно, множество А называется разрешимым (или - рекурсивным), если таков его предикат принадлежности (характеристическая функция) p_A, p_A = x (x A).

Упражнение. Покажите, что (примитивно) разрешимые предикаты образуют булеву алгебру, т.е. применение к разрешимым предикатам булевских операций - конъюнкции and, дизъюнкции or, отрицания not - дает снова разрешимые предикаты. Следовательно, то же справедливо относительно разрешимых множеств и теоретико-множественных операций - объединения, пересечения и отрицания.

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

Теорема Клини о нормальной форме

Существуютпримитивнорекурсивныефункция u и примитивно разрешимый предикат T такие, что e,x ( _e(x)=p ( k [T(e,x,k)])). В частности, e,x ( _e(x) k T(e,x,k))

(здесь и далее запись вида f(x)= означает, что функция f неопределена в точке x).

Доказательство.

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

{сделать шагов n шагов в вычислении универсальной функции}

{и проверить, не вычислилось ли значение y}

start(e,x,y,n);

Привести_программу_в_ начальное_состояние;

Счетчик:=O;

while Счетчик<=n and Не_попали_в_конечное_состояние do

begin Перейти_к_следующему_состоянию; Счетчик:=S(Счетчик) end

По_конечному_состоянию_определить_значение_функции

ifРезультат=y

stop(1) {true}

else

stop(0) {false}

end

Эта программа вычисляет предикат “при входных данных e,x программа вычисления универсальной функции на шаге n вычисляет y”, обозначим его через T1(e,x,n,y). Очевидно, за счет добавления счетчика - параметра цикла - единственный цикл нашей программы гарантированно сходиться, т.е. Т1 - примитивно разрешимый предикат. Для окончания доказательства осталось положить T(e,x,k)= T1(e,x,Элемент_пары(k,1),Элемент_пары(k,2)) и p(k)=Элемент_пары(k,2)

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

Неразрешимость

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

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

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

Перечислимость.

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

X P(X,Y)=not X (not P(X,Y) )

для любых списков переменных X=< x₁, x₂,...,x_n>, Y=< y₁, y₂,...,y_m>_.

Предикаты вида X P(X,Y), где P - разрешимый предикат, называют полуразрешимыми. Быть может, стоило назвать их “почти-разрешимыми”, поскольку стратегия их вычисления кажется совсем очевидной - это обычный алгоритм линейного поиска.

{пример “вычисления” x P(x,y)}

read(y);

x:=1;

found:=0; {0 - код для false}

while found=0 {not found}do

ifP(x,y)

then found:=1 {true}

else x:=x+1

write(found)

Однако, очевидность обманчива - если предикат x P(x,y) верен, то наш алгоритм, найдя значение соответствующего x, действительно выдаст значение 1, т.е. true. Но в случае, когда x P(x,y) не верен, алгоритм не выдаст значение 0 (false), оставив значение предиката неопределенным. Чисто теоретически, мы могли бы считать предыдущую программу вычислением предиката x P(x,y) за бесконечное время, но, к сожалению, в реальности у нас нет бесконечного времени, чтобы гарантированно дождаться ее результата.

Однако, заметим для дальнейшего,что операция ограниченной квантификации x [1,m] (P(x,y), конечно же, вычислима как функция от m и y:

found:=0; {false}

x:=1;

while ( x<= m) and (found=0) do

if P(x,y)

then found:=1 {true}

else x:=x+1

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

Теорема. Для любого множества A, A N, следующие условия эквивалентны:

A - область значений некоторой вычислимой функции f, A=f(N) (т.е. А перечислимо);

A - область определения некоторой вычислимой функции g,

A=g^-1(N) ;

A - проекция разрешимого предиката P, A={y: x P(x,y) };

A - проекция примитивно разрешимого предиката P, A={y: x P(x,y) }.

Доказательство.

Покажем следующую цепочку следствий 24312

24. Прямо следует из теоремы о нормальной форме.

4 3 Тривиально.

31Пусть P - разрешимый предикат иA={y: x P(x,y)}. В качестве f взять функцию, вычислимую следующим алгоритмом

read(n);

y:=Элемент_пары(n,1); m:=Элемент_пары(n,2);

{сделай m шагов в поиске x такого, что P(x,y)}

found:= x [1,m] P(x,y); {правая часть - обращение к вычислимой функции, см. выше}

if found then write(y)

Очевидно, f(N) {y: x P(x,y)}. Использованный прием с раскодировкой аргумента n на элементы пары обеспечивает, что, при разных n, мы будем делать все большее число шагов в подалгоритме линейного поиска и найдем нужный x, если он существует. Следовательно, верно и обратное включение.

12 Пусть f вычислима, A=f(N). Тогда в качестве g можно взять функцию y x (f(x)=y), вычислимую следующим алгоритмом

read(y);

found:=0;

x:=1;

while found=0 do

if f(x)=y

then found:=1

else x:=x+1

{если цикл завершился}

write(x)

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

Упражнения

Мы определили перечислимое множество А как множество значений некоторой произвольной вычислимой функции f. Немногоизменив алгоритм из 31, покажите, что

если А - не пустое множество, функцию f можно считать всюду определенной;

если А - бесконечное множество, функцию f можно считать всюду определенной и взаимно-однозначной, т.е. любое бесконечное перечислимое множество можно перечислять без повторений.

Теорема (решетка перечислимых множеств).

Пересечение и объединение перечислимых множеств A,B также перечислимо; иначе говоря, класс всех перечислимых множеств образуют решетку по включению (с минимальным элементом и максимальным элементом N)

Множество A разрешимо оно само и его дополнение N\A перечислимы

Доказательство.

По предыдущей теореме, найдутся разрешимые предикаты P1 и P2, такие, что A={y: x P1(x,y) } и B={y: x P2(x,y) }. Тогда, для любого x, x AB (x A) or (x B) ( y1 P1(x,y1)) or ( y2 P2(x,y2)) y1,y2 (P1(x,y1) orP2(x,y2)). По доказанному ранее, предикат P1(x,y1) orP2(x,y2) разрешим как дизъюнкция разрешимых предикатов. Следовательно, множество Аописывается полуразрешимым предикатом и (снова, по предыдущей теореме) перечислимо.

Если множество А разрешимо, то является областью значения (и определения) вычислимой функции IF(xA,x,) и перечислимо по определению. По доказанному ранее, множество N\A разрешимо и, следовательно, также перечислимо.

Пусть A и N\A перечислимы. Снова, во предыдущей теореме, найдутся разрешимые предикаты P1 и P2, такие, что A={y: x P1(x,y) } и N\A={y: x P2(x,y) }. Тогда характеристическую функцию множества A можно вычислить следующим алгоритмом:

read(n);

{выясняем, принадлежит ли n множеству A}

answer:=3; x:=1;

while answer=3 do

if P1(x,y) then answer:=1

else if P2(x,y) then answer:=0

else x:=x+1

{поскольку для любого x верно либо xA, либо x N\A }

{цикл обязательно завершиться}

write(answer)

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

существуют ли полуразрешимые, но не разрешимые предикаты, или, эквивалентно,

существуют ли перечислимые, но не разрешимые множества?

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

Неразрешимость - методы доказательства

Основными методами при доказательстве теорем о не существовании алгоритмовявляются

- прямой метод диагонализации, восходящий к "диагональному" доказательству несчетности множества действительных чиселГ. Кантором, и

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

Диагонализация

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

Пусть f - двуместная вычислимая, не обязательно - всюду определенная, функция и F, F={ x f(n,x): n N} - соответствующий f равномерно перечислимый класс одноместных функций (см. определение в замечании 2). Как определить функцию, не принадлежащую классу F? Идея следующего определения прозрачна -поскольку такая функция должна отличаться от каждой функции f_n= x f(n,x) хотя бы в одной точке, попробуем сделать ее отличной от f_n ну, хотя бы, в точке n.

Назовем частичной диагональной функцией назовем функцию d(f)= x (f(x,x)+1), а (тотальной) диагональной функцией D(f) - доопределение нулевым значением функции d то всюду определенной функции. Для сокращения записи функций, определяемых разбором случаев, далее будем применять программистскую нотацию -

d(f)= x IF(f(x,x),S(f(x,x)), )

D(F)= x IF(f(x,x),S(f(x,x)), 0)

Если класс F содержит только тотальные функции, то n f(n,n)d(n) и желаемая цель достигнута, но если F содержит и частичные функции, то частичная диагонализация не решает проблему - равенство d(n)=f(n,n)+1=f(n,n) может выполняться при f(n,n)= ! Гарантированно решает проблему лишь функция D - она в действительно отличается от каждой функции из F.

Взяв в качестве класса F класс всех вычислимых функций, и в качестве f - его универсальную функцию, мы получаем явный и очень простой пример невычислимой функции.

Замечания и упражнения

Докажите, что

d - вычислимая функция.

D - вычислимая функция предикат f(x,x)разрешим.

Частичная проблема остановки- можно ли построить алгоритм, проверяющий по тексту программы x, сходиться ли она на входе x?Предикат _x(x) неразрешим

Класс Total всех всюду определенных вычислимых функций не равномерно перечислим

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

Отсутствие у класса Total “хорошей” нумерации реально ощущается в программировании в принципиальной невозможности определения “хороших” языков программирования - либо такой язык обязан содержать средства зацикливания, либо он не является универсальным, т.е. достаточным для реализации любых (даже всюду определенных!) алгоритмов.

Проблема распознавания тотальности - можно ли построить алгоритм, проверяющий по тексту программы x, сходиться ли она на всех входных данных? Предикат y _x(y) неразрешим.

Замечание и обсуждение. Диагонализация - что дальше?

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

Множество А продуктивно, если существует алгоритм, опровергающий его перечислимость указанием явного контрпримера - более формально, если существует вычислимая функция f, f Total, такая, что

x (Wx A f(x) Wx\A)

Перечислимые множество с продуктивным дополнением называюткреативными, или - творческими. Благодаря нащим диагональным рассуждениям и предыдущим упражнениям, мы уже имеем пример креативного множества - это множество K,

K={x: x Wx}={x: _x(x)}

Чуть позже мы вернемся к тому, что заставило Поста дать столь интригующее название введенному им классу множеств.

Сводимость

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

Приведем примеры применения метода сведения при доказательстве неразрешимости.

Теорема (примеры неразрешимости).

Следующие предикаты (проблемы) - неразрешимы:

Предикат `_x(y) определена' ( проблема остановки: предъявить алгоритм, распознающий, сходиться липрограмма x на входе y);

Предикат ` y _x(y)=0' неразрешим. (проблема распознавания 0-функции).

Предикат ` y _x1(y)=_x2(y)' (проблема распознавания функциональной эквивалентности программ);

Доказательство.

(Сведение к частичной проблеме остановки). Если бы функция

f1= x IF ( _x(y), 1, 0)

была вычислимой, то вычислимой была бы и функция x f1(x,x),что противоречит неразрешимости проблемы `_x(x) определена'.

(Сведение к проблеме остановки).

Пусть, от противного, функция

f2= x IF ( y _x(y)=0, 1, 0)

вычислима. Тогда функция f= x,y ( _x(x), 0, ) вычислима как композиция вычислимых, x,y f(x,y)=0(u(x,y)). Потеоремео параметризации, существует вычислимая функция kтакая,что x,y_k(x)(y)=f(x,y).

Тогда

если _x(x) определена, то y (f(x,y)=0)и f2(k(x))=1, и

если _x(x) не определена, то y(f(x,y) неопределена),следовательно, y (f(x,y) 0) и f2(k(x))=0.

Иначе говоря, если f2 вычислима, то разрешима проблема частичной остановки, что противоречит доказанному ранее.

(Сведение к проблеме распознавания 0-функции)

Пусть , от противного, функция

f3= x1,x2 IF( y (_x1(y)=_x2(y) ), 1,0)

вычислима, а c0 - некоторый индекс 0-функции, y ( _c0(y)=0). Тогдаодноместнаяфункция x с(x,c0)такжевычислима,что противоречит доказанному в предыдущем пункте.

Синтаксис и семантика. Теорема Райса

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

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

Теорема Райса

Для произвольного нетривиального (непустого и собственного) подкласса класса всех вычислимых функцийпроблема `_x ' неразрешима.

Доказательство (сведение к проблеме частичной остановки).

Поскольку класс разрешимых предикатов замкнут относительно операции отрицания, то проблема `<sub>x</sub> ' разрешима тогда и только тогда, когда разрешима проблема `_x '. Поэтому, без ограничения общности можно считать, что нигде не определенная функция - обозначим ее f - принадлежит (в противном случае будем доказывать неразрешимость проблемы`_x '). Пусть g - некоторая функция из (по условию, оно не пусто) и, по определению, f(x,y)=g(y), если _x (x) определена, и f(x,y) не определена, в противном случае. По теореме о параметризации, найдется тотальная вычислимая функция k, такая что x, y (_k(x)(y)=f(x,y) ). Тогда

если _x(x) определена, то _k(x)=gи _k(x) , и

если _x(x) не определена, то _k(x)=f и _k(x)

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

Приложение. Неразрешимые проблемы в других областях математики

Арифметика

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

Диофантовы уравнение не всегда имеют решение. Вспомним, например, знаменитое уравнение x²-2=0, отражающего проблему несоизмеримости диагонали квадрата с его длиной - проблему, приведшую к кризису ранней древнегреческой математической школы Пифагора и положившую начало долгих и труднейших поисков на, казалось бы, очевидный вопрос - “что же такое число?” Нахождение эффективной процедуры нахождения ответа на вопрос о существовании целых корней диофантовых уравнений была названа, десятой по счету, в 1900 году Д.Гильбертом в числе наиболее важных проблем математики.

В 1970 году Ю.Матиясевич завершил многолетние исследования этой проблемы, доказав, что 10 проблема Гильберта неразрешима. В реальности, был доказана следующая, значительно болееобщая

Теорема. Следующие условия эквивалентны

Множество А перечислимо

Множество А есть множество положительных значений некоторого диофантова многочлена p(x₁,x₂, x₃,..., x_n)

A={ p(x₁, x₂, x₃,..., x_n): x_i N }

Множество А есть проекция некоторогодиофантова многочлена p(x₁,x₂, x₃,..., x_n) -

A={x: x₂, x₃,..., x_n p(x, x₂, x₃,..., x_n)=0 }

(сравните с теоремой о проекции).

Это - исключительно сильный и неожиданныйтеоретико-рекурсивный результат, показывающий, что, все вычисления (в частности, все программирование) могут быть в принципе сведены к арифметике (вычислению диофантовых многочленов). В частности, он дает явные арифметические формулы порождения любых “нормальных”, т.е. встречающихся на практике, числовых множеств - например, многочлены, положительные значения которых есть, в точности, все числа Фибоначчи и все простые числа (хотя известно, что не существует многочлена, все значения которого есть в точности простые числа). Заметим, что хотя поиски“формулы простого числа” велись на протяжении веков, в получении окончательной формулы специфика определения простых чисел никак не участвует!

Алгебра

Вспомним, что один из центральных объектов исследования алгебры - группа - определяется как множество G, рассматриваемое вместе с некоторой бинарной операцией абстрактного “умножения” ( обозначим ее через ),удовлетворяющей следующим условиям (аксиомам группы):

А1) умножение ассоциативно: x, y, z (x(yz)= (xy)z)

А2) в G имеется единичный элемент e: x (xe= ex)

А3) для каждого элемента существует обратный: x y (xy = yx = e);

(элемент, обратный к x, обычно обозначают через x^-1)

Значимость групп -в том, что дают абстрактное аксиоматическое описание одного из наиболее важных объектов математики - класса перестановок ( взаимно-однозначных функций) элементов некоторого множества, рассматриваемых относительно операции композиции (последовательного применения) функций; единичный элемент e в этом случае есть тождественное преобразование, а x^-1 - функция, обратная к функции x. Это описание адекватно- любая группа изоморфна некоторой группе 1-1 преобразований.

Пусть X G. Словом в X называется произвольная последовательность обозначений степеней элементов w=x₁ⁿ¹, x₂ⁿ²,..., x_k^nk, для некоторых целых n_i и x_i X. Элемент группы x представляется словом w, если x= x₁ⁿ¹ x₂ⁿ² ... x_k^nk.Ясно, что элемент группы может, вообще говоря, иметь разное синтаксическое выражение в виде слова (так, например, в группе всех целых чисел по сложению 4=2+2=1+1+2=2+1+1=1+1+1+1)

Наиболее простые - а именно, конечно определенные - группы имеют конечное описание - именно, существует

конечное порождающее множество X такое, что любой элемент G представим словом в X, и

конечный список равенств слов w=w' такой, что любое другое равенство слов в группе выводиться (с использованием свойств равенства) из аксиом группы и этого списка “дополнительных аксиом”.

Очевидно, в этом случае мы можем эффективно порождать все равенства слов в G.Проблема тождества слов заключается в том, чтобы эффективно распознавать по тексту записей двух слов W,W' верно ли равенство W=W', или, эквивалентно, - построить алгоритм, распознающий по слову W, верно ли, что оно представляет данный элемент группы, заданный словом W'.Как показали Новиков (1955 г.) и Бун (1957 г.), проблема тождества слов неразрешима.

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

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

Математическая логика

Любая формальная математическая теория определяется следующими базовыми понятиями:

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

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

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

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