Арифметичность вычислимых функций

c:=a;
  {инвариант: ответ=сумма текущих значений c и b}
  while b<>0 do begin
     c:=c+1;
     b:=b-1;
  end;

1 c:=a
 2 if b=0 then goto 6 else goto 3
 3 c:=c+1
 4 b:=b-1
 5 goto 2
 6 stop

Арифметичность вычислимых функций

Сейчас мы докажем, что функции, вычислимые программами с конечным числом переменных, арифметичны, то есть их графики являются арифметическими множествами. В этом разделе мы вновь предполагаем некоторое знакомство читателя с логическими обозначениями, и будем рассматривать арифметические формулы, содержащие переменные по натуральным числам, равенство, константы 0 и 1, операции сложения и умножения, логические связки (И, ИЛИ, НЕ) и кванторы " для всех" и " существует". Формально говоря, мы рассматриваем сигнатуру, содержащую единственный двуместный предикатный символ (равенство), две константы 0 и 1 и два двуместных функциональных символа (сложение и умножение). Говоря об истинности таких формул, мы имеем в виду их истинность в стандартной интерпретации, носителем которой является множество N натуральных чисел.

Множество $$A \subset N^{k}$$ называется арифметическим, если существует арифметическая формула $$\alpha$$ с параметрами x1,...,xk, которая его представляет в следующем смысле: $$\langle n_1,\dots,n_k\rangle\hm\in A$$ тогда и только тогда, когда формула $$\alpha$$ истинна при значениях параметров x1=n1,..., xk=nk.

Теорема 67. График любой функции, вычисляемой программой с конечным числом переменных, является арифметическим множеством.

Пусть f : N -> N функция, вычислимая некоторой программой P с конечным числом переменных k1,...,kN. Будем считать, что входной переменной является k1, а выходной k2. Нам нужно написать формулу с двумя переменными x, y, которая была бы истинна тогда и только тогда, когда y=f(x). Состояние программы с конечным числом переменных полностью описывается значениями переменных и номером текущей команды (в процессорах соответствующий регистр часто называют program counter, по-русски счетчик команд). Легко понять, что соответствие между двумя последовательными состояниями программы с конечным числом переменных арифметично. Мы имеем в виду, что можно написать арифметическую формулу

Step(s1,...,sN,p,s1',...,sN',p'),

с 2N+2 переменными, которая утверждает, что данная программа P из состояния, где переменные равны s1,...,sN, а счетчик команд равен p, за один шаг переходит в состояние, где переменные равны s1',...,sn', а счетчик команд равен p'. (Договоримся, что значение p'=0 соответствует остановке программы.) Такая формула является конъюнкцией отдельных утверждений, соответствующих каждой строке программы. Пусть, например, строка 7 программы имеет вид k2:=k3. Тогда в конъюнкции будет член вида

$$(p=7)\Rightarrow ((s_{1}'=s_{1})\wedge (s_{2}'=s_{3}) \wedge (s_{3}'=s_{3}) \wedge \dots \wedge (s_{N}'=s_{N}) \wedge (p'=8)).$$

Для строки с условными переходами типа

3  if k5=0 then goto 17 else goto 33

в формуле будет два конъюнктивных члена (на два случая перехода)

$$((p=3) \wedge (s_{5}=0)) \Rightarrow ((s_{1}'=s_{1}) \wedge \dots \wedge (s_{N}'=s_{N}) \wedge (p'=17))$$

и

$$((p=3) \wedge (s_{5} \ne 0)) \Rightarrow ((s_{1}'=s_{1})\wedge \dots \wedge (s_{N}'=s_{N})\wedge (p'=33)).$$

Надо еще добавить утверждение о том, что при p=0 работа прекращается, то есть что переменные на следующем шаге сохраняют свои значения, и p' остается равным 0.

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

Это делается с помощью приема, традиционно называемого $$\beta$$ -функцией Геделя. Вот что имеется в виду.

Лемма 1. Для любого k можно найти сколь угодно большое целое положительное число b, при котором первые k членов последовательности b+1, 2b+1, 3b+1,... попарно взаимно просты.

Доказательство. Любой общий простой делитель двух из этих чисел будет делителем их разности, то есть числа lb при 0<l<k ; взяв b кратным k!, мы гарантируем, что он будет делителем числа b, но все члены нашей последовательности взаимно просты с b. Лемма доказана.

Лемма 2. Для любой последовательности x0,x1,...,xn натуральных чисел можно найти такие числа a и b, что xi есть остаток от деления a на b(i+1)+1.

Доказательство. Согласно предыдущей лемме, делители b(i+1)+1 можно взять взаимно простыми (и сколь угодно большими), остается воспользоваться " китайской теоремой об остатках". Эта теорема утверждает, что если целые положительные числа d1,...,dk взаимно просты, то при делении целого u на них может получиться любой заданный набор остатков. В самом деле, таких наборов будет d1d2... dk (поскольку при делении на di возможны остатки от 0 до di-1 ). При делении чисел u=0,1,...,d1d2... dk-1 получаются разные наборы остатков (если два числа u' и u'' дают одинаковые остатки, то их разность делится на все di, что невозможно в силу взаимной простоты). Поэтому чисел столько же, сколько наборов остатков, и должны появиться все наборы. Лемма 2 доказана.

Эта лемма показывает, что последовательность произвольной длины можно закодировать тремя числами a, b и n (последнее число длина последовательности). Таким образом, условно говоря, можно заменить " формулу"

$$\exists \langle x_0,\dots,x_n\rangle (\forall i \le n)[\dots x_i \dots]$$

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

$$\exists a \exists b \exists n (\forall i \le n)[\dots (остаток\ от\ деления\ a\ на\ b(i+1)+1)\dots ].$$

Мы будем записывать остаток от деления a на b(i+1)+1 как $$\beta (a,b,i)$$ (отсюда и название " бета-функция").

Возвращаясь к нашей программе P с конечным числом переменных k1,...,kN и вычисляемой ей функции f, можно записать утверждение вида f(x)=y так: существуют такое число шагов n и такие числа a1,b1,a2,b2,...,aN,bN,a,b, что

$$\beta (a_{1},b_{1},0),\dots ,\beta (a_{N},b_{N},0)$$ есть правильные начальные значения переменных (первое равно x, остальные равны 0 ); $$\beta (a,b,0)$$ есть правильное начальное значения счетчика команд, то есть 1 ;

для каждого i от 0 до n-1 имеет место$$Step(\beta (a_{1},b_{1},i),\dots ,\beta (a_{N},b_{N},i),\beta (a,b,i),\beta (a_{1},b_{1},i+1),\dots ,\beta (a_{N},b_{N},i+1),\beta (a,b,i+1)),$$ то есть каждый переход соответствует программе;

$$\beta (a_{2},b_{2},n)=y$$ (значение выходной переменной k2 в конце вычисления равно y ) и $$\beta (a,b,n)=0$$ (значение счетчика команд в конце вычисления равно 0, что по нашей договоренности соответствует остановке машины).

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

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

Теоремы Тарского и Геделя

Поскольку графики вычислимых функций арифметичны, очевидно, разрешимые и перечислимые множества тоже будут арифметическими. Тем самым мы можем оправдать название " арифметическая иерархия" для классов $$\Sigma _{n}$$ и $$\Pi _{n}$$:

Теорема 68. При любом n любое множество из класса $$\Sigma _{n}$$ или $$\Pi _{n}$$ арифметично (есть формула арифметики, выражающая принадлежность этому множеству).

После того, как мы доказали арифметичность вычислимых функций, все ясно множества из классов $$\Sigma _{n}$$ и $$\Pi _{n}$$ получаются навешиванием кванторов на разрешимые множества, а разрешимое множество арифметично.

Верно и обратное:

Теорема 69. Всякое арифметическое множество лежит в классе $$\Sigma _{n}$$ или $$\Pi _{n}$$ для некоторого n (и, естественно, для всех больших n ).

Формулу, задающую арифметическое множество, приведем к предваренной нормальной форме (вынеся кванторы наружу). Ясно, что бескванторная часть задает разрешимое множество, поэтому исходное множество принадлежит какому-то из классов $$\Sigma _{n}$$ или $$\Pi _{n}$$.

Можно и не использовать предваренной нормальной формы, а применить индукцию по длине формулы и сослаться на то, что пересечение, объединение и дополнение, а также проекция не выводят за пределы арифметической иерархии (объединения всех классов $$\Sigma _{n}$$ и $$\Pi _{n}$$ ).

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

Теорема 70. Любое арифметическое множество m -сводится к множеству T.

Это утверждение почти очевидно. Пусть A произвольное арифметическое множество. Пусть $$\alpha (x)$$ формула с одной переменной, которая выражает принадлежность множеству A. Это означает, что $$\alpha (n)$$ истинно при тех и только тех n, которые принадлежат A. Тогда вычислимая функция n $$\mapsto$$ номер формулы, которая является результатом подстановки константы n в $$\alpha (x))$$ m -сводит A к T.

Теорема 71. Множество T не арифметично.

После проведенной нами подготовки это утверждение очевидно: если бы T было арифметическим, то оно лежало бы в некотором конкретном классе $$\Sigma _{n}$$. Поскольку всякое арифметическое множество сводится к T, то по теореме 53 все арифметические множества лежали бы в этом классе. Но мы знаем, что множества из более высоких классов иерархии тоже арифметичны, но в $$\Sigma _{n}$$ не лежат.

Эта теорема называется теоремой Тарского. Ее можно прочесть так: множество арифметических истин не арифметично. Или: понятие арифметической истины невыразимо в арифметике.

Теорема 72. Множество T арифметических истин неперечислимо.

В самом деле, любое перечислимое множество арифметично.

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

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

  86. Сформулируйте и докажите аналогичное утверждения для формул ограниченной кванторной глубины (число вложенных кванторов) и для формул с ограниченным числом перемен кванторов в предваренной нормальной форме.

Прямое доказательство теорем Тарского и Геделя

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

Начиная доказывать теорему Тарского, предположим, что множество номеров всех истинных арифметических формул (без параметров) арифметично. Пусть T это множество, а $$\tau (x)$$ соответствующая формула. Перенумеруем также все формулы с одним параметром x ; пусть Fn(x) формула, имеющая номер n в этой нумерации. Рассмотрим формулу с единственным параметром x, утверждающую, что результат подстановки константы x в x -ую формулу с параметром ложен. Эту формулу можно написать так:

$$\exists\ z\ ( \neg \tau (z) \wedge Subst(z,x,x) ),$$

где Subst(p,q,r) формула с тремя параметрами, выражающая такое свойство: " p есть номер (в нумерации всех формул без параметров) той формулы, которая получится, если в q -ю формулу с одним параметром подставить константу r вместо этого параметра". Записанное в кавычках свойство описывает график некоторой вычислимой функции (соответствующей простым синтаксическим действиям и переходу от одной нумерации к другой) и потому существует выражающая его формула.

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

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

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

Теперь напишем формулу с одним параметром x, которая говорит, что результат подстановки числа x вместо параметра в x -ую формулу с одним параметром не имеет доказательства:

$$\neg \exists\ z\ \exists\ p\ [Subst(z,x,x) \wedge Proof(p,z)]$$

Эта формула имеет единственный параметр ( x ); пусть ее номер в нумерации таких формул равен N. Подставим N вместо параметра. Получится формула без параметров $$\phi.$$ По построению формула $$\phi$$ истинна, когда результат подстановки N в N -ю формулу с одним параметром недоказуем. А этот результат есть сама формула $$\phi,$$ так что она истинна тогда и только тогда, когда недоказуема. Значит, наше исчисление либо позволяет доказать ложную формулу $$\phi$$ (если $$\phi$$ ложна; в таком случае его называют неадекватным), либо не позволяет доказать истинную формулу $$\phi.$$

Заметим, что оба этих доказательства напоминают как построение неподвижной точки, так и классический парадокс лжеца:

$$\fbox{\hbox{\textsc{утверждение в рамке ложно}}}$$

Более тонкий анализ позволяет установить, что для любой достаточно богатой формальной системы (скажем, для формальной арифметики или теории множеств) множество доказуемых формул (теорем) и множество опровержимых формул (отрицания которых являются теоремам) являются перечислимыми эффективно неотделимыми множествами. Это делается примерно так. Рассмотрим два произвольных непересекающихся перечислимых множества A и B и вычислимую функцию f, которая на всех элементах множества A равна нулю, а на всех элементах множества B равна 1. Поскольку наша формальная система " достаточно богата", в ней (для любого данного числа n ) можно написать формулу Fn, утверждающую, что f(n)=0. При этом для $$n\in A$$ формула Fn будет доказуемой (протокол работы f на данном числе n, завершающийся получением ответа 0, можно превратить в доказательство того, что f(n)=0 ), а при $$n\in B$$ формула Fn будет опровержимой (поскольку можно доказать, что f(n)=1 ). Следовательно, пара $$\langle A,B\rangle$$ m -сводится к паре $$\langle $доказуемые формулы, опровержимые формулы$\rangle$$, и потому последняя пара является эффективно неотделимой.

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

Оказывается, что можно построить программу p с таким странным свойством: никакая программа q не является доказуемо различной с p. Программу p можно было бы назвать абсолютно непознаваемой: ведь формально доказав любое свойство $$\alpha$$ этой программы, можно было бы доказуемо отличить p от программы q, не обладающей этим свойством. (Мы предполагаем, что можно предъявить некоторую программу q, про которую можно формально доказать, что она не обладает свойством $$\alpha.$$ )

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

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

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

Арифметическая иерархия и перемены кванторов

Мы установили, что класс арифметических множеств есть объединение всех классов $$\Sigma _{n}$$ и $$\Pi _{n}$$. Посмотрим подробнее, как связан номер класса с числом перемен кванторов в арифметической формуле.

Чтобы сделать это, надо уточнить, какие формулы мы считаем бескванторными. Если представлять сложение и умножение предикатными символами, то бескванторные формулы будут логическими комбинациями формул xi + xj = xk и xi x xj=xk ; при этом уже для записи формулы a+b+c=d нам понадобится квантор: она записывается как $$\exists u ((a+b=u) \wedge (u+c=d))$$. Мы же, как это обычно делается, будем считать сложение и умножение функциональными символами и тем самым разрешим использовать произвольные многочлены с целыми коэффициентами в бескванторных формулах. При этом бескванторными формулами будут логические комбинации выражений вида P=Q, где P и Q произвольные многочлены с целыми коэффициентами. Тогда верна такая теорема:

Теорема 73. Множество $$A \subset N$$ принадлежит классу $$\Sigma _{n}$$ ( n >= 1 ) тогда и только тогда, когда принадлежность ему выражается формулой в предваренной нормальной форме, начинающейся с квантора существования и содержащей n групп одноименных кванторов.

(Переходя к дополнению, видим, что множество принадлежит классу $$\Pi _{n}$$ тогда и только тогда, когда принадлежность ему выражается в предваренной нормальной форме с n группами одноименных кванторов, начинающейся с квантора всеобщности.)

Мы докажем эту теорему лишь отчасти. Во-первых, если множество задается формулой в предваренной нормальной форме с n группами кванторов, то оно принадлежит классу $$\Sigma _{n}$$ (или $$\Pi _{n}$$ в зависимости от того, какой квантор первый) напомним, что k подряд идущих одноименных кванторов можно заменить на один с помощью вычислимой биекции между Nk и N.

Более сложно доказать обратное утверждение. Основную трудность представляет случай n=1. В 1970 году Ю.В.Матиясевич, решая 10-ю проблему Гильберта, показал, что всякое перечислимое множество есть множество неотрицательных значений многочлена от нескольких переменных с целыми коэффициентами при натуральных значениях переменных. А это свойство, очевидно, записывается в виде формулы с кванторной приставкой из кванторов существования. Тем самым случай n=1 был разобран.

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

Посмотрим, однако, что можно извлечь из приведенного нами доказательства арифметичности вычислимых функций. Пусть дано произвольное перечислимое множество. Его можно представить как область определения вычислимой функции, все значения которой равны нулю, и применить описанную нами процедуру. Тогда получится формула, начинающаяся с кванторов существования (существуют числа, кодирующие последовательности значений каждой переменной в смысле $$\beta$$ -кодирования по Геделю). Затем идет квантор всеобщности (по номеру шага работы программы: на каждом шаге переход должен соответствовать программе). Затем идет формула, которая была бы бескванторной, если бы не содержала в себе остатков от деления одного выражения на другое. Но их можно устранить, добавив еще кванторы всеобщности: утверждение типа

$$\forall i [\dots остаток\ от\ деления\ P\ на\ Q \dots ],$$

где P и Q некоторые выражения, содержащие переменные (из определения \beta -кодирования) можно заменить по определению остатка на

$$\forall\ i\ \forall\ u\ \forall\ v\ [(P=uQ+v) \wedge (v < Q)] \Rightarrow [\dots v \dots ].$$

Следовательно, мы можем представить любое перечислимое множество в виде $$\exists \dots \exists \forall \dots \forall$$ -формулы. Тем самым любое множество из класса $$\Sigma _{n}$$ можно представить формулой в предваренной нормальной форме с n+1 группами кванторов, начинающейся с кванторов существования, а любое множество из класса $$\Pi _{n}$$ можно представить формулой с n+1 группами кванторов, начинающейся с квантора всеобщности.