\documentclass[12pt]{article} \usepackage{amsmath,amsthm,amssymb} \usepackage{russcorr} %\usepackage[T2A]{fontenc} %\usepackage[koi8-r]{inputenc} %\usepackage[russian]{babel} %\newcommand{\eps}{\varepsilon} \newtheorem{theorem}{Теорема} \newtheorem{lemma}{Лемма} \newtheorem{cor}{Следствие}[theorem] %\newcommand{\poly}{\text{poly}} \newcommand{\prob}{\text{Pr}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} %\newcommand{\bo}{\mathbb{B}} \newcommand{\bo}{\{0,1\}} \newcommand{\boo}{\{0,1\}^*} \newcommand{\ave}{\mathop{\mathbf E}} \newcommand{\disp}{\mathop{\mathbf D}} \let\le=\leqslant \let\leq=\leqslant \let\ge=\geqslant \let\geq=\geqslant \let\preceq=\preccurlyeq \let\succeq=\succcurlyeq \newcommand{\pair}[1]{\langle #1\rangle} %\newenvironment{proof} %{\par$\lhd%\blacktriangleleft %$}{\nolinebreak$\rhd%\blacktriangleright %$} \newcounter{probl} \newenvironment{problem} {\smallskip \par\refstepcounter{probl}{\framebox{\bfseries\arabic{probl}}}}% {\smallskip \par\normalsize} \DeclareMathOperator{\K}{\textit{KS\,}} \DeclareMathOperator{\KS}{\textit{KS\,}} \DeclareMathOperator{\KM}{\textit{KM\,}} \DeclareMathOperator{\KP}{\textit{KP\,}} \DeclareMathOperator{\KD}{\textit{KD\,}} \DeclareMathOperator{\KR}{\textit{KR\,}} \DeclareMathOperator{\KA}{\textit{KA\,}} \DeclareMathOperator{\BB}{\textit{BB\,}} \DeclareMathOperator{\B}{\textit{B\,}} \DeclareMathOperator{\bin}{\mathrm{bin}} \DeclareMathOperator{\poly}{\mathrm{poly}} \newcommand{\bbR}{\mathbb{R}} \newcommand{\bbN}{\mathbb{N}} \newcommand{\bbZ}{\mathbb{Z}} \newcommand{\bbB}{\mathbb{B}} \newcommand{\perems}[2]{#1_1,\dots,#1_{#2}} \newcommand{\perem}[3]{#1_{#2},\dots,#1_{#3}} \newcommand{\ta}{\tilde a} \newcommand{\tb}{\tilde b} \newcommand{\tc}{\tilde c} \newcommand{\td}{\tilde d} \newcommand{\ba}{\bar a} \newcommand{\bb}{\bar b} \newcommand{\bc}{\bar c} \newcommand{\bd}{\bar d} \begin{document} \section{Универсальная машина Тьюринга} Классическая теорема теории алгоритмов утверждает, что существует универсальная вычислимая функция для класса частичных вычислимых функций типа $\boo\to\boo$. Функция $U$, отображающая пары двоичных слов в двоичные слова называется универсальной, если выполнено следующее. Для любой вычислимой частичной функции $f$, аргументами и значениями которой являются двоичные слова, существует $p\in\boo$, для которого $$ f(x)=U(p,x) $$ для всех $x\in\boo$. Двухленточную машину, вычисляющую универсальную функцию (вход $p$ дается на первой ленте, вход $x$ --- на второй) мы будем называть \emph{универсальной} машиной Тьюринга. Нас интересует такой вопрос: сколько времени требуется универсальной машине для вычисления $U(p,x)$ по сравнению со временем вычисления $f(x)$? Оказывается, существуют универсальные машины, для которых замедление линейно: для каждого $p$ время работы универсальной машины на паре $p,x$ не более чем в константу раз больше времени вычисления $f(x)$. При этом константа линейно зависит от длины $p$. Будем в дальнейшем рассматривать только машины Тьюринга, алфавит которых содержит пробел и символы 0,1 (и, возможно, иные символы). Только такие машины могут получать на вход двоичные слова. \begin{theorem}\label{th-universal-machine} Существует двухленточная машина Тьюринга $U$ такая, что для любой одноленточной машины Тьюринга $M$ найдется $p\in\boo$, для которого $$ M(x)=U(p,x) $$ для всех $x\in\boo$. При этом $$ t_U(p,x)=O(|p|t_M(x) + |p||x|) $$ (константы в ``О-большом'' абсолютные). (Время работы $U$ на паре $(p,x)$ по существу ограничено линейной функцией от произведения $|p|$ и времени работы $M$ на входе $x$.) \end{theorem} \begin{proof} Идея построения машины $U$ в следующем. Универсальная машина будет моделировать работу $M$ на входе $x$ шаг за шагом. Слово $p$ будет записью программы машины $M$ в удобном для моделирования формате. Формат записи программ должен позволять моделировать один шаг работы $M$ за время $O(|p|)$. Слагаемое $O(|p||x|)$ необходимо, чтобы преобразовать исходное данное $x$ в удобный для моделирования формат. Пусть $M$ --- некоторая одноленточная машина Тьюринга. Закодируем ее программу нулями и единицами следующим образом. Пусть $\{\perems al\}$ алфавит машины $M$, причем символы перенумерованы так, что $a_1$ --- это пробел, $a_2=0$ и $a_3=1$. Пусть $\{\perems qk\}$ --- множество состояний, причем $q_1$ --- начальное состояние. Каждая команда машины $q_ia_j\to q_sa_t\Delta$ является словом в алфавите, состоящем из символов $\perems am$, $\perems qk$, $\to$, $R$, $L$, $S$. Мы хотим представлять команды словами в фиксированном алфавите. Для этого договоримся записывать $q_i$ и $a_j$ последовательностями q(двоичная запись $i$) и a(двоичная запись $j$), соответственно. Тогда каждая команда станет словом длины $O(\log k+\log l)$ в восьмибуквенном алфавите $\{0,1,a,q,\to,R,L,S\}$. Закодируем буквы этого алфавита трехбитовыми строками, например, в лексикографическом порядке. Двоичные слова, в которые при выбранном кодировании перейдут $q_i$, $a_j$, и символы $\to,R,L,S$ будем называть их кодами и обозначать $\overline{q_i}$, $\overline{a_j}$ и т.д. %Например, $\overline{a_0}=010000$, %$\overline{q_1}=011001$ и т.д. Заменив в записи команды каждый символ на его код, мы получим двоичное слово, называемое кодом команды. Перепишем коды всех команд подряд в лексикографическом порядке и получим двоичное слово $p$, кодирующее программу машины $M$ в удобном формате. Длина слова $p$ имеет порядок $kl(\log k+\log l)$, поскольку количество команд равно $kl$ и на запись одной команды нужно $O(\log k+\log l)$ битов. Первая лента машины $U$ будет содержать последовательность кодов всех букв, написанных на ленте моделируемой одноленточной машины $M$ (в том же порядке), причем головка будет обозревать первый символ кода буквы, обозреваемой машиной $M$. На второй ленте будет записан код программы $p$, а затем код состояния $q_i$ машины $M$. Как смоделировать один шаг машины $M$? Нужно скопировать на вторую ленту код обозреваемой буквы $a_j$. Затем просмотрев программу $p$, нужно найти вхождение последовательности $\overline{q_ia_j\to}$. Для этого понадобится $O(kl(\log k+\log l))=O(|p|)$ шагов (мы просматриваем все $kl$ вхождений кода символа $\to$, и для каждого вхождения сравниваем слово $\overline{q_ia_j}$ со словом, написанным слева от этого вхождения). Когда мы найдем вхождение последовательности $\overline{q_ia_j\to}$, надо заменить на второй ленте $\overline{q_i}$ на последовательность $\overline{q_sa_t\Delta}$, стоящую справа от символа $\to$. Затем заменяем код $a_j$ на код $a_s$ на первой ленте. Чтобы для этого не понадобилось сдвигать все содержимое ленты, нужно, чтобы коды всех символов имели одну длину (равную $1+\lceil\log l\rceil$). Затем перемещаем головку на первой ленте влево или вправо, в зависимости от $\Delta$ и стираем код $\overline{a_t\Delta}$ со второй ленты. Моделирование одного шага закончено. Оно выполняется за $O(|p|)$ шагов. Осталось только заметить, что преобразование исходного данного $x$ в его код $\overline{x}$ можно выполнить за время $O(|x|\log l)=O(|p||x|)$ с помощью второй ленты: каждый бит слова $x$ надо заменить на код нуля или код единицы. Обратное преобразование кода результата работы $y$ в двоичное слово также требует времени $O(|y|\log l)$. Поскольку длина $y$ ограничена максимумом из длины $x$ и времени работы $M$ на $x$, слагаемое $O(\log l|y|)$ поглощается слагаемыми $O(|p||x|)$ и $O(|p|t_M(x))$. \end{proof} \section{Теоремы о иерархии} Пусть имеется некоторая функция $t:\N\to\N$. Существует ли язык $A\subset\{0,1\}^*$, который не распознается никакой одноленточной машиной Тьюринга за время $t(n)$? (Напомним, что машина $M$ распознает язык $A$ за время $t(n)$, если на любом входе $x\in\{0,1\}^*$ она останавливается, проработав не более $t(|x|)$ шагов и напечатав 0 или 1 в зависимости от того, принадлежит ли $x$ к $A$ или нет.) Разумеется, такой язык существует для любой функции $t(n)$: можно взять в качестве $A$ любой неразрешимый язык, то есть, язык для которого вообще нет распознающей машины Тьюринга. Для понимания дальнейшего полезно вспомнить, как доказывается существование неразрешимого языка. Вот наиболее простое доказательство этого факта. Перенумеруем все одноленточные машины Тьюринга, алфавит которых содержит символы $0,1$ и пробел: $$ M_0,M_1,\dots,M_n,\dots. $$ Каждая машина должна встречаться в этой последовательности хотя бы однажды, но может встречаться и много раз. Рассмотрим язык \begin{equation} \label{la} A=\{1^n\mid M_n(1^n)=0\}. \end{equation} Через $1^n$ здесь обозначено слово, состоящее из $n$ единиц, фактически $A$ это множество слов в алфавите $\{1\}$. Докажем, что какую бы нумерацию машин Тьюринга мы ни выбрали, построенный язык $A$ неразрешим. Действительно, пусть машина с номером $k$ разрешает $A$, то есть, $M_k(x)\in \{0,1\}$ для любого $x$ и при этом $$ M_k(x)=1\Leftrightarrow x\in A. $$ По построению $A$ из этого следует, что для любого $n$ $$ M_k(1^n)=1 \Leftrightarrow M_n(1^n)=0. $$ При $n$ равном $k$ мы получаем противоречие, которое доказывает, что язык $A$ неразрешим. Этот метод доказательства принято называть диагональным по следующей причине. Расположим результаты работы всевозможных одноленточных машин Тьюринга на всевозможных входах вида $1^n$ в бесконечную таблицу, строки которой нумеруются номерами машин, а столбцы их входами вида $1^n$. На диагонали полученной матрицы стоит последовательность $M_n(1^n)$. Более содержательный вопрос --- для каких функций $t(n)$ существует \emph{разрешимый} язык, который невозможно распознать за время $t(n)$? Оказывается, такой язык существует для всех вычислимых функций $t(n)$ и его можно построить с помощью того же метода. А именно, рассмотрим язык \begin{equation} \label{lb} \begin{split} \{1^n\mid & \text{ машина }M_n \text{ останавливается на входе }1^n\\ &\text{ с результатом 0 за } t(n) \text{ шагов}\}. \end{split} \end{equation} \begin{theorem} \label{th-diag} (1) Какова бы ни была выбранная нумерация одноленточных машин Тьюринга, не существует одноленточной машины Тьюринга, разрешающей язык \eqref{lb} за время $t(n)$. (2) Если выбранная нумерация машин Тьюринга вычислима, то язык \eqref{lb} разрешим. (Вычислимость нумерации означает существование алгоритма, который по любому $n$ находит программу машины $M_n$.) \end{theorem} \begin{proof} (1) Допустим, машина Тьюринга с номером $k$ разрешает язык \eqref{lb} за время $t(n)$. Тогда $$ M_k(1^n)=1 \Leftrightarrow (M_n(1^n)=0 \text{ за время } t(n)). $$ При $n$ равном $k$ это означает, что $$ M_k(1^k)=1 \Leftrightarrow (M_k(1^k)=0 \text{ за время } t(k)). $$ Но поскольку машина $M_k$ на входе $1^k$ заведомо остановится за время $t(k)$, мы получаем противоречие: $$ M_k(1^k)=1 \Leftrightarrow M_k(1^k)=0. $$ (2) Алгоритм разрешения \eqref{lb} заключается в моделировании: по данному натуральному $n$ мы находим программу машины $M_n$ (по условию это возможно --- у нас есть алгоритм нахождения программы $M_n$ по $n$) и затем применяем ее шаг за шагом к исходному данному $1^n$. Мы обрываем моделирование после шага номер $t(n)$ и выдаем 0, если машина $M_n$ не остановилась за это время. Иначе мы выдаем 1, если машина $M_n$ остановилась с результатом 0 и выдаем 0 во всех остальных случаях. В этом рассуждении важно, что функция $t(n)$ вычислима, иначе мы не знали бы когда нам можно оборвать моделирование. Кстати, по этой же причине не проходит попытка разрешить язык $A$ с помощью моделирования --- мы можем начать пошаговое моделирование работы $M_n$ на входе $1^n$, но мы не знаем, когда его закончить. \end{proof} \begin{problem} Пусть фиксирована вычислимая нумерация одноленточных машин Тьюринга. Приведите пример невычислимой функции $t(n)$, для которой язык \eqref{lb} неразрешим. \end{problem} Теперь у нас все готово для доказательства теорем о иерархии. В наиболее простой форме теорема о иерархии говорит, что для данных двух функций $t(n)\ll t'(n)$ существует язык, распознаваемый за время $t'(n)$, но не распознаваемый за время $t(n)$ (на одноленточных машинах Тьюринга). В качестве такого языка можно взять диагональный язык из теоремы~\ref{th-diag}. Вспомним, как доказывалась разрешимость языка \eqref{lb}. Мы сначала вычисляли значение $t(n)$, а затем моделировали $t(n)$ шагов работы машины $M_n$ на входе $1^n$. Чтобы доказать теорему о ирерархии нам нужно подсчитать, сколько шагов на это требуется. Самый простой способ подсчета такой: сначала оценить, сколько шагов требуется многоленточной машине Тьюринга, а потом использовать моделирование многоленточной машины с помощью одноленточной с квадратичным замедлением. На многоленточной машине можно организовать вычисление так. (1) Сначала скопировать исходное данное $1^n$ на вторую ленту (мы предполагаем, что изначально оно записано на первой ленте) и вычислить значение $t(n)$ в унарной записи, то есть $1^{t(n)}$, результат записать на вторую ленту. (2) Затем скопировать $1^n$ на третью ленту и преобразовать его в программу машины $M_n$. %(3) Затем скопировать $1^n$ на четвертую ленту и преобразовать его %код исходного данного для машины $M_n$. (3) Затем смоделировать $t(n)$ шагов работы $M$ на входе $1^{t(n)}$. После моделирования каждого шага уменьшать на 1 счетчик количества шагов, записанный не второй ленте. Общее время работы этой многоленточной машины будет равно (время вычисления $1^{t(n)})+$ (время преобразования $1^n$ в программу $M_n)+ %(время преобразования $1^n$ в код %исходного данного для программы машины $M_n)+ t(n)\times(1+$ (время моделирования одного шага)). Первое слагаемое зависит от трудности вычисления $t(n)$, а остальные от выбора способа записи программ машин и выбора нумерации машин Тьюринга. Обычно теорема о ирерархии применяется только к просто вычислимым функциям $t(n)$ (полиномам, экспонентам и т.д.). Мы будем предполагать, что существует многоленточная машина Тьюринга, вычисляющая $1^{t(n)}$ по $1^n$ за $O(t(n)+n)$ шагов. Такие функции называются \emph{конструируемыми по времени}. Чтобы последнее слагаемое было мало нужно, чтобы номер машины был существенно больше длины записи ее программы. Для этого годится самая, например, следующая нумерация. Сопоставим каждой одноленточной машине $M$ двоичное слово $p$ (двоичный код ее программы), как в теореме~\ref{th-universal-machine}. Номером машины $M$ будет натуральное число, двоичная запись которого равна $1p$ (мы приписываем слева 1, поскольку двоичные записи натуральных чисел начинаются на 1). Если двоичная запись натурального числа $n$ не имеет такого вида, то будем считать $n$ номером тривиальной машины, которая ничего не делает (стоит на одном месте). По двоичному слову $p$ на двухленточной машине за время $O(|p|)=O(\log n)$ можно узнать, является ли оно кодом какой-нибудь программы машины Тьюринга. Для этого, как это делалось при моделировании (см. доказательство теоремы~\ref{th-universal-machine}), надо проверить, что оно состоит из кодов команд, записанных в лексикографическом порядке. Если $p$ не является кодом программы никакой машины, то мы не выполняем моделирования, а останавливаемся сразу с результатом 0. Итак, первое слагаемое по условию есть $O(t(n)+n)$ шагов. Второе слагаемое (время преобразования $n$ из унарной в двоичную запись и последующая проверка, является ли слово $p$ программой некоторой машины) есть $O(n)$ (преобразование) плюс $O(|p|)=O(\log n)$ (проверка). Наконец, последнее слагаемое, как доказано в теореме ~\ref{th-universal-machine}, есть $O(t(n)|p|)=O(t(n)\log n)$. %Оно поглощает все предыдущие слагаемые. %Как мы увидим, при естественном способе нумерации машин %по слову $1^n$ можно за время $O(n)$ записать %программу машины $M_n$ в таком формате, чтобы %время моделирования одного шага работы $M_n$ обходилось в $O(\log n)$ шагов. %Таким образом мы получим такую оценку времени распознавания языка \eqref{lb}: Кроме того, нужно еще учесть следующее обстоятельство. Исходное данное $1^n$ записано на ленте не в том формате, который требуется для начала пошагового моделирования. Необходимо заменить каждую из $n$ единиц на ее код. Для этого достаточно времени $O(n\log n)$. %Это слагаемое также поглощается слагаемым %$O(t(n)\log n)$, так как по условию $t(n)\ge n$. \begin{theorem}\label{th-upperbound} Существует нумерация одноленточных машин Тьюринга такая, что для любой конструируемой функции $t(n)\ge n$ язык \eqref{lb} можно распознать за время $O((t(n)\log n)^2)$ на одноленточной машине Тьюринга. \end{theorem} %\begin{proof} %Рассмотрим следующий способ нумерации машин --- каждой %машине сопоставим двоичное слово $p$, которое %естественным образом кодирует программу машины. %Номером машины будет натуральное число, двоичная запись которого %равна $1p$ (мы приписываем слева 1, поскольку %двоичные записи натуральных чисел начинаются на 1). % %Код программы данной машины $M$ строится следующим образом. %Пусть $\{\perems am\}$ алфавит машины $M$, %причем символы перенумерованы так, что $a_1$ --- это пробел, %$a_2=0$ и %$a_3=1$. Пусть $\{\perems qk\}$ --- множество состояний, причем %$q_1$ --- начальное состояние. %Каждая команда машины $q_ia_j\to q_sa_t\Delta$ является словом %в алфавите, состоящем из символов $\perems am$, $\perems qk$, $\to$, $R$, %$L$, $S$. %Мы хотим представлять команды словами в фиксированном %алфавите. Для этого договоримся записывать %$q_i$ и $a_j$ последовательностями q(двоичная запись $i$) и %a(двоичная запись $i$), соответственно. %Тогда каждая команда станет словом длины $O(\log k+\log l)$ %в восьмибуквенном алфавите %$\{a,q,0,1,\to,R,L,S\}$. %Выберем произвольное кодирование букв этого алфавита %трехбитовыми строками. Двоичные слова, в которые %при выбранном кодировании перейдут %$q_i$, $a_j$, и символы $\to,R,L,S$ будем называть их кодами и %обозначать %$\overline{q_i}$, $\overline{a_j}$ и т.д. %Заменив в записи команды каждый символ на его код, мы получим %двоичное слово, называемое кодом команды. %Перепишем коды всех команд подряд в лексикографическом порядке %и получим бинарное слово $p$, кодирующее программу машины $M$ в удобном для %моделирования формате. Длина слова $p$ имеет порядок %$kl(\log k+\log l)$, поскольку количество команд равно $kl$ %и на запись одной команды нужно %$O(\log k+\log l)$ битов. %Натуральные числа, двоичные записи которых не имеют вида %$1p$, где $p$ код программы некоторой машины, будем %считать номерами тривиальной машины, которая %ничего не делает (стоит на одном месте). % %Первая лента %моделирующей многоленточной машины будет содержать %последовательность кодов всех букв, написанных на ленте %моделируемой одноленточной машины $M$ (в том же порядке), причем головка будет %обозревать первый символ кода буквы, обозреваемой машиной $M$. %На второй ленте будет записан код программы $p$. %На третьей ленте будет записан код состояния $q_i$ машины $M$. %Как смоделировать один шаг машины $M$? %Нужно скопировать на третью ленту код обозреваемой буквы $a_j$. %Затем просмотрев всю программу $p$, нужно найти %вхождение последовательности $\overline{q_ia_j\to}$. %Для этого понадобится $O(kl(\log k+\log l))=O(|p|)$ шагов %(мы просматриваем все $kl$ вхождений кода символа $\to$, %и для каждого вхождения сравниваем слово $\overline{q_ia_j}$ %со словом, написанным слева от этого вхождения). Когда мы найдем %вхождение последовательности $\overline{q_ia_j\to}$, надо переписать %на третью ленту последовательность %$\overline{q_sa_t\Delta}$, стоящую справа %от символа $\to$, и заменяем код $a_j$ на код $a_s$ на первой ленте. %Затем %перемещаем головку на первой ленте влево или вправо, %в зависимости от $\Delta$ и %стираем код $\overline{a_t\Delta}$ с третьей ленты. %Моделирование одного шага закончено. %Оно выполняется за $O(|p|)=O(\log n)$ шагов, где %$n$ --- это номер моделируемой машины $M$. % %Осталось только заметить, что по слову $1^n$ можно %найти его двоичную запись (а значит и код программы $p$) за время %$O(n)$ на двухленточной машине. %Слагаемое $O(n)$ поглощается слагаемыми %$O(t(n)\log n)$. %По двоичному слову $p$ на двухленточной машине %за время $O(|p|)=O(\log n)$ можно узнать, %является ли оно кодом какой-нибудь программы машины Тьюринга. %Для этого, как это делалось при моделировании, %надо проверить, что оно состоит из кодов команд, %записанных в лексикографическом порядке. %Если $p$ не является кодом программы никакой машины, %то мы не выполняем моделирования, а останавливаемся сразу %с результатом 0. %\end{proof} \begin{problem}~\label{p1} Докажите, что функции $n$ и $2^n$ являются конструируемыми. Докажите, что для произвольного натурального $с$ функция $t(n)\equiv c$ конструируема. \end{problem} \begin{problem}~\label{p2} Докажите, что сумма и произведение конструируемых функций конструируемы. Докажите, что если $t(n)$ конструируемая функция, то и функция $2^{t(n)}$ конструируема. Следовательно, все полиномы с натуральными коэффициентами, а также экспоненты от полиномов конструируемы. \end{problem} \begin{problem} Докажите, что в формулировке теоремы требование конструируемости функции $t$ можно ослабить. Достаточно потребовать, чтобы функция $1^n\to 1^{t(n)}$ вычислялась на многоленточной машине Тьюринга за время $O(t(n)\log n)$. \end{problem} Замечание. Для построения языка, распознаваемого за время $O((t(n)\log n)^2)$, но не распознаваемого за время $t(n)$ (для конструируемой функции $t(n)$) можно и не прибегать к нумерации машин Тьюринга. %Обозначим через $\tilde x$ слово, полученное из слова %$x$ удвоением всех его букв (например, $\widetilde{011}=001111$). Рассмотрим следующий язык \begin{align*} \{1^{2^{|p|}}0p \mid &\ p\text{ есть двоичный код программы машины Тьюринга,}\\ &\text{ останавливающейся на входе }1^{2^{|p|}}0p \\ &\text{ за } t(2^{|p|}+1+|p|) \text{ шагов с результатом }0\}. \end{align*} Этот язык отличается от языка \eqref{lb} тем, что программа указывается явно, а не своим номером, но при этом исходное данное искусственно удлиняется, чтобы один шаг машины $M$ можно было смоделировать за время $O(\log n)$. Прежде чем начинать моделирование надо проверить, что вход имеет вид $1^{2^{|x|}}0x$ для некоторого слова $x$, то есть, понадобится опять переводить число $2^{|x|}$ из унарной записи в двоичную. Так что доказательство того, что этот язык можно распознать за время $O((t(n)\log n)^2)$ не будет проще. Теорема~\ref{th-diag} для этого языка доказывается точно так же, как и раньше. Теорему~\ref{th-upperbound} можно усилить, избавившись от возведения $t(n)$ в квадрат. Точнее, для той же самой нумерации машин можно доказать, что язык \eqref{lb} распознается за время $O(t(n)\log t(n)+n^2)$ на одноленточной машине Тьюринга (для просто вычислимых функций $t(n)$). Для этого нужно записывать счетчик числа шагов в двоичной форме, а не в унарной. При этом вычитание единицы из счетчика уже будет выполняться не за 1 шаг, как раньше, а за $O(\log t(n))$ шагов. В результате многоленточная машина будет распознавать \eqref{lb} за время $O(t(n)\log t(n))$. Это больше, чем было раньше, но зато теперь содержимое всех лент, кроме первой (на которой записано содержимое ленты моделируемой машины) занимает мало места. А именно, на всех лентах, кроме первой используется не более $O(\log t(n))$ ячеек. Это дает возможность сэкономить на переходе от многоленточной машины к одноленточной. А именно, при моделировании многоленточной машины содержимое всех лент кроме первой, надо сдвигать вслед за положением головки на первой ленте. Тогда моделирование одного шага многоленточной машины и уменьшение счечтика обойдется $O(\log t(n))$ шагов. Кроме этого надо скопировать $1^n$ на ``вторую дорожку'' и разложить $n$ в двоичную запись. На это уйдет $O(n^2)$ шагов. Затем надо проверить, является ли полученное слово $p$ программой машины Тьюринга (в $O(|p|)=O(\log n)$ шагов). Наконец, надо в исходном данном заменить каждую единицу на ее код (в $O(n^2)$ шагов). Итак, мы установили следующий факт. Назовем функцию $t(n)$ доступной, если функция $1^n\mapsto (\text{двоичная запись }t(n))$ вычислима за время $O(t(n)\log t(n)+n^2)$ на одноленточной машине Тьюринга, \begin{theorem}\label{th-upperbound-improved} Для некоторой нумерации одноленточных машин Тьюринга для любой доступной функции $t(n)\ge n$ язык \eqref{lb} можно распознать за время $O(t(n)\log t(n)+n^2)$ на одноленточной машине Тьюринга. \end{theorem} \begin{problem} Докажите, что класс доступных функций удовлетворяет утверждениям задач~\ref{p1} и~\ref{p2}. \end{problem} Обычно требуется доказать, что существует язык не распознаваемый за время $t(n)$ ни для одной функции $t(n)$ из некоторого семейства функций и распознаваемый за время $O(t'(n))$ для некоторой функции $t'(n)$, значительно большей всех функций из этого семейства. Например, если мы хотим доказать, что данный язык не принадлежит классу P, то в качестве семейства можно взять класс всех полиномов с натуральными коэффициентами (можно ограничиться классом всех полиномов вида $n^k+k$, где $k$ --- натуральное число, поскольку любой полином ограничен сверху некоторым полиномом такого вида). Другой пример --- если мы хотим доказать, что данный язык нельзя разрешить за время $O(2^n)$, в качестве класса семейства можно взять класс всех функций вида $k2^{n}$, $k=0,1,2,\dots$. Утверждения такого сорта можно доказывать, применяя теорему~\ref{th-upperbound-improved} к подходящей функции $t(n)$. \begin{problem} ~\label{p6} Докажите, что для любой доступной функции $t(n)>n$ существует язык, распознаваемый за время $O(t(n)\log t(n)+n^2)$, но не распознаваемый за время $o(t(n))$ (на одноленточных машинах Тьюринга). (Указание. Этим требованиям удовлетворяет язык из теоремы~\ref{th-upperbound-improved}. Любую машину, распознающую его за время $o(t(n))$ можно преобразовать в машину, распознающую его за время $t(n)$. Заметьте, что исходная машина на коротких входах может работать более $t(n)$ шагов.) \end{problem} \begin{problem} Докажите, что существет язык, распознаваемый за время $O(2^n)$ и не принадлежащий классу P. (Указание. Примените задачу~\ref{p6} к функции $2^{n/2}$.) \end{problem} \begin{problem} \label{p7} Докажите, что для любой доступной функции $t(n)>n$ существует язык, распознаваемый за время $O(t(n)\log^2 t(n)+n^2)$, но не распознаваемый за время $O(t(n))$ (на одноленточных машинах Тьюринга). (Указание. Примените задачу~\ref{p6} к функции $t(n)\log t(n)$.) \end{problem} \begin{problem} Докажите, что для каждого натурального $c\ge2$ существует язык, распознаваемый за время $O(n^{c}\log^2 n)$ на одноленточной машине Тьюринга, но не распознаваемый за время $O(n^c)$ на одноленточных машинах Тьюринга. (Указание. Примените задачу~\ref{p7} к функци $n^{c}$.) \end{problem} %Теми же рассуждениями, что и в доказательстве теоремы~\ref{th-upperbound-improved}, %устанавливается следущая теорема иерархии для семейства %функций. % %\begin{theorem}\label{th-upperbound-family-improved} %Для некоторй нумерации машин Тьюринга выполнено следующее. %Пусть $t_0(n),t_1(n),\dots$ возрастающая последовательность %функций (то есть, $t_{m+1}(n)\ge t_{m}(n)$ для всех $n,m$) такая, %что функция %$1^k01^l\mapsto (\text{двоичная запись }t_l(k))$ %вычислима за время %$O(t_{n}(n)\log t_{n}(n))$ на одноленточной машине Тьюринга. %Тогда язык $C$ %разрешим за время %$O(t_n(n)\log t_n(n))$ на одноленточной машине Тьюринга. %\end{theorem} % %\begin{cor} %Существует язык, распознаваемый за время $O(n^22^n)$ на одноленточной машине %Тьюринга, но не распознаваемый за время $O(2^n)$ на одноленточных машинах %Тьюринга. %\end{cor} %\begin{proof} %Применим теорему~\ref{th-upperbound-family-improved} %к последовательности $t_m(n)=m2^n$. %Функция %$1^k01^l\mapsto (\text{двоичная запись }l2^k)$ %вычислима за время $\poly(k,l)$, поэтому условия теоремы выполнены. %\end{proof} % %\begin{problem} %Докажите, что для каждого натурального $c\ge1$ существует язык, %распознаваемый за время $O(n^{c}\log^2 n)$ %на одноленточной машине %Тьюринга, но не распознаваемый за время $O(n^c)$ на одноленточных машинах %Тьюринга. %(Указание. Примените теорему~\ref{th-upperbound-family-improved} %к последовательности $\lceil\log m\rceil n^c$.) %\end{problem} % %\begin{problem} %Пусть %$t(n)\ge n$ %и %$1^n\mapsto (\text{двоичная запись }t(n))$ %вычислима за время %$O(t(n)\log t(n))$ на одноленточной машине Тьюринга. %Докажите, что существует %язык, распознаваемый за время %$O(t(n)\log t(n))$, но распознаваемый за время $o(t(n))$ %на одноленточных машинах Тьюринга. %(Указание. Этим требованиям удовлетворяет %язык \eqref{lb}: любую машину, распознающую %его за время $o(t(n))$ можно преобразовать в %машину, распознающую его за время $t(n)$. Заметьте, что исходная машина %на коротких входах может работать более $t(n)$ шагов.) %Рассмотрим ту же кодировку одноленточных машин, как %в теореме~\ref{th-upperbound} и рассмотрим %двухленточную машину $U$, которая имея на одной ленте %код программы $p$ машины $M$, а на другой %исходное данное $x$ моделирует работу $M$ на $x$ %с замедлением в $O(|p|)$ раз. %Язык $\{1^n01^m\mid U(p,1^n01^m)=0 \text{ за $t(n+m+1)$ шагов}\}$ %(где $n$ есть номер машины с программой $p$) удовлетворяет %обоим требованиям. %\end{problem} % %Пусть $t_0(n),t_1(n),\dots$ последовательность функций %натурального аргумента с натуральными значениями такая, что %функция двух аргументов $m,n\mapsto t_m(n)$ вычислима. %Рассмотрим язык %\begin{align*} %C=\{1^n01^m \mid &\text{машина }M_n \text{ останавливается на входе }1^n01^m\\ %&\text{ с результатом 0 за } t_m(n+1+m) \text{ шагов}\}. %\end{align*} %(Обратите внимание на то, что $n+1+m$ есть длина слова %$1^n01^m$.) %Для языка $C$ выполнен следующий аналог предыдущей теоремы: % %\begin{theorem} %(1) Какова бы ни была выбранная %нумерация машин Тьюринга, ни для одного $l\in\N$ не существует машины Тьюринга, %разрешающей язык $C$ за время $t_l(n)$. %(2) Если выбранная нумерация машин Тьюринга вычислима, %то язык $C$ разрешим. %\end{theorem} %\begin{proof} %Доказательство почти буквально повторяет %доказательство теоремы~\ref{th-diag}. % %(1) Допустим, машина Тьюринга с номером $k$ разрешает \eqref{lb} за время $t_l(n)$ (для некоторого $l\in\N$). %Тогда %$$ %M_k(1^n01^m)=1 \Leftrightarrow (M_n(1^n01^m)=0 \text{ за время } t_m(n+1+m)). %$$ %При $n,m$ равных $k,l$ это означает, что %$$ %M_k(1^k01^l)=1 \Leftrightarrow (M_k(1^k01^l)=0 \text{ за время } t_l(k+1+l). %$$ %Но поскольку машина $M_k$ на входе $1^k01^l$ заведомо остановится за время $t_l(k+1+l)$, %мы получаем противоречие: %$$ %M_k(1^k01^l)=1 \Leftrightarrow M_k(1^k01^l)=0. %$$ % %(2) Алгоритм разрешения $C$ заключается в моделировании: %по данному слову $1^n01^m$ мы находим программу машины $M_n$ %затем моделируем $t_m(n+1+m)$ шагов ее работы на входе $1^n01^m$. %В качестве результата, мы выдаем 1, если %машина $M_n$ остановилась с результатом 0 за это время, и выдаем 0 %во всех остальных случаях. %\end{proof} % % \section{Нижние оценки времени распознавания других языков} Трудность распознавания других языков обычно доказывают с помощью свед\'ений к языкам \eqref{la} и \eqref{lb}. Вот как это делается. Докажем, например, неразрешимость классической проблемы применимости машины Тьюринга, то есть неразрешимость языка $$ H=\{1^n0x \mid x\in\boo,\ M_n \text{ останавливается на входе }x\}. $$ (Мы предполагаем, что нумерация машин вычислима.) Для доказательства неразрешимости языка $H$ мы сведем к проблеме его разрешения проблему разрешения языка \eqref{la}. Для этого рассмотрим следующее преобразование на машинах Тьюринга: преобразуем машину $M$ в машину $M'$, которая работает так же, как и $M$, за одним исключением: машина $M'$ останавливается только если $M$ останавливается с результатом 0. То есть, машина $M'$ останавливается на входе $x$ тогда и только тогда, когда $M(x)=0$. Существует вычислимое отображение $k\mapsto k'$ такое, что $(M_k)'=M_{k'}$. Действительно, по натуральному числу $k$ мы можем найти программу машины $M_k$, преобразовать ее в программу машины $(M_k)'$ и затем найти некоторый номер получившейся программы в данной нумерации машин. Слово $1^n$ принадлежит языку \eqref{la} тогда и только тогда, когда машина $(M_n)'$ останавливается на входе $1^n$, то есть слово $1^{n'}01^{n'}$ принадлежит языку $H$. Значит, если бы существовал алгоритм, распознающий принадлежность данного слова к $H$, то применив его к слову $1^{n'}01^{n'}$, мы получили бы ответ на вопрос, принадлежит ли слово $1^n$ к языку \eqref{la}. %Из неразрешимости языка \eqref{la} следует неразрешимость языка %$$ %A'=\{1^n0x \mid x\in\boo,\ M_n(x)=0\}. %$$ %Действительно, если бы существовал алгоритм, который по слову %определял, принадлежит оно языку $A'$, %то, применив этот алгоритм к слову %$1^n01^n$, мы определили бы, принадлежит ли слово $1^n$ %диагональному языку \eqref{la}. %Аналогичным образом можно доказать неразрешимость классической проблемы %остановки машины Тьюринга, то есть неразрешимость языка %$$ %A''=\{1^n0x \mid x\in\boo,\ M_n \text{ останавливается на входе }x\}. %$$ %(Мы предполагаем, что нумерация машин вычислима.) % %Для доказательства неразрешимости языка $A''$ мы сведем к проблеме его разрешения %проблему разрешения языка $A'$. Для этого %рассмотрим следующее преобразование на машинах Тьюринга: %преобразуем машину $M$ в машину $M'$, которая работает так же, как и $M$, %за одним исключением: машина $M'$ останавливается только если $M$ останавливается %с результатом 0. %То есть, машина $M'$ останавливается на входе $x$ тогда и только тогда, когда $M(x)=0$. %Существует %вычислимое отображение $k\mapsto k'$ такое, что %$(M_k)'=M_{k'}$. %Действительно, по натуральному числу %$k$ мы можем найти программу машины $M_k$, преобразовать ее в программу %машины %$(M_k)'$ и затем найти некоторый %номер получившейся программы в данной нумерации машин. % %Слово $1^n0x$ принадлежит $A''$ тогда и только тогда, когда %машина $(M_n)'$ останавливается на входе $x$, то есть слово %$1^{n'}0x$ принадлежит языку $A''$. Значит, если бы существовал алгоритм, %распознающий принадлежность данного слова к $A''$, то %применив его к слову $1^{n'}0x$, мы получили бы ответ на вопрос, %принадлежит ли слово $1^n0x$ к $A$. Применение метода свед\'ения к языку \eqref{lb} немного более хлопотно, поскольку требуется оценить время, нужное для вычисления сводящего отображения, а также оценить, во сколько раз это отображение увеличивает длину слова. Для примера рассмотрим язык, универсальный для класса всех языков, распознаваемых за время $t(n)$: \begin{equation}\label{lu} \begin{split} U=\{1^k0x\mid &\text{ машина }M_k \text{ останавливается на входе }x\\ &\text{ с результатом 1 за } t(|x|) \text{ шагов}\} \end{split} \end{equation} К языку $U$ сводится любой язык $L$, распознаваемый за время $t(n)$: для подходящего $k$ (зависящего от $L$): $$ x\in L\Leftrightarrow 1^k0x\in U. $$ Язык $U$ удовлетворяет следующему немного ослабленному варианту теоремы~\ref{th-upperbound-improved}: \begin{theorem} (1) Для некоторого квадратичного полинома $p(n)$ для любой функции $t$ и любой нумерации машин язык неразрешим за время $t(\lfloor(n-1)/2\rfloor)-p(n)$ на одноленточных машинах Тьюринга. (2) Для некоторой нумерации одноленточных машин Тьюринга для любой функции $t(n)\ge n$ такой, что функция $1^n\mapsto (\text{двоичная запись }t(n))$ вычислима за время $O(t(n)\log t(n)+n^2)$ на одноленточной машине Тьюринга, язык \eqref{lu} можно распознать за время $O(t(n)\log t(n)+n^2)$ на одноленточной машине Тьюринга. \end{theorem} \begin{proof} Первое утверждение доказывается сведением задачи разрешения \eqref{lb} к задаче разрешения $U$. А именно слово $1^k$ принадлежит \eqref{lb} тогда и только тогда, когда слово $1^k01^k$ принадлежит $U$. Поэтому если машина Тьюринга $M$ распознает язык $U$ за время $t'(n)$, то применив эту машину к слову $1^k01^k$ мы за время $t'(2k+1)$ узнаем, принадлежит ли слово $1^k$ языку \eqref{lb}. Нужно еще учесть время, необходимое для преобразования слова $1^k$ в слово $1^k01^k$. Это можно сделать за время $O(k^2)$. Поэтому общее время работы машины Тьюринга для распознавания \eqref{lb} будет равно $t'(2k+1)+O(k^2)$. Если $t'(n)=t(\lfloor(n-1)/2\rfloor)-p(n)$, где $p(n)$ подходящий квадратичный полином, то $t'(2k+1)+O(k^2)$ будет меньше $t(k)$ и мы получим противоречие. Второе утверждение доказывается точно так же, как и теорема~\ref{th-upperbound-improved}. \end{proof} Если функция $t(\lfloor(n-1)/2\rfloor)$ существенно меньше, чем $t(n)$, то зазор между верхней и нижней оценками для языка~\eqref{lu} хуже, чем для языка~\eqref{lb}. Например, если $t(n)=2^{2n+1}$, то язык~\eqref{lu} нельзя распознать за время $2^n$, и можно распознать за время $O(n2^{2n})$, в то время как язык~\eqref{lb} нельзя распознать за время $2^{2n+1}$ (и можно распознать за время $O(n2^{2n})$). С другой стороны, если функция $t(n)$ ограничена полиномом, то зазоры между верхней и нижней оценками для языков~\eqref{lu} и~\eqref{lb} одинаковы. \section{Теорема Фишера--Рабина} Классическая теорема Тарского утверждает, что элементарная теория упорядоченного поля действительных чисел разрешима. Это означает, что имеется алгоритм, который по замкнутной формуле сигнатуры $$\{0,1,+,\times,=,<\}$$ выясняет истинна ли она в упорядоченном поле действительных чисел. Теорема Фишера-Рабина утверждает, что такой алгоритм не может быть быстрым: разрешить эту теорию невозможно за время $2^{o(n)}$ (где $n$ длина записи исходной формулы). Под длиной формулы мы понимаем количество символов в ней. При этом каждая переменная считается одним символом. Чтобы алфавит формул оставалься конечным (ведь каждая машина Тьюринга может получать на вход только слова над конечным алфавитом), мы зафиксируем некоторый конечный список индивидных переменных $V$ и будем предполагать, что в формулах не используются другие переменные. Существует такой конечный список, что ни одна машина Тьюринга не разрешает элементарную теорию упорядоченного поля действительных чисел за время $2^{o(n)}$. Более того, это верно для элементарной теории действительных чисел в обедненной сигнатуре $\{0,1,+,=\}$. \begin{theorem}[Фишера--Рабина] Не существует одноленточной машины Тьюринга, разпознающей за время $2^{o(n)}$ множество истинных в аддитивной группе действительных чисел замкнутых формул сигнатуры $\{0,1,+,=\}$, содержащих только переменные из некоторого конечного списка $V$. \end{theorem} Замечание. По теореме о моделировани многоленточноых машин одноленточными теорема Фишера--Рабина верна и для многолетночных машин. \begin{proof} Воспользуемся теоремой~\ref{th-upperbound} для $t(n)=2^n$. Язык $L$, о котором в ней идет речь, можно распознать за время $O(n^22^{2n})=2^{O(n)}$ и нельзя (по теореме~\ref{th-diag}) распознать за время $2^{n}$, а значит и за время $2^{o(n)}$. Предоположим, теорема Фишера--Рабина неверна, то есть истинность формул можно было распознавать за время $2^{o(n)}$. Мы получим противоречие, доказав, что тогда и язык $L$ можно распознать за время $2^{o(n)}$. Это делается с помощью сведения. Ключевую роль здесь играет следующая лемма. {\bf Основная лемма.} Пусть дана зафиксирована произвольная машина Тьюринга $M$, время работы которой есть $2^{O(n)}$. По любому двоичному слову $w$ за время ограниченное неоторым полиномом от длины $w$ можно найти замкнутую формулу $\Phi_w$ длины $O(|w|)$ с $O(1)$ переменными, такую, что $$ M(w)=1\Leftrightarrow \Phi_w\text{ истинна.} $$ Допустим лемма уже доказана. Зафиксируем машину Тьюринга $M$, распознающую $L$ за время $2^{O(n)}$. Рассмотрим следующий алгоритм распознавания $L$: по данному $w$ находим формулу $\Phi_w$, удовлетворяющую Основной лемме и применяем алгоритм разпознавания истинности формул за время $2^{o(n)}$. Общее время работы построенной машины Тьюринга равно $$ \poly(|w|)+2^{o(|\Phi_w|)}= \poly(|w|)+2^{o(O(|w|))}= \poly(|w|)+2^{o(|w|)}= 2^{o(|w|)}. $$ По условию, не существует машины Тьюринга, распознающей $L$ за время $2^{o(n)}$, следовательно, не существует и машины Тьюринга, распознающей истинность формул за время $2^{o(n)}$. Итак, осталось доказать Основную лемму. Она следует из следующей вспомогательной леммы. {\bf Вспомогательная лемма.} (1) По любому натуральному $n$ за время $\poly(n)$ можно построить формулы $Z_n(x)$, $N_n(x)$, $P_n(x,y,z)$, $E_n(x,y)$, длина каждой из которых есть $O(n)$, и такие что \begin{align*} Z_n(x)\text{ истинна}&\Leftrightarrow x=2^n\\ N_n(x)\text{ истинна}&\Leftrightarrow x\in\N,\ x<2^{2^n}\\ P_n(x,y,z)\text{ истинна}&\Leftrightarrow x\in\N,\ x<2^{2^n},\ xy=z\\ E_n(x,y)\text{ истинна}&\Leftrightarrow x\in\N,\ x\le2^n,\ y=2^x. \end{align*} (2) По двоичному слову $u$ можно за время за $\poly(n)$ построить формулу $\Psi_u(x)$ длины $O(|u|)$ такую, что \begin{align*} \Psi_u(x)\text{ истинна}&\Leftrightarrow \text{(двоичная запись }x)=u. \end{align*} (Имеется в виду, что двоичная запись $x$ дополняется старшими нулями до слова длины $|u|$.) Число переменных во всех указанных формулах ограничено константой. Допустим, эта лемма уже доказана. Тогда доказательство основной леммы завершается следующим образом. Рассмотрим протокол работы $M$ на входе $x$. Протокол естественным образом представляется в виде матрицы размера $2^{O(n)}\times 2^{O(n)}$ (где $n=|w|$), элементы которой являются символами из некоторого фиксированного алфавита $\Gamma$ (зависящего от $M$). В этой матрице каждый элемент (кроме крайних) в любой строчке, кроме первой, является фиксированной функцией $f$ от трех своих соседей из предыдущей строчки. Элементы первого столбца также являются некоторой функцией $g$ от двух соседей из предыдщуей строки, и то же самое верно для элементов последнего столбца и некоторой функции $h$. Запишем строчки этой матрицы подряд, начиная с первой. Получим слово $v$ над алфавитом $\Gamma$, которое также будем называть протоколом. Оно состоит из $2^{cn}$ блоков длины $2^{сn}$; каждый блок соответствует одной строке матрицы. Элемент матрицы, стоящий в $i$-ом столбце и $j$-ой строке, стоит на $(j2^{сn}+i)$-ому символу слова $v$ (нумерация символов начинается с нуля). Заменив каждую букву этого слова его двоичным кодом фиксированной длины $l$ (зависящей только от машины $M$), мы получим двоичную строку длины $2^{2сn}l$. Эту строку будем называть двоичным кодом протокола. Будем называть протокол вычисления $M$ на $w$ допускающим, если $M(w)=1$, то есть первая ячейка ленты в момент остановки содержит 1. Формула $\Phi_w$ будет утверждать, что существует натуральное число $p$, двоичная запись которого является кодом допускающего протокола вычисления $M$ на $w$. Чтобы понять, как это свойство $p$ можно коротко выразить на нашем языке, полезно переформулировать его в терминах самого протокола (а не его кода). Слово $v$ в алфавите $\Gamma$ длины $2^{2cn}$ является допускающим протоколом вычисления $M$ на $w$, если и только если \\ (1) начальный символ $v[0]$ слова $v$ равен паре $\pair{w[1],\text{начальное состояние }M}$, последующие $n-1$ символов $v$ равны $w[2],\dots,w[n]$, соответственно, а все оставшиеся символы первого блока $v$, то есть $v[n],\dots,v[2^{cn}-1]$, являются пробелами,\\ (2) для всех $j<2^{cn}-1$ символ номер $(j+1)2^{cn}$ слова $v$ (то есть первый символ $j+1$-ого блока $v$) равен значению функции $g$ на паре символов $v[j2^{cn}]$ и $v[j2^{cn}+1]$, \\ (3) для всех $j<2^{cn}-1$ и всех $0