
 \documentclass[12pt, leqno]{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}        % Кодировка входного документа;
                                    % при необходимости, вместо cp1251
                                    % можно указать cp866 (Alt-кодировка
                                    % DOS) или koi8-r.

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{verbatim}
\usepackage{listings}
\usepackage{algorithm2e}

\usepackage{tabto} %Табуляция
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning,trees}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}
\usepackage{indentfirst}  % абзацный отступ после заголовка
\usepackage{enumitem} %Item tricks


%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}
\theoremstyle{definition}
\newtheorem{Example}{Пример}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\varnothing
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\first{\mathrm{ FIRST} }
\def\follow{\mathrm{ FOLLOW} }
\let\yield\Rightarrow
\def\abstractname{}

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}
\let\w\omega

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}
\def\PP{{\mathsf{P}}}
\def\NP{{\mathsf{NP}}}
\def\NPc{{\mathsf{NP}}\text{-}{\rm c}}
\def\coNP{{\rm co}\text{-}{\mathsf{NP}}}
\def\DTIME{{\mathsf{DTIME}}}
\def\NTIME{{\mathsf{NTIME}}}
\def\HALT{{\rm{HALT}}}
\def\SAT{{\rm{SAT}}}
\def\3SAT{{\rm{3\text{-}SAT}}}
\def\2SAT{{\rm{2\text{-}SAT}}}
\def\UNSAT{{\rm{UNSAT}}}
\def\LL{{\mathrm{LL}}}
\def\poly{{\rm{poly}}}
\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .  }\setcounter{subproblem}{0} }
\def\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0} }
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf{\theproblem^*}\negmedspace .$  }\setcounter{subproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\theproblem^\dagger$ .  }\setcounter{subproblem}{0} }
\def\upr{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem .  }\setcounter{subproblem}{0} }
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\medskip\noindent\stepcounter{subproblem}{\rm \thesubproblem .  } }
%прочее
\def\quotient{\backslash\negthickspace\sim}

\begin{document}
\centerline{\LARGE Задание 10}

\medskip

\begin{center}
	{\Large Сложность вычислений: разрешимость, класс $\PP$ }
\end{center}

\bigskip

{\bf Литература: }
\begin{enumerate}

\item Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. \\ {\it Алгоритмы. Построение и анализ. }\\  2-е изд. М.: Вильямс, 2005.

\end{enumerate}

\section{Машины Тьюринга и формальные языки}

	Под формальным языком $L$ мы понимаем некоторое подмножество множества всех слов над алфавитом $\Sigma$. В этой теме слова «язык» и «задача» являются синонимами, поскольку речь идёт только о задачах распознавания, то есть задач проверки принадлежности слова языку. То есть задача перемножить два числа не является задачей в наших терминах в рамках этого раздела.
	
	Каждому языку мы ставим в соответствие машину Тьюринга, которая его распознаёт. 

\begin{Def} 

	\emph{Детерминированная Машина Тьюринга} $M$  имеет $l$ лент, $k$ головок, множество состояний $Q$, множество принимающих состояний $Acc \subset Q$,  входной алфавит $\Sigma$, функцию перехода $\delta : \Sigma^k\times Q \to \{0,+1,-1\}^k\times \Sigma^k\times Q  $ -- за такт работы машина меняет состояние, символы под каждой головкой и двигает каждую головку влево, вправо или оставляет её неподвижной. На машину могут быть наложены ограничения, например, полиномиальное время работы или полиномиальная память по входу. Среди всех лент выделена входная лента, на которой в начале работы машины написано входное слово $x$. Если машина переходит в принимающее состояние, то она останавливается и принимает входное слово. 
		
\end{Def}


Будем говорить, что машина Тьюринга $M$ вычисляет функцию $M(x)$, которая равна $1$, в случае если машина $M$ на входе $x$ останавливается в принимающем состоянии, если машина $M$ на входе $x$ останавливается в не принимающем состоянии, то $M(x) = 0$, а если машина $M$ не останавливается на входе $x$, то функция $M(x)$ не определена.

$$
	M(x) = 
	\begin{cases}
		1, & M \text{ остановилась в принимающем состоянии на $x$;} \\
		0, & M \text{ остановилась в не принимающем состоянии на $x$;}\\ 
		\uparrow, & M \text{ не остановилась, функция не определена на $x$.}
	\end{cases}
$$


	 Машина $M$ \emph{принимает} язык $L$, если она принимает каждое слово из языка $L$, если машина $M$ принимает язык $L$ и к тому же все слова, принимаемые машиной $M$, лежат в языке $L$,  то будем говорить, что машина $M$ \emph{распознаёт} $L$. Язык, распознаваемый машиной $M$ будем обозначать $L(M)$.


\begin{Remark}
	Определение языка, распознаваемого машиной Тьюринга, при беглом взгляде кажется естественным, но на самом деле оно весьма коварно. На слова не из $L$ ограничений не накладывается, поэтому на них машина $M$ может и не останавливаться вовсе.
\end{Remark}


Языки, распознаваемые машинами Тьюринга, называются \emph{(рекурсивно-)перечислимыми} языками или \emph{распознаваемыми} языками.

Будем говорить, что машина Тьюринга $M$ разрешает язык $L$, если она останавливается на всех входах и распознаёт язык $L$.

Языки разрешимые машинами Тьюринга образуют класс \emph{рекурсивных} языков, также называемыми \emph{разрешимыми}.
 


Если не оговорено противного, мы будем считать, что машина Тьюринга $M$ имеет одну ленту и одну головку.

\bigskip


Поскольку машины Тьюринга имеют конечное описание, то их описание можно закодировать. Будем обозначать $M_\alpha$ машину Тьюринга, описание которой закодирована строкой $\alpha$. Мы можем просто занумеровать все возможные описания машин Тьюринга и считать, что $\alpha$ -- натуральное число. Если же это неудобно, мы можем считать, что $\alpha$ есть просто строка, содержащая описание машины Тьюринга, и если описание некорректно, то будем считать, что $M_\alpha$ -- машина Тьюринга, распознающая пустой язык.


Из возможности кодирования описаний машин Тьюринга следует, что существует машина Тьюринга, которая получает на вход описание $\alpha$ и вход $x$ и проделывает работу машины $M_\alpha$ на входе $x$. Такую машину Тьюринга будем называть \emph{универсальной} и обозначать $UM$.


\section{Разрешимые и неразрешимые задачи}

Прежде чем говорить о сложности задачи надо доказать, что она разрешима. Это далеко не всегда так даже в очень естественных случаях.

\begin{Example} Пусть язык $L$ лежит в классе $\CFL$. Проверка условия $L \stackrel{?}{=} \Sigma^*$  -- неразрешимая задача.
\end{Example}
	
Одна из самых распространённых неразрешимых задач -- проблема останова. Под проблемой останова понимается язык $\HALT$ состоящий из описаний всех машин Тьюринга, останавливающихся на пустом входе.

\begin{Example}
	$$\HALT = \{ \alpha\, |\, M_\alpha(\eps) = 1 \} $$
\end{Example}

\upr Докажите что язык $ \HALT $ является неразрешимым. Если доказать самостоятельно не получается, обратитесь к литературе.

\bigskip

Язык $L$ называется \emph{перечислимым}, если существует такая МТ $M$, которая выводит все слова из языка. МТ $M$ может вообще говоря никогда не остановится, но если слово $w$ лежит в $L$, то машина $M$  должна вывести $w$ через некоторое, быть может очень большое, число тактов.


\upr Докажите, что данное здесь определение перечислимого языка согласовано с данным выше определением. 

\upr Докажите, что язык $\HALT$ является перечислимым.

\upr Докажите, что язык $L$ является разрешимым тогда и только тогда, когда языки $L$ и $\bar L$ перечислимы.

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

\prp Докажите, что язык, состоящий из описаний МТ, не останавливающихся на некотором входе через более чем $2015$ шагов неразрешим.

\prp Является ли разрешимым язык, состоящий из описаний МТ, которые делают меньше $2015$ шагов при обработке каждого входного слова?

\section{Класс $\PP$}

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

Если детерминированная машина Тьюринга $M$ распознаёт $L$, причём для каждого слова $x$ из $L$ она делает не более чем $O(n^c)$ тактов, то язык $L$ лежит в классе $\DTIME(O(n^c))$. Такую машину Тьюринга мы будем называть детерминированной полиномиальной или просто полиномиальной.

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


Класс $\PP$ состоит из объединения всех языков, лежащих в $\DTIME(O(n^c))$, то есть

$$
 \PP = \bigcup_{c \geq 0} \DTIME(O(n^c))
$$


\prdag Покажите, что в определении класса $\PP$ неважно сколько лент и головок у машины Тьюринга $M$. То есть, если язык $L$ распознаётся за полиномиальное время машиной Тьюринга $M$ с $k$ лентами и $l$ головками, то он распознаётся и некоторой машиной $M^\prime$ с одной лентой и одной головкой.

\bigskip

\section{Задачи на повторение}

\prp Найдите все неточности в следующем утверждении (возможно, их там и нет).

Некто доказал теорему, что любой алгоритм проверки 
$n$-битового числа на простоту требует $\Omega(n^2)$ операций.

Значит ли это, что существует такая (абсолютная) константа $c>0$, что любой 
алгоритм $A$ проверки простоты
будет для всех $n>N(A)$ (число $N(A)$ зависит от алгоритма $A$) проверять простоту
произвольного
$n$-битового числа, используя не менее $c n^2$-операций?




\section{Домашнее задание}

Задачи из канонического задания № 12-15, задачи № 1-3, 5 из данного текста.


\end{document}