\chapter{������������� ������� � ��������������}\label{chapt02}

\section{������������� �������}\label{chapt02-1}%
\index{������������� �������}\index{�������!�������������}

������ �� �������� ������ ������������� ���������, ��
����������� ����������. ��� ���� ����� �������������� ���
���������� ������������� �������.

�������, ��� �������~$U$ ���� ����������� ����������
�������� \emph{�������������} ��� ������ ���������� �������
������ ���������, ���� ��� �������~$n$ �������
        $$
U_n\colon  x \mapsto U(n,x)
        $$
(\�� �������\index{�������!�������}\��\ �������~$U$ ��� �������������~$n$) ��������
���������� � ���� ��� ���������� ������� (������ ���������)
����������� �����~$U_n$. (��������, ��� �� �������~$U$, ��
���������� ������� ������ ��������� �� ������� ���� �����
������̣�����.)

����������� ����������� ����� ���� � ��� ������ ������� �������
(������ ���������): ��������, �������~$U$ ���� ���������� �����
������������� ��� ������ ���� ����� ������̣���� ����������
������� ������ ���������, ���� ţ �������~$U_n$ ��������
����� ������̣�����
����������� ��������� ������ ��������� � ����������� ��� �����
�������. ��������, ������������� ������� ���������� ��� �����
�ޣ���� ������� (� ������ ��� ���).

�������� ���� � ���� ������� ������ ����� ����:

\begin{theorem}
        \label{universal-function}
���������� ���������� ������� ���� ����������, ����������
������������� ��������\index{������������� ���������� �������}%
\index{�������!������������� ����������} ��� ������ ���������� ������� ������
���������.
        %
\end{theorem}

\begin{proof}
        %
������� ��� ���������, ����������� ������� ������ ���������, �
���������� ������������������ $p_0, p_1,\dots$ (��������, �
������� ����������� �� �����). �������~$U(i,x)$ ������
���������� ������ $i$\� �� ��������� �� �����~$x$. ����� �������~$U$
� ����� ������� ���������� ������������� ��������. �������~$U_i$
����� ���������� ��������, ����������� ����������~$p_i$.
��������, ����������� ���� �������~$U$, ���� �� ��������
������������� ��� ������������� ����� ���������������� (��
��������� ������ �������� �� �������, ���� ������������
��������� � ţ �����).
        %
\end{proof}

\begin{problem}
        %
��� �������~$U_n$ ��������� �������~$U$ ���� ����������
���������. ������� �� ������, ��� �������~$U$ ���������?
        %
\end{problem}

\begin{problem}
        %
����� (������������) ����������� ������� ���������� ������� �ң� ����������,
������������� ��� ������ ���������� ������� ���� ����������,
� �������� ţ �������������.
        %
\end{problem}

��� �������� ������������ ����������� ������������: ���������
$W\hm\subset \bbN\hm\times\bbN$ ��������
\emph{�������������}\index{������������� ���������}%
\index{���������!�������������} ��� ���������� ������ �������� �����������
�����, ���� ��� �������\index{�������!���������}
        $$
W_n=\{x\mid \langle n,x\rangle \in W\}
        $$
���������~$W$ ����������� ����� ������ � ������ �������� �
������ ���.

\begin{theorem}
        %
���������� ������������ ���������
��� ����������� �����,
�������������\index{������������� ������������ ���������}
��� ������ ���� ������������ �������� ����������� �����.
        %
\end{theorem}

\begin{proof}
        %
���������� ������� �����������
������������� �������~$U$. ��� ����� ������������� ������������
����������, ��������� ������ ������������ ��������� ��������
�������� ����������� ��������� ���������� �������~$U_n$.
        %
\end{proof}

\begin{problem}
        %
��� ��������� ������������� ���������, ������ �� ����, ���
������ ������������ ��������� ���� ��������� �������� ���������
�������~$U_n$?
        %
\end{problem}

\begin{problem}
        %
���������� �� ���������� ��������� ��� ����������� �����,
������������� ��� ������ ���� ���������� �������� �����������
�����?
        %
\end{problem}

\section{������������ �����������}\label{chapt02-2}
        \label{diagonal-construction}

� ���������� ������� �� ��������� ������������� ������� ���
������ ���� ���������� ������� ������ ���������. ����� ��
������� �� �� ����� ��� ������ ����� ������̣���� ����������
�������? �����������, ��� ���.

\begin{theorem}
        %
�� ���������� ���������� ����� ������̣���� ������� ����
����������, ������������� ��� ������ ���� ���������� �����
������̣���� ������� ������ ���������.
        %
\end{theorem}

\begin{proof}
        %
������������� \�� ������������ ������������\��\� ����� ��� ��
������������ ���ޣ������ ��������� ���� ����������� ����������
������.
����� $U$\� ������������ ���������� ����� ������̣����
������� ���� ����������. ���������� ������������ �������~$u(n)\hm=U(n,n)$.
��������, �� ���������~$n$ �������~$u$
��������� � ��������~$U_n$, � �������~$d(n)\hm=u(n)\hm+1$ ����������
��~$U_n$. ����� �������, ���������� ����� ������̣���� �������~$d(n)$
���������� �� ���� �������~$U_n$, � ������ �������~$U$ ��
�������� �������������.
        %
\end{proof}

������ ��� ����������� �� �������� ��� ������ ���� ���������� �������
(� ��� ����� ���������)? ���� � ���, ��� �������� $d(n)\hm=U(n,n)\hm+1$
������ �� ������� ���������� ��
�������� $U_n(n)\hm=U(n,n)$, ��� ���
��� ��� ����� ���� �� ����������.

��� �� �����, ����� ����������� �������� � ����.

\begin{theorem}
        \label{diagonal}%
���������� ���������� �������~$d$ (� ������������ ����������� �
����������), �� ������� ������� ���������� �������~$f$ �� �����
����� ����������: ��� ����� ���������� �������~$f$ ���ģ��� ����� �����~$n$,
���~$f(n)\hm=d(n)$ (��������� ��������� ���������� � ��� ������,
��� ���� ��� ��������~$f(n)$ �~$d(n)$ �� ����������, ����
��� ���������� � �����).
        %
\end{theorem}

\begin{proof}
        %
�� �������� �ӣ ��� �������: ������ ������������ �������
$d(n)\hm=U(n,n)$ (����� $U$\� ���������� ������� ���� ����������,
�������������\index{������������� ���������� �������}%
\index{�������!������������� ����������} ��� ������ ����������
������� ������ ���������).
����� ���������� �������~$f$ ����~$U_n$ ��� ���������~$n$ �
������ $f(n)\hm=U_n(n)\hm=U(n,n)\hm=d(n)$.
        %
\end{proof}

\begin{theorem}
        %
���������� ���������� �������, �� ������� ����� ������̣�����
����������� �����������.
        %
\end{theorem}

\begin{proof}
        %
������, ��������, �������~$d'(n)\hm=d(n)\hm+1$, ��� $d$\� ������� ��
���������� �������. � ����� ����, ����� ţ ����� ������̣����
����������� ����� ���������� ��~$d$ (� ��� ������, ��� �������~$d$ ����������,
�������~$d'$ �� ������� ������~$d$ � ������ ����� ����������� �������~$d'$
���������� ��~$d$; ���, ��� $d$~�� ����������,
����� ����� ������̣���� ������� ���������� ��~$d$).
        %
\end{proof}

\begin{problem}
        %
��������, ��� � ���� �������~$d$ �� �������������� ����������
������� �� ����� ����������� ����� ������̣����� �����������.
        %
\end{problem}

\section{������������ ������������ ���������}\label{chapt02-3}%
        \index{������������ ������������ ���������}%
        \index{���������!������������ ������������}

������ �� ����� �������� ��������� �����������.

\begin{theorem}
        \label{enumerable-undecidable}%
���������� ������������ ������������ ���������.
(����������������: ���������� ������������ ��������� �
�������������� �����������.)
        %
\end{theorem}

\begin{proof}
        %
���������� ���������� �������~$f(x)$, �� ������� �����
������̣����� �����������
�����������. � ������� �����������~$F$ �����
������� ����������. � ����� ����, $F$~����������� (�� ������ ��
����������� ��������������). ���� �� $F$~���� ���������, ��
�������
        $$
g(x)=\left\{
        \begin{aligned}
           & f(x), \text{ ���� $x\in F$},\\
           & 0,    \text{ ���� $x\notin F$}
        \end{aligned}
      \right.
        $$
���� �� ���������� ����� ������̣���� ������������ �������~$f$
(��� ����������~$g(x)$ �� ������� ���������, ����� ��~$x$ �~$F$,
���� �����, �� ���������~$f(x)$).
        %
\end{proof}

������� ����������, ����� ������ ��������� � ����� ���������
������������ � ������������. ����� ������, ��� ��� ��������� ���~$n$,
��� ������� $U(n,n)$~����������. ���� ��������� �����������
�������~$U$, �� ��� ��������� ���~$n$, ��� ������� $n$\� �
��������� ��������������� ��~$n$. ������� ������ �������, ���
\�� �������� ����������������\index{��������!����������������}\��\
(������������ ��������� � ������ ������) �����������.

�������, ��� ������ �������, ��� � ������� ����������� ����
������������� �������~$U$ �������� ������������ ������������
���������� ���. (���� �� �������� ��������� ������������
��������� � ������������� ��������� ���� �� ���������, �� � ţ
������� ������\� ������������ ��������� � ����\� ��� ��
��������.)

\begin{problem}
        %
�����~$U$\� ������������ ��������� ��� ����������� �����,
������������� ��� ������ ���� ������������ �������� �����������
�����. ��������, ��� ��� \�� ������������ �������\index{������������
�������}\index{�������!������������}\��\ $K\hm=\{
x\mid \langle x,x\rangle \hm\in U\}$ �������� ������������
������������ ����������.
        %
\end{problem}

\begin{problem}
        %
��������� ���������~$S$ ����������� ����� ���������. �������� ��� �����
��~$S$ �� ������� ��������� � �������� ���������~$D$ ����
������� �����, ������������� � ���� �����������. ����� ��
����������, ��� ���������~$D$ ���������?
        %
\end{problem}

\begin{problem}
        %
��������� $U\hm\subset\bbN\hm\times\bbN$ ���������.
����� �� ����������, ��� ��������� \��
������ �����\index{������ �����}\��\ ���������~$U$, �� ���� ���������
        $$
V=\{ \langle
x,y\rangle\mid \text{ ($\langle x,y\rangle \in U$) � ($\langle
x,z\rangle\notin U$ ��� ���� $z<y$)}\}
        $$
�������� ����������? ����� �� ����������, ��� $V$~�����������,
���� $U$~�����������?
        %
\end{problem}

\begin{problem}
        \label{computable-real-2}
��������, ��� ���������� ������������ �����, �� �� ����������
        \index{�����!������������ �����/������}%
        \index{������������ �����/������ �����}%
        \index{�����!����������}%
        \index{���������� �������������� �����}%
����� � ������ �����������, ������ ��
�.~\pageref{computable-real}. (��������. ���������� ����� ����
$\sum 2^{-k}$ �� ����~$k$ �� ������\� ���� �������������
���������~$P$. ��� ������ ����������� �����, �� ����� ����������
������ ��� ����������~$P$.)
        %
\end{problem}

�� ���Σ��� � ���������� �������������� ������ �
�������~\ref{computable-real-3}
�~\ref{computable-real-4}.

\section{������������ ����������� ���������}\label{chapt02-4}
        \index{������������ ����������� ���������}%
        \index{���������!�������������}

��������� ����������� ����������� ��������� �������� ��������
���������� ���� �������:

\begin{theorem}
        \label{2-no-extension}%
���������� ���������� �������, ����������� ������ ��������~$0$ �~$1$
� �� ������� ����� ������̣����� ����������� �����������.
        %
\end{theorem}

\begin{proof}
        %
������ ������� $d'(x)\hm=d(x)\hm+1$ ����� ����������� �������
        $$
d''(x)=\left\{
        \begin{aligned}
            & 1, \text{ ���� $d(x)=0$},\\
            & 0, \text{ ���� $d(x)>0$}\\
        \end{aligned}
      \right.
        $$
(������� � ����, ��� $d''(x)$~�� ����������, ���� $d(x)$~��
����������). ����� ����� ����� ������̣���� ����������� �������~$d''$
����� ��\� �������� ���������� ��~$d$ ����� � ������ �� ����� ����������.
        %
\end{proof}

���� ��������� ����� ��������� �� ���� ������������ ��������.
�������, ��� ��� ���������������� ���������~$X$ �~$Y$
\emph{����������}\index{���������� ���������} ����������~$C$,
���� ���������~$C$ �������� ���� �� ��� � �� ������������ � ������.

\begin{theorem}
        \label{non-separable}\index{����������� ���������}%
���������� ��� ���������������� ������������ ���������~$X$ �~$Y$,
������� �� ���������� ������� ���������� ����������.
        %
\end{theorem}

\begin{proof}
        %
� ����� ����, ����� $d$\� ���������� �������, �����������
������ ��������~$0$ �~$1$ � �� ������� ����� ������̣�����
����������� �����������. ����� $X\hm=\{x\mid d(x)\hm=1\}$ � $Y\hm=\{x\mid
d(x)\hm=0\}$. ����� ������, ��� ���������~$X$ �~$Y$ �����������.
����� ��� ���������� ���������� ����������~$C$; ����� �������,
��� $C$~��������~$X$ � �� ������������ c~$Y$ (���� ��������,
�����ģ� � ����������). ����� ������������������ �������
���������~$C$ (������~$1$ ������~$C$ �~$0$ ��� ����) ����������~$d$.
        %
\end{proof}

�������, ��� ���� ��������� ��������� ����������� �
������������� ������������� ������������� ��������� (���� ���
��������� �� �������� ����������� �����������, �� �� ���� �� ���
�� ���������).

\begin{problem}
        %
��� ������� ����������� ������������ ����������� ���������
� �������� ������������� �������~$U(n,x)$?
        %
\end{problem}

\begin{problem}
        %
��������, ��� ���������� �ޣ���� ����� ����������������
������������ ��������, ������� ��� �� ������� ������ ��������
���������� ����������.
        %
\end{problem}

\section{������� ���������: ����������� �����}
        \label{chapt02-5}\index{������� ���������}\index{���������!�������}

���������� � ������ ����������� ������������ ������������
��������. ��� ���� �� ��� (������������ �.\,������\glossary{����@\����}).

����ף� ��������� \emph{��������}\index{�������� ���������}%
\index{���������!��������}\label{immune}, ���� ��� ����������, �� ��
�������� ����������� ������������ �����������. ������������
��������� �������� \emph{�������}\index{������� ���������}%
\index{���������!�������}, ���� ��� ���������� �������.
(��������, ����� ��������� �� ����� ���� ����������.)

\begin{theorem}
        \label{simple-set}%
���������� ������� ���������.
        %
\end{theorem}

\begin{proof}
        %
��� �����, ����� ������������ ���������~$S$ ����� ��������
����������. ��� ��������, ��� $S$~������ ������������ � �����
����������� ������������ ����������. ����� ������������� ���,
������� ��� ������� ������������� ���������~$V$ ��������
�����\� �� ��� ������� �~$S$ (���� �� ��� �����������~$V$). ���
���� ���� ������������ � ���, ����� ���~$S$ �������� ����������
����� ���������. ��� ����� �������������, ���� ���������
���������� �����\'�� �������� (��������, �� ��������� �����~$i$
��������� ������ ���� �������, ������ �\'������~$2i$).

�������� ����������� ���������. ����� $W$\� �������������
������������ ��������� ���, ����� �������~$W_i$ ��������
����������� ��� ������������ ��������� ����������� �����. �����
��������~$W_i$ \�� ������������ ���������� �����~$i$\��\ (���
���� ������ ������� ����� ��������������� ���� � �� ��
���������). ���������� ��������� ��� $T\hm=\{\langle i,x\rangle
\mid (x \hm\in W_i) \text{ � } (x \hm> 2i)\}$. ��� ��������� �����������
(��� �����������~$W$ � ����������� ��������� $\{\langle
i,x\rangle\mid x\hm>2i\}$). ���������� ���, ����� ����������� ����,
� ������� ������ ���� ��� ���������� �����. ��������� ���������
������������ ������������~$T'\subset T$. ���������� ������
������������ ���������~$S$ ������ ������ ���, �������� �~$T'$.

��� ��������� ������������ � ����� ����������� ������������
����������. � ����� ����, ���� $W_i$~����������, �� ��� ��������
� �����, �\'������~$2i$, ������� �~$T$ (�, ������, � �~$T'$) ����
���� � ������ ������~$i$. ������ ���� ����� ���� ��~$T'$ �����
������ � �~$S$, � �~$W_i$.

� ������ �������, ���������~$S$ ����� ����������� ����������,
��������� ����� ����� ��~$0$ ��~$2n\hm-1$ ��������~$n$ ���������
����� ����� ������������~$S$ (��� �����, �������� �~$S$ c �����
�� ������~$n$ ����������\� ��� ��������� ����� ��� ������~$2n$).
        %
\end{proof}

\begin{problem}
        %
��������, ��� ����������� ���������, �� ���������� �����������
���������� �����������, �������\index{�������� ���������}%
\index{���������!��������}.
        %
\end{problem}

\begin{problem}
        %
��������, ��� ���������� ������������ ���������, ���
�������� ������ �����ޣ� (������������������ ��������� � �������
����������� ��� ����������) ��� ���������� �� ��������� ������
������� ����� ������̣���� ���������� ��������. ��������, ���
��� ��������� �������� �������.
        %
\end{problem}

