% исправлены опечатки 20.04.2000
\chapter{Арифметичность вычислимых функций}\label{chapt10}

\section[Программы с конечным числом переменных]
        {Программы с конечным числом\\переменных}\label{chapt10-1}

Мы хотим показать, что график всякой вычислимой функции является
        \index{Функция!вычислимая}%
        \index{Вычислимая функция}%
арифметическим множеством, то есть выразим формулой арифметики.
        \index{Множество!арифметическое}%
        \index{Арифметическое множество}%
        \index{Формула!арифметики}%
Для этого удобно перейти от машин~Тьюринга к другой модели,
которую можно условно назвать машинами с конечным числом
        \index{Машина!с конечным числом регистров}%
регистров.

Программа для такой машины использует конечное число переменных,
значениями которых являются натуральные числа. Числа эти могут
быть произвольного размера, так что машина реально имеет память
неограниченного объёма. Программа состоит из нумерованных по порядку
команд. Каждая команда имеет один из следующих видов:
        %
\begin{itemize}
        %
\item \verb|a:=0|
        %
\item \verb|a:=b|
        %
\item \verb|a:=b+1|
        %
\item \verb|a:=b-1|
        %
\item \verb|goto |$\langle$номер$\rangle$

\item \verb|if a=0 then goto |%
    $\langle$номер$1\rangle$\verb| else goto |%
    $\langle$номер$2\rangle$
\item \verb|stop|
        %
\end{itemize}
        %
Для тех, кто не сталкивался с командой \texttt{goto},
поясним, что имеется в виду в команде~\verb|if|: если
значение переменной~\verb|a| равно нулю, то далее исполняется
команда с номером, указанным после~\verb|then| (этот номер\т
конкретное натуральное число, не превосходящее числа команд в
программе); если \verb|a|~не равно нулю, то дальше выполняется
команда с номером, указанным после~\verb|else|.
Команда~\verb|goto| без условия всегда выполняет переход к
команде с указанным в ней номером.

Поскольку мы считаем, что значения переменных\т натуральные
(целые неотрицательные) числа, условимся считать
разность~$0\hm-1$ равной~$0$ (впрочем, это не так важно\т можно
было бы считать это аварией).

Дойдя до команды~\verb|stop|, программа заканчивает работу.

Как и для машин~Тьюринга, полезна некоторая практика
программирования. Для тренировки напишем программу сложения
двух чисел. Она помещает в~\verb|c| сумму чисел, которые были в
переменных~\verb|a| и~\verb|b|. Такая программа на паскале имела бы
вид
        %
\begin{verbatim}
  c:=a;
  {инвариант: ответ=сумма текущих значений c и b}
  while b<>0 do begin
     c:=c+1;
     b:=b-1;
  end;
\end{verbatim}
        %
Имитируя цикл с помощью операторов перехода, получаем программу
для нашей машины:
        %
\begin{verbatim}
 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
\end{verbatim}

Теперь легко понять, как написать программы для вычитания,
умножения (которое реализуется как цикл с повторным сложением),
деления с остатком (как учил ещё Энгельс в забытой ныне книге
\лк Диалектика природы\пк, деление есть сокращённое вычитание),
возведения в степень, проверки простоты, отыскания $n$\д го
простого числа \итп Вообще по сравнению с машинами~Тьюринга
этот язык более привычен и потому легче поверить, что на нём
можно запрограммировать все алгоритмы.

Единственное, чего в нём реально не хватает\т это массивов.
        \index{Массивы, моделирование}%
Но это легко обойти, поскольку есть числа произвольного
размера и нас не интересует число операций (как это
принято в общей теории алгоритмов). Вместо массива битов мы
можем хранить число, двоичной записью которого он является, а
для массивов чисел воспользоваться, скажем, основной теоремой
        \index{Простое число}%
арифметики и хранить
последовательность~$\langle a,b,c,d,e\rangle$ как
число~$2^a3^b5^c7^d11^e$. При этом операции~\verb|a[i]:=b|
и~\verb|b:=a[i]| заменяются на небольшие программы, которые
содержат переменные~\verb|a|, \verb|b|, \verb|i| и ещё несколько
переменных. (Частью этих программ является нахождение простого
числа с заданным порядковым номером.)

Легко определить понятие вычислимой (в этой модели) функции.
Пусть есть программа с двумя переменными~\verb|x| и~\verb|y| (и, возможно,
другими).
Поместим в~\verb|x| некоторое число~$n$, а в
остальные переменные поместим нули. Запустим программу. Если она
не остановится, то вычисляемая ей функция в точке~$n$
не определена. Если
остановится, то содержимое переменной~\verb|y| после остановки и
будет значением функции, вычисляемой нашей программой (в точке~$n$).
Функция называется вычислимой (в этой модели), если существует
        \index{Вычислимость!на машине с конечным числом регистров}%
вычисляющая её программа.

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

\begin{problem}
        %
Покажите, что класс вычислимых функций не изменится, если
исключить из определения команду копирования~\verb|a:=b|.
        %
\end{problem}

Несколько более удивительно, что число переменных можно
ограничить, скажем, сотней\т но и это не так уж странно, если
вспомнить, что мы можем хранить в одной переменной целый массив.

\begin{problem}
        %
Проверьте это.
        %
\end{problem}

\section{Машины~Тьюринга и программы}\label{chapt10-2}

Построенная вычислительная модель не слабее машин~Тьюринга в том
        \index{Машина!Тьюринга}%
        \index{Тьюринга машина}%
смысле, что любую вычислимую на машинах~Тьюринга функцию можно
вычислить и программой с конечным числом переменных.
        \index{Вычислимость!на машине Тьюринга}%
        \index{Программа с конечным числом переменных}%

\begin{theorem}
        \label{turing-to-program}%
Всякая функция, вычислимая на машинах~Тьюринга, может быть вычислена
с помощью программы описанного вида с конечным числом переменных.
        %
\end{theorem}

Следует уточнить, однако, что мы имеем в виду, так как для
машин~Тьюринга исходное данное и результат были двоичными словами,
а для программ\т натуральными числами. Мы отождествляем те и другие
по естественному правилу, при котором слова $\Lambda$ (пустое),
$0$, $1$, $00$, $01$,\ldots соответствуют
числам $0$, $1$, $2$, $3$, $4$\ldots
(чтобы получить из числа слово, прибавим к
нему единицу, переведём в двоичную систему и отбросим единицу в
старшем разряде).

\begin{proof}
        %
Как и раньше, мы приведём лишь приблизительное описание того,
как по машине~Тьюринга строится программа с конечным числом
переменных, вычисляющая ту же функцию. Прежде всего конфигурации
        \index{Конфигурация машины Тьюринга}%
машины~Тьюринга надо закодировать числами. Можно сделать это,
например, поставив в соответствие каждой конфигурации четыре
числа: номер текущего состояния, номер текущего символа (в
ячейке, где стоит головка машины), код содержимого ленты слева
от головки и код содержимого ленты справа от головки.

Чтобы решить, как удобнее кодировать содержимое ленты слева и
справа от головки, заметим, что машина~Тьюринга обращается с
двумя половинами лентами слева и справа от головки как со
        \index{Стек}%
стеками. (Стеком называется структура данных, напоминающая
стопку листов. В неё можно положить лист наверх, взять верхний
лист, а также проверить, есть ли ещё листы.) В самом деле, при
движении головки направо из правого стека берётся верхний
элемент, а в левый стек кладётся; при движении налево\т
наоборот. Стеки легко моделировать с помощью чисел: например,
если в стеке хранятся символы~$0$ и~$1$, то добавление нуля
соответствует операции~$x\hm\mapsto 2x$, добавление единицы\т
операции~$x\hm\mapsto 2x+1$, верхний элемент есть остаток при
делении на~$2$, а удаление верхнего элемента есть деление
на~$2$ (с отбрасыванием остатка). Другими словами, мы воспринимаем
двоичную запись числа как стек, вершина которого находится
справа, у младшего разряда. Точно так же можно использовать
$n$\д ичную систему счисления и представить стек с~$n$ возможными
символами в каждой позиции.

Теперь основной цикл машины~Тьюринга можно записать как
программу, оперирующую с указанными четырьмя числами (символ,
состояние, левый стек и правый стек)\т без особых хитростей.
Но несколько вещей всё\д таки надо иметь в виду.

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

Во\д вторых, напомним, что мы договорились отождествлять
двоичные слова (которые подаются на вход машины~Тьюринга) и их
коды (которые хранятся в переменных нашей программы). Поэтому,
получив код входного слова, надо его разобрать по символам и
положить эти символы один за другим в стек (основания систем
счисления разные, так что просто так переписать это нельзя).
Аналогичные проблемы возникают и при превращении выхода (части
содержимого правого стека) в соответствующее число, но все они
легко преодолимы, и мы не будем вдаваться в подробности.
        %
\end{proof}

Верно и обратное утверждение:
\begin{theorem}
        \label{program-to-turing}%
Всякая функция, вычислимая программой с конечным числом переменных,
вычислима на машине~Тьюринга.
        %
\end{theorem}

\begin{proof}
        %
Нам надо моделировать поведение программы с помощью
машины~Тьюринга. Будем считать, что значения переменных записаны на
ленте (в двоичной системе) и разделены специальным
разделительным символом. Тогда машина может найти любую
переменную, идя от начала ленты и считая разделительные символы,
сделать что\д то с этой переменной и затем вернуться обратно в
начало. (Нет необходимости записывать на ленте номер исполняемой
команды, поскольку команд конечное число и машина может помнить
номер текущей команды как часть своего состояния.) Операции
прибавления и вычитания единицы также легко выполнимы в двоичной
записи (если идти справа налево). Надо только иметь в виду, что
размер числа может увеличиться, и тогда нужно для него
освободить место, сдвинув все символы справа от головки на одну
позицию. (При уменьшении нужно сдвинуть влево.) Ясно, что это
также легко выполнить с помощью машины~Тьюринга.

Если мы записываем числа в двоичной системе, то проблемы с
перекодированием при вводе\д выводе минимальны (надо лишь дописать
нули для значений остальных переменных в начале работы
и встать в
нужное место ленты в конце).
        %
\end{proof}

\section{Арифметичность вычислимых функций}\label{chapt10-3}

Сейчас мы докажем, что функции, вычислимые программами с
        \index{Функция!арифметическая}%
        \index{Арифметическая функция}%
конечным числом переменных, арифметичны, то есть их графики
        \index{Множество!арифметическое}%
        \index{Арифметическое множество}%
являются арифметическими множествами. В этом разделе мы вновь
предполагаем некоторое знакомство читателя с логическими
обозначениями, и будем рассматривать \emph{арифметические
        \index{Формула!арифметики}%
        \index{Арифметическая формула}%
формулы}, содержащие переменные по натуральным числам,
равенство, константы $0$ и $1$, операции сложения и умножения,
логические связки (И, ИЛИ, НЕ) и кванторы \лк для всех\пк\ и \лк
существует\пк. Формально говоря, мы рассматриваем сигнатуру,
содержащую единственный двуместный предикатный символ
(равенство), две константы $0$ и $1$ и два двуместных
функциональных символа (сложение и умножение). Говоря об
истинности таких формул, мы имеем в виду их истинность в
стандартной интерпретации, носителем которой является множество
$\bbN$ натуральных чисел.{\looseness=1\par}

Множество~$A\hm\subset \bbN^k$ называется \emph{арифметическим},
        \index{Множество!арифметическое}%
        \index{Арифметическое множество}%
если существует арифметическая формула~$\alpha$ с
параметрами~$x_1,\dots,x_k$, которая его представляет в
        \index{Формула!представляющая множество}%
        \index{Представление множества формулой}%
следующем смысле: $\langle n_1,\dots,n_k\rangle\hm\in A$ тогда и
только тогда, когда формула~$\alpha$ истинна при значениях
параметров~$x_1\hm=n_1$,\dots,$x_k\hm=n_k$.

\begin{theorem}
        \label{computability-arithmetic}%
График любой функции, вычисляемой программой с конечным
числом переменных, является арифметическим множеством.
        %
\end{theorem}

\begin{proof}
        %
Пусть $f\colon \bbN\hm\to\bbN$\т функция, вычислимая
некоторой программой~$P$ с конечным числом
переменных~$k_1,\dots,k_N$. Будем считать, что входной переменной
является~$k_1$, а выходной\т~$k_2$. Нам нужно написать формулу с двумя
переменными~$x$,~$y$, которая была бы истинна тогда и только
тогда, когда~$y\hm=f(x)$. Состояние программы с конечным числом
переменных полностью описывается значениями переменных и
номером текущей команды (в процессорах соответствующий регистр
        \index{Счётчик команд}%
часто называют program counter, по\д русски счётчик команд). Легко
понять, что соответствие между двумя последовательными
состояниями программы с конечным числом переменных арифметично.
Мы имеем в виду, что можно написать арифметическую формулу
        $$
\mathop{\textrm{Step}}(s_1,\dots,s_N,p,s_1',\dots,s_N',p'),
        $$
с
$2N+2$~переменными,
которая утверждает, что данная программа~$P$ из состояния, где
переменные равны~$s_1,\dots,s_N$, а счётчик команд равен~$p$, за
один шаг переходит в состояние, где переменные
равны~$s_1',\dots,s_n'$, а счётчик команд равен~$p'$. (Договоримся,
что значение~$p'\hm=0$ соответствует остановке программы.)
Такая формула является конъюнкцией отдельных утверждений,
соответствующих каждой строке программы. Пусть, например,
строка~7 программы
имеет вид~\verb|k|$_2$\verb|:=k|$_3$. Тогда в
конъюнкции будет член вида
\begin{multline*}
(p=7)\Rightarrow ((s_1'=s_1)\land (s_2'=s_3) \land (s_3'=s_3)
        \land\dots\\
\ldots\land(s_N'=s_N) \land (p'=8)).
\end{multline*}
Для строки с условными переходами типа

 \verb| 3  if k|$_5$\verb|=0 then goto 17 else goto 33|

\noindent
в формуле будет два конъюнктивных
члена (на два случая перехода)
        $$
((p=3) \land (s_5=0)){\Rightarrow}
                 ((s_1'=s_1)\land\ldots\land(s_N'=s_N)\land (p'=17))
        $$
и
        $$
((p=3) \land (s_5\ne0)){\Rightarrow}
                 ((s_1'=s_1)\land\ldots\land(s_N'=s_N)\land (p'=33)).
        $$
Надо ещё добавить утверждение о том, что при $p=0$ работа
прекращается, то есть что переменные на следующем шаге сохраняют
свои значения, и $p'$ остаётся равным~$0$.

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

Это делается с помощью приёма, традиционно называемого
        \index{$\beta$\д функция Гёделя}%
        \glossary{Гёдель@\Гедель}%
$\beta$\д функцией~Гёделя. Вот что имеется в виду.

\lemma{Лемма 1.} Для любого~$k$ можно найти сколь угодно большое целое
положительное число~$b$, при котором первые $k$~членов
последовательности
        $
b+1, 2b+1, 3b+1,\dots
        $
        \index{Взаимно простые числа}%
попарно взаимно просты.

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

\lemma{Лемма 2.} Для любой
последовательности~$x_0,x_1,\dots,x_n$ натуральных
чисел можно найти такие числа~$a$ и~$b$, что $x_i$~есть остаток от
деления~$a$ на~$b(i\hm+1)\hm+1$.

Доказательство. Согласно предыдущей лемме, делители $b(i\hm+1)\hm+1$~можно
взять взаимно простыми (и сколь угодно большими), остаётся
воспользоваться \лк китайской теоремой об остатках\пк.
        \index{Китайская теорема об остатках}%
Эта теорема утверждает, что если целые положительные числа
$d_1,\dots,d_k$ взаимно просты, то при делении целого $u$ на них
может получиться любой заданный набор остатков. В самом деле,
таких наборов будет~$d_1d_2\dots d_k$ (поскольку при делении
на~$d_i$ возможны остатки от~$0$ до~$d_i-1$). При делении чисел
$u=0,1,\dots,d_1d_2\dots d_k-1$ получаются разные наборы
остатков (если два числа~$u'$ и~$u''$ дают одинаковые остатки,
то их разность делится на все~$d_i$, что невозможно в силу
взаимной простоты). Поэтому чисел столько же, сколько наборов
остатков, и должны появиться все наборы.
Лемма 2 доказана.

Эта лемма показывает, что последовательность
произвольной длины можно закодировать
тремя числами~$a$, $b$ и $n$ (последнее число\т
длина последовательности). Таким образом, условно говоря, можно
заменить \лк формулу\пк
        $$
\exists \langle x_0,\dots,x_n\rangle (\forall i \le n)[\dots x_i \dots]
        $$
(которая на самом деле не является арифметической формулой, так
как содержит квантор по конечным последовательностям) на формулу
       \par\vspace*{-2ex}
{\small
        $$
\exists a\,\exists b\,\exists n\, (\forall i \le n)[\dots
     \text{(остаток от деления $a$ на $b(i+1)+1$)}
     \dots].
        $$
}
Мы будем записывать остаток от деления~$a$ на~$b(i\hm+1)\hm+1$
как~$\beta(a,b,i)$ (отсюда и название \лк бета\д функция\пк).

Возвращаясь к нашей программе~$P$ с конечным числом
переменных~$k_1,\dots,k_N$ и вычисляемой ей функции~$f$,
можно записать утверждение вида~$f(x)\hm=y$ так: существуют такое число
шагов~$n$ и такие числа $a_1,b_1,a_2,b_2,\dots,a_N,b_N,a,b$, что
        %
\begin{itemize}
        %
\item $\beta(a_1,b_1,0),\dots,\beta(a_N,b_N,0)$ есть правильные
    начальные значения переменных (первое равно~$x$, остальные
    равны~$0$); $\beta(a,b,0)$~есть правильное начальное значения
    счёт\-чи\-ка команд, то есть~$1$;
        %
\item для каждого~$i$ от~$0$ до~$n\hm-1$ имеет место
\begin{multline*}
        $$
 \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)),
\end{multline*}
то есть каждый переход соответствует программе;
        %
\item $\beta(a_2,b_2,n)\hm=y$ (значение выходной переменной~$k_2$
в конце вычисления равно~$y$) и $\beta(a,b,n)\hm=0$
(значение счётчика команд в конце вычисления равно~$0$,
что по нашей договорённости соответствует остановке машины).
        %
\end{itemize}
        %
Итак, арифметичность вычислимых (на машинах с конечным
числом переменных) функций доказана.
\end{proof}

Вспоминая
теорему~\ref{turing-to-program}, мы заключаем, что
всякая вычислимая на машине
Тьюринга функция арифметична. Принимая тезис Тьюринга,
        \index{Тьюринга машина}
        \index{Тьюринга тезис}
можно сказать, что график любой вычислимой функции является
арифметическим множеством.

\section{Теоремы~Тарского и~Гёделя}\label{chapt10-4}

Поскольку графики вычислимых функций арифметичны, очевидно, разрешимые
        \index{Множество!разрешимое}%
        \index{Разрешимое множество}%
        \index{Множество!перечислимое}%
        \index{Перечислимое множество}%
        \index{Множество!арифметическое}%
        \index{Арифметическое множество}%
и перечислимые множества тоже будут арифметическими. Тем самым мы можем
оправдать название \лк арифметическая иерархия\пк\ для
        \index{$\Sigma_n$}%
        \index{$\Pi_n$}%
        \index{Арифметическая иерархия}%
классов~$\Sigma_n$ и~$\Pi_n$:

\begin{theorem}
        \label{arithmetic-hiearchy-again}%
При любом~$n$ любое множество из класса~$\Sigma_n$ или~$\Pi_n$
арифметично (есть формула арифметики, выражающая
принадлежность этому множеству).
        %
\end{theorem}

\begin{proof}
        %
После того, как мы доказали арифметичность вычислимых функций,
всё ясно\т множества из классов~$\Sigma_n$ и~$\Pi_n$
получаются навешиванием кванторов на разрешимые множества, а
разрешимое множество арифметично.
        %
\end{proof}

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

\begin{theorem}
        \label{arithmetic-hiearchy-again-2}%
Всякое арифметическое множество лежит в классе~$\Sigma_n$ или
$\Pi_n$~для некоторого~$n$ (и, естественно, для всех б\'ольших~$n$).
        %
\end{theorem}

\begin{proof}
        %
Формулу, задающую арифметическое множество, приведём к
предварённой нормальной форме (вынеся кванторы наружу).
Ясно, что бескванторная часть
задаёт разрешимое множество, поэтому исходное
множество принадлежит какому\д то из классов~$\Sigma_n$ или~$\Pi_n$.

Можно и не использовать предварённой нормальной формы, а
применить индукцию по длине формулы и сослаться на то, что
пересечение, объединение и дополнение, а также проекция не
выводят за пределы арифметической иерархии (объединения всех
классов $\Sigma_n$ и $\Pi_n$).
        %
\end{proof}

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

\begin{theorem}
        \label{tarski-theorem-1}%
        \index{$m$\д сводимость}%
Любое арифметическое множество $m$\д сводится к множеству~$T$.
        %
\end{theorem}

\begin{proof}
        %
Это утверждение почти очевидно. Пусть $A$\т произвольное
арифметическое множество. Пусть $\alpha(x)$\т формула с одной
        \index{Арифметическое множество}%
        \index{Множество!арифметическое}%
переменной, которая выражает принадлежность множеству~$A$. Это
означает, что $\alpha(n)$~истинно при тех и только тех~$n$,
которые принадлежат~$A$. Тогда
        вычислимая
функция
        $
n \hm\mapsto \text{(номер}$
формулы, которая является результатом подстановки
                константы~$n$ в~$\alpha(x))$
$m$\д сводит~$A$ к~$T$.
        %
\end{proof}

\begin{theorem}
        \label{tarski-theorem-2}%
Множество~$T$ не арифметично.
        %
\end{theorem}

\begin{proof}
        %
После проведённой нами подготовки это утверждение очевидно: если
бы $T$~было арифметическим, то оно лежало бы в некотором
конкретном классе~$\Sigma_n$. Поскольку всякое арифметическое
множество сводится к $T$, то по
теореме~\ref{arithmetic-m-reducibility} все арифметические
множества лежали бы в этом классе. Но мы знаем, что множества из
более высоких классов иерархии тоже арифметичны, но в~$\Sigma_n$
не лежат.
        %
\end{proof}

Эта теорема называется \emph{теоремой~Тарского}. Её можно
        \index{Теорема!Тарского}%
        \glossary{Тарский@\Тарский}%
        \index{Тарского теорема}%
прочесть так: множество арифметических истин не арифметично. Или:
понятие арифметической истины невыразимо в арифметике.

\begin{theorem}
        \label{goedel-theorem}%
Множество~$T$ арифметических истин неперечислимо.
        %
\end{theorem}

\begin{proof}
        %
В самом деле, любое перечислимое множество арифметично.
        %
\end{proof}

Это утверждение называется \emph{теоремой~Гёделя о неполноте}.
        \index{Теорема!Гёделя о неполноте}%
        \index{Гёделя теорема}%
Его можно переформулировать так: всякое исчисление, порождающее
        \index{Исчисление}
формулы арифметики (\те алгоритм, перечисляющий некоторое множество
таких формул) либо \emph{неадекватно} (порождает некоторую ложную
        \index{Адекватность}%
        \index{Полнота}%
формулу), либо \emph{неполно} (не порождает некоторой истинной
формулы).

\begin{problem}
        %
Покажите, что для любого $N$ множество всех истинных замкнутых
арифметических формул, содержащих не более $N$ кванторов,
арифметично.
        %
\end{problem}

\begin{problem}
        %
Сформулируйте и докажите аналогичное утверждения для формул
ограниченной кванторной глубины (число вложенных кванторов)
и для формул с ограниченным числом перемен кванторов в
предварённой нормальной форме.
        %
\end{problem}

\section[Прямое доказательство теорем Тарского и~Гё\-де\-ля]
        {Прямое доказательство теорем\\Тарского и~Гё\-де\-ля}\label{chapt10-5}

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

        \index{Теорема!Тарского}%
        \glossary{Тарский@\Тарский}%
        \index{Тарского теорема}%
Начиная доказывать теорему~Тарского, предположим, что множество
номеров всех истинных арифметических формул (без параметров)
арифметично. Пусть $T$\т это множество, а $\tau(x)$\т
соответствующая формула. Перенумеруем также все формулы с одним
параметром~$x$; пусть $F_n(x)$\т формула, имеющая номер~$n$ в
этой нумерации. Рассмотрим формулу с единственным
параметром~$x$, утверждающую, что результат подстановки константы~$x$ в
$x$\д ую формулу с параметром ложен. Эту формулу можно написать
так:
        $$
\exists z ( \lnot\tau(z) \land \Subst(z,x,x) ),
        $$
где $\Subst(p,q,r)$\т формула с тремя параметрами, выражающая
такое свойство: \лк $p$~есть номер (в нумерации всех формул без
параметров) той формулы, которая получится, если в $q$\д ю формулу
с одним параметром подставить константу~$r$ вместо этого
параметра\пк. Записанное в кавычках свойство описывает график
некоторой вычислимой функции (соответствующей простым
синтаксическим действиям и переходу от одной нумерации к другой)
и потому существует выражающая его \hbox{формула}.

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

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

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

Теперь напишем формулу с одним параметром~$x$, которая говорит,
что результат подстановки числа~$x$ вместо параметра в $x$\д ую
формулу с одним параметром не имеет доказательства:
        $$
\lnot\exists z\exists p [\Subst(z,x,x)\land
          \Proof(p,z)]
        $$
Эта формула имеет единственный параметр ($x$); пусть её номер в
нумерации таких формул равен~$N$. Подставим~$N$ вместо
параметра. Получится формула без параметров~$\varphi$. По
построению формула~$\varphi$ истинна, когда результат
подстановки~$N$ в $N$\д ю формулу с одним параметром недоказуем. А
этот результат есть сама формула~$\varphi$, так что она истинна
тогда и только тогда, когда недоказуема. Значит, наше исчисление
либо позволяет доказать ложную формулу~$\varphi$ (если $\varphi$~ложна;
в таком случае его называют неадекватным), либо не
позволяет доказать истинную формулу~$\varphi$.

Заметим, что оба этих доказательства напоминают как построение
        \index{Неподвижная точка}%
        \index{Парадокс лжеца}%
неподвижной точки, так и классический парадокс лжеца:
        %
\begin{center}
        %
\fbox{\hbox{\textsc{утверждение в рамке ложно}}}
        %
\end{center}

\section[Арифметическая иерархия и перемены кванторов]
        {Арифметическая иерархия и \\число перемен кванторов}\label{chapt10-6}

        \index{Арифметическая иерархия}%
        \index{Кванторы}%
Мы установили, что класс арифметических множеств есть
объединение всех классов~$\Sigma_n$ и~$\Pi_n$. Посмотрим
подробнее, как связан номер класса с числом перемен кванторов в
арифметической формуле.

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

\begin{theorem}
        \label{diophantine-arithmetic}
Множество~$A\hm\subset\bbN$ принадлежит классу~$\Sigma_n$~($n\hm\ge 1$)
        \index{Арифметическая иерархия}%
        \index{Множество!арифметическое}%
        \index{Арифметическое множество}%
        \index{$\Sigma_n$}%
тогда и только тогда, когда принадлежность ему выражается
формулой в предварённой нормальной форме, начинающейся с
квантора существования и содержащей $n$~групп одноимённых
кванторов.
        %
\end{theorem}

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

\begin{proof}
        %
Мы докажем эту теорему лишь отчасти. Во\д первых, если множество
задаётся формулой в предварённой нормальной форме с $n$~группами
кванторов, то оно принадлежит
классу~$\Sigma_n$ (или~$\Pi_n$\т в зависимости от того, какой
квантор первый)\т  напомним, что $k$ подряд идущих одноимённых
кванторов можно заменить на один с помощью вычислимой биекции
между $\bbN^k$ и $\bbN$.

Более сложно доказать обратное утверждение. Основную трудность
представляет случай~$n\hm=1$.
        \glossary{Матиясевич@\Матиясевич}%
        \glossary{Гильберт@\Гильберт}%
        \index{Десятая проблема Гильберта}%
В~1970~году Ю.\,В.\,Матиясевич, решая 10\д ю проблему~Гильберта,
показал, что всякое перечислимое множество есть
        \index{Перечислимое множество}%
        \index{Множество!перечислимое}%
множество неотрицательных значений многочлена от нескольких
переменных с целыми коэффициентами при натуральных значениях
переменных. А это свойство, очевидно, записывается в виде
формулы с кванторной приставкой из кванторов существования. Тем
самым случай~$n\hm=1$ был разобран.

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

Посмотрим, однако, что можно извлечь из при\-ве\-дён\-но\-го нами
доказательства арифметичности вычислимых функций. Пусть дано
произвольное перечислимое множество. Его можно представить как
область определения вычислимой функции, все значения которой
равны нулю, и применить описанную нами процедуру. Тогда получится
формула, начинающаяся с кванторов существования (существуют числа,
кодирующие последовательности значений каждой переменной в смысле
        \glossary{Гёдель@\Гедель}%
        \index{$\beta$\д функция Гёделя}%
$\beta$\д кодирования по~Гёделю). Затем идёт квантор всеобщности
(по номеру шага работы программы: на каждом шаге переход должен
соответствовать программе). Затем идёт формула, которая была
бы бескванторной, если бы не содержала в себе остатков от деления
одного выражения на другое. Но их можно устранить, добавив
ещё кванторы всеобщности: утверждение типа
        $$
\forall i\,[\ldots \text{остаток от деления~$P$ на~$Q$}\ldots],
        $$
где~$P$ и~$Q$\т некоторые выражения, содержащие переменные (из
определения $\beta$\д кодирования) можно заменить по определению
остатка на
        $$
\forall i\, \forall u\, \forall v \,
    [(P=uQ+v)\land(v<Q)]\Rightarrow[\ldots v\ldots].
        $$
Следовательно, мы можем представить любое перечислимое множество
в виде $\exists\ldots\exists\forall\ldots\forall$\д формулы. Тем
самым любое множество из класса~$\Sigma_n$ можно представить
формулой в предварённой нормальной форме
с $n\hm+1$~группами кванторов, начинающейся с кванторов
существования, а любое множество из класса~$\Pi_n$ можно
представить формулой с $n\hm+1$~группами кванторов, начинающейся с
квантора всеобщности.
        %
\end{proof}
