% ���������� �������� 20.04.2000
\chapter{���������� � ��������}\label{chapt07}
        \index{������������!� ��������}

\section{������ � ��������}\label{chapt07-1}
        \index{������!� ��������}

���� ���������~$B$ $m$\� �������� � ����������� ���������~$A$, ��
� $B$~���������. ����� ����, ���� ���� $A$~� �����������, �� �
��� ���� ������ � \�� �������\index{������}\��\ ���~$A$, ������� �������� ��
������� � �������������� ����� ���������~$A$, �� �� �����
� ��� �������
�������� �� ������� � �������������� ����� ���������~$B$. �
����� ����, ���� $f$\� �������� ������� � ���� �� �����
������, ����������� �� ��������� �����~$x$ ���������~$B$,
���������� �������� � �������, ����������� ��~$f(x)$
���������~$A$.

����� ������, ��� $m$\� ���������� ���������� ����������� �������
�������� ������������ �������: ��\� ������, ������� ��������
������ ���� ������, ��\� ������, ����� �� ���� ������ � ���������
������� �� �������� ������ � �������������� �����~$x$ ���������~$A$.
��� ������, �� �������������� � ����� �����: ���� ������
��� ���������~$A$, �� ����� �������� �� ������� � ��������������
����� ���������~$B\hm=\bbN\setminus A$. ����� ������
��\� �������� ����, �� ����� �� ���� ���������� ��
���������������. ������ ������: ���� ������ ��� ���������~$A$,
����� �������� �� ������� � �������������� ���� �����������
����� ���������~$B\hm=A\hm\times A$. (����� ������� ���� ������ ���
��� �������.)

������� ����������� ������� ���������� �� ���� ����������� �
���� ����� ����������� ���������� ���������~$B$ � ���������~$A$.
�������� ����� � ������������ ����������� ������: $B$~��������
�~$A$, ���� ���������� ��������, ������� ��������� ���������~$B$
��� �������, ��� ��� ������������ ������ � �������, �����������
�� ������� ��� ���������~$A$. � ����� ��������������� ��������:
���� ��������, ���������� ������ ������� �������
\verb|a(x:integer):boolean| (�� ��������� ������ ���������); ����
�������� ��������� ���������~$B$, ���� ������~\verb|a(x)|
���������� ���������� ������ ��� ���������~$A$.

���� ��� ���������� ���������� \emph{����������� �� ��������}\index{����������
�� ��������}\glossary{�������@\�������}, ���
$T$\� �����������\index{$T$\� ����������}.
�����������: $B\hm\leqT A$\index{$\leqT$} ��������, ���
$B$~�������� �� �������� �~$A$. ��� ��������� ������� ������ ���
$T$\� ����������:

\begin{theorem}
        \label{T-reducibility-lemma}%
(\textsf{�})~����~$B\hm\lem A$, ��~$B\hm\leqT A$.
        %
(\textsf{�})~$A\hm\leqT {\bbN\setminus A}$ ��� �����~$A$.
        %
(\textsf{�})~����~$A\hm\leqT B$ �~$B\hm\leqT C$, ��~$A\hm\leqT C$.
        %
(\textsf{�})~����~$A\leqT B$ � $B$~���������, �� $A$~���������.
        %
\end{theorem}

\begin{proof}
        %
��� ��� ����������� ����� ��������\� �������, ��������,
�����������~(�). ����� � ��� ���� �������� ���~$A$, ����������
������ ������� ����������� ��������� ���~$B$, � ����� ��������
���~$B$, ���������� ������ ������� ��������� ���~$C$. �����
����� �������� ������ ������� $B$\� ��������� �� ���� ������
�������� � ��������� ����������� �������� ���~$A$, ������������
������ ������� ��������� ���~$C$.
        %
\end{proof}

�������, ��� (� ������� �� $m$\� ����������) ��������������
��������� ������ ����� $T$\� ��������� � �������������. ��������,
���������� ������������� ������������� ���������~$K$ �������� �
�����\'� ���������~$K$.

����� �������� �� ������ � ���������� �
���������~$A$, �� � ������ �� ����������, ������� ������ � ������� ���
���������~$A$. ����� ����� �������� ��������� ���������
�������~$f$. ��� ��������, ��������, ��� ���� $f(x)$~����������, �� ��
�����~$x$ �������� ��������������� � ���� �����~$f(x)$, � ����
$f(x)$~�� ����������, �� �� ���������������. (��������������, �����������,
��� ������ \�� �� ��������\��\ � ������
������, ������ ����������, �� ��� �������� ��� �������.)
� ���� ������ �������, ��� (���������) �������~$f$ ���������
������������ ���������~$A$.

� ����� ����������� ���������� ���������� ������� �������
��������� ������ ��� �������� (\�� ��\��\ � \�� ���\��). �����
����������� ����� �� �����������. �����
$\alpha\colon \bbN\hm\to\bbN$\� ������������ �����
������̣���� �������. ����� ����� �������� � ��������,
\emph{���������� ������������}~$\alpha$\index{������������� ������������};
����������� �� ���������
�������� � ���� ������ �������~$\alpha$. ������ ��� ���������
�� �������� ������������:

\begin{theorem}
        \label{oracle-function-graph}%
��������� �������~$f$ ��������� ������������ �����
������̣���� �������~$\alpha$
����� � ������ �����, ����� ��� ��������� ������������
���������, ����������� �������� �������~$\alpha$, �� ����
������������ ���������~$\{\langle n, \alpha(n)\rangle\mid
n\hm\in\bbN\}$.
        %
\end{theorem}

\begin{proof}
        %
� ����� ����, ���� �� ����� �������� �������~$\alpha$, �� �����
� �������� �� ������� � �������������� ������������ ���� �������
�������~$\alpha$. ��������, ���� �� ����� ���������
������~$\alpha$, �� ����� �����~$\alpha(x)$ ��� �������~$x$,
������� �� �������
������� � �������������� ������� ���~$\langle x,0\rangle,
\langle x,1\rangle,\dots$, ���� �� ������� ������������� �����.
        %
\end{proof}

��������� ������������ ������������ �������~$\alpha$, �� ������������,
��� $\alpha$~����� ����������. ��� ����������� �������������: ���
�� ����� ������̣���� ������� �������� ��������� � ��� (��� � �������
����������) ������� ���������. ��������, �� �������~$\alpha(x)$, � ���������,
��� �������~$\alpha$ �� ���������� ��~$x$. �������� �� ���, ��� ��������
� ���� ����� \�� ��������\��\ � ��� �� ����� ������ ���������?
��� �� ����� ����������� ���������� �����\� �� ���������� �
� �����\� �� ������� ������ ���������, �� ��������� ������ ��~$\alpha(x)$?
����� �� �� ����������� ��������� ��������� �������� �������~$\alpha$?
��������, ������� �� ������� �������~$f(x)$, ��������
��������
        $$
f(x)=  \left\{
          \begin{aligned}
             &0, \text{ ���� $\alpha(2x)$ ��� $\alpha(2x+1)$ ����������,}\\
             &\text{�� ���������� � ��������� ������}
          \end{aligned}
       \right.
        $$
���������� ������������~$\alpha$? ������ ������, � ������� ��
������ ����� ������̣���� �������, ��� ���� ������ (� ������ ��
�������������) �������� �����������, � ������ ���� ��������,
����� ������ ������� ������� � ����. ������� ��, ������ �
������������ ������������ ��������� �������~$\alpha$,
������������, ��� �������~$\alpha$
����� ����������.

\begin{problem}
        %
����� ���� ��� ��������� ���������~$X$ �~$Y$. ����� �������������
���������, ������� ������ � ���� �������� ���~$X$ � ���~$Y$,
� �������, ������� ����� ��������� � ������� ����� ��������.
��������, ��� ��� ����������� �� ���� ������ �����������
������, ������ ����� ���������~$Z$, ��� $X$\� $Y$\� ������������ ���������
� $Z$\� �������������.
        %
\end{problem}

\section[������������� ��������]
{������������� ������������:\\������������� ��������}\label{chapt07-2}

������ �� ����� ������������� ����������� ������������ �������
������������~$\alpha$, �� ������������ � ���������� � �������
�������.

�� �������� ��������\index{�������} ������� � ������������ ����������� �
����������, ������̣���� �� �������� ������������ ������������
����. ����� ������� �������� �������
���~$\langle\text{��������},\text{��������}\rangle$;
������� ����� ��������� �������������, ����� ����
�� ��������� ������� � ��� ����� � �������� �
���������� ��������� ��������, ������������ ��������� �������� \���

��� ������� ���������� \emph{�����������}\index{����������
�������}, ���� ����������� ��
�������� ���� ��\� �������� ������ �������, �� ���� ���� ��� �����
�����, � ������� ��� ��� ���� �� ���������� � ��������� ������
��������.

����� ������� ���������~$M$ ����� ����~$\langle x,y,t\rangle$,
��� $x$ �~$y$\� ����������� �����, � $t$\� �������. �����
��������, ��� ��� ������~$\langle x_1, y_1, t_1\rangle$ �~$\langle
x_2, y_2, t_2\rangle$ \emph{������������}\index{�������������� ������}
���� �����,
����~$x_1\hm=x_2$, $y_1\hm\ne y_2$, � �������~$t_1$ �~$t_2$ ���������.
���������~$M$ ����� �������� \emph{����������}\index{����������
���������}, ���� � Σ�
��� �������������� ���� ����� �����.

����� $M$\� ���������� ���������, � $\alpha$\� ���������
�������. ����ң� �~$M$ ��� ������ ����~$\langle x,y,t\rangle$,
��� ������� $t$~�������� ������~$\alpha$ (������~$t$ ��������
������������� �������~$\alpha$). �������� � ��� �������
���������, ������� (� ���� ������������) ����� ���������� �����
��� ����, � ������� ������ ����� �����, � ������\� ���.
������, �������� ������ ���������� � ���������� �������, ��
������� ������ ��������� ������� (������ ������, ���������).
����� ���������� ��� �������~$M[\alpha]$.

\begin{theorem}
        \label{alternative-definition-relative-computability}%
��������� �������~$f\colon \bbN\hm\to\bbN$ ���������
������������ ����� ������̣����
�������~$\alpha\colon \bbN\hm\to\bbN$ ����� � ������ �����, �����
���������� ������������ ���������� ��������� �����~$M$, ���
��������~$f \hm= M[\alpha]$.
        %
\end{theorem}

\begin{proof}
        %
����� ������� ���������~$p$, �����������~$f$ � ���������� � ����
��������� � ������� ���������~$\alpha$. ����� ��� ����
�����������~$n$ ������������ ������ ���� ��������� �� �����~$n$ ��
���� �����, �� ���� �������������� ��� ���������
��������~$\alpha(n)$ ��� ������� ��������� � ������� ���������. ���
�������~$n$ ���������� ������ ���������\� ������� ��������� �
������� ��������� ������������� �������� �� �ޣ���� ����������.
�� ��������� ������ ����� ������ ���������� ����������� �
��������� ������ �����. ��� ������ �� ������������, ��� ��
�����~$x$ �������� �����~$y$ (�� ��������� �����), �� ��������
������~$\langle x,y,t\rangle$, ��� $t$\� �������, ���������� ���
��������� � �������� �������~$\alpha$, �������������� �� ����
�����.

���������� ��������� �����, ������� �� ���������~$M$, �����
������������ (��������� ��������� ��������� ���������� ��� ���
��������). � ���� ��������� ��� �������������� ���� ����� �����.
� ����� ����,
���� ��� ������ � ���� ��~$x$ � ���� ����� ������~$\langle
x,y_1,t_1\rangle$ �~$\langle x,y_2,t_2\rangle$ �~$y_1\hm\ne y_2$,
�� ��� ������������� ������ ����� � ������ ���������� �� �����
� ��� �� �����~$x$. ��� ����
� �����\� �� ����� ���������, �� ���� �� ���� � ��� �� ������ �
��� ���� �������� ������ ������. ��� ������ ����� �
�������~$t_1$ �~$t_2$, � ������ ��� ������� �����������. ����,
���������~$M$ ���������.

����� $\alpha$\� ����� ������̣���� �������. ����������� ţ �
���������~$p$. ����� ����� ���������~$p$ ��������� �������~$f$.
�������, ���~$f\hm=M[\alpha]$. � ����� ����, �����~$f(x)\hm=y$, ��
���� ������ ���������~$p$ �� �����~$x$ ���� �����~$y$. ���
������ �������� � ���� ��������� ������� �������~$\alpha$ �
��������������� ��������� ����� �������������� ���� ������. �����
$t$\� �������, ���������� ��� �������� ��� ���� ������� �
���������� �� ��� ������. ����� $t$~�������� ������~$\alpha$.
����� ����, ������~$\langle x,y, t\rangle$ ������ � ���������~$M$.
�������������, $M[\alpha](x)$~���������� � �����~$y$.

��������, ����~$M[\alpha](x)\hm=y$, �� ����������
������~$\langle x,y,t\rangle\hm\in M$, ��� ������� $t$~��������
������~$\alpha$. ��� ������ ������������� ��������� �����
������ ����������. ��������� $t$~�������� ������~$\alpha$,
������������� � ���������~$p$ ������� ���������~$\alpha$
�����ģ� � ����, ��� ���������� ������ ������ �� �����
����, � ��������� ���� �����~$y$.

����, ��� ����� ���������~$p$ �� ��������� ����������
���������~$M$, ������� ������ �� �� �������, ��� � ���������~$p$, �
������
�������� ����������� ������� ��������.

����� �������� ������ ��������, �����������, ��� �������
���������� ���������~$M$, � �������� ������������� ���
���������~$p$. ��� ��������� ����� (����� ������������� �
��� �������, ������������~$\alpha$) ���������
�������~$M[\alpha]$. ���������~$p$ ��������� ���: ������� ����~$x$,
��� ����������� ���������~$M$ � �������� � Σ� ������,
������ ������ ������� ��������~$x$. ��� ������ �����
������~$\langle x,y,t\rangle$, ������� ������� ���������
(������� ������� �������) �� ��������, ��������
��~$t$ ������ �������~$\alpha$. ���� ��������, �� ����������
������������� � �������� �����~$y$, ���� ���, ������������
���������~$M$ ������������.

��������, ��� ����������� ���������~$p$ ��������� �������~$M[\alpha]$.
        %
\end{proof}

\begin{problem}
        %
�����������, ��� �� ������� ��� ���������� � ��� �������:
������� �� ����������� ���������~$M$ ��������� ���������
���������, ��� ��� ������� �� ������ �������� ��������������,
� ����� �� ��������� ��������� ��������� ����������
���������~$M'$. ����� �� $M'$~���������� ��~$M$?
        %
\end{problem}

\section{�������������}\label{relativization}
        \index{�������������}

����� ����������� ��������� ����� ������̣����
�������~$\alpha$. ����� ��� ������ ���������� ������� �����
����, ��� �������, \�� ��������������\��\ ������������~$\alpha$,
���� �� ���� ������������ � ������������� �������� ����������
������� �� �������, ���������� ������������~$\alpha$
(������� ��� ��������� �������� ����� $\alpha$\� \emph{�����������}%
    \index{������������!������������~$\alpha$}%
    \index{$\alpha$\� ���������� �������}%
    \index{�������!$\alpha$\� ����������}).
��� ���� ��� ���������������� ���� ���������� ��������
� ����, � �������������� �������� ����� ������ ��.

� ���������, ����� ���������� ������� \emph{�������������
������������}~$\alpha$ (��� $\alpha$\� \emph{�������������}%
    \index{$\alpha$\� ������������ ���������}%
    \index{�������������� ������������~$\alpha$})
��������� ����� �� ������������� ��������: ��� �������
����������� $\alpha$\� ���������� �������, ��� ��������� ��������
$\alpha$\� ���������� �������, ��� �������� $\alpha$\� �����������
(����������� ������������~$\alpha$) ��������� \��� �����
������� � ����� ������ �������� ������~$\alpha$\� ������������
��������.

����� $E$\� �����������e ��������� ��� ����~$\langle x,
t\rangle$, ��� $x$\� �����, � $t$\� �������. �����
$\alpha$\�
��������� ����� ������̣���� �������. ����ң� � ���������~$E$ ��
����, � ������� ������ ����� �������� ������~$\alpha$; ������
����� ����� ��� �������� ���������, ������� �� ���������~$E\lbk\alpha\rbk$.

\begin{theorem}
        \label{relative-enumerable}%
���������~$X$ �������� $\alpha$\� ������������ ����� � ������
�����, �����~$X\hm=E\lbk\alpha\rbk$ ��� ���������� �������������
���������~$E$. (�������, ��� � ���� ������ �� ���������
�������� ������������ ������� ���� ������������.)
        %
\end{theorem}

\begin{proof}
        %
����� $X$~���� ������� ����������� ���������� ������������~$\alpha$
�������~$f$. �����~$f\hm=M[\alpha]$ ��� ����������
������������� ����������� ���������~$M$. ������� �� ���� ����� �~$M$
������ ������ � ������ �����; ��������� ���������
������������ ���������~$E$. ����� ���������, ���
$E\lbk\alpha\rbk$~����� �������� ����������� �������~$M[\alpha]\hm=f$, ���
���~$E\lbk\alpha\rbk\hm=X$.

��������, �����~$X\hm=E\lbk\alpha\rbk$ ��� ����������~$\alpha$. �����
���������� ���������~$M$, ������� ���������, ���� � ��������
������ ���� ��~$E$ �������� �����~$0$. ����, ��� ���������~$M$
����� ���������� � ��� $M[\alpha]$~����� ��������, ������̣����
��~$X\hm=E\lbk\alpha\rbk$ � ����������� ������ ������� ��������.
        %
\end{proof}

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

\begin{theorem}
        \label{relative-universal-function}%
����� $\alpha$\� ����� ������̣���� �������.
���������� ���������� ������������~$\alpha$ ������� ����
����������, ���������� ������������� ��� ������ ����������
������������~$\alpha$ ������� ������ ���������.
        %
\end{theorem}

\begin{proof}
        %
��� � � ������ �������, ����� ����� ��� ��������� �������������
�������������� ��������������� ������������������ �������.
��������� �����\� �� ���� ���������������� (�����������������
�� ���� ��� ������ ������� ��������) � ������������ ���
���������, ������� �������� � ���� ������ ������� ���������~$\alpha$.
������ � �������� ������������� ����� ����� �������
        $$
U_\alpha(i,x)=(\text{��������� ���������� $i$\� �� ��������� �~$x$}).
        $$
�� ������������ ������ ������, ����� �����������, ���
�������~$U_\alpha$ ������� ��~$\alpha$. �������, ����� �����������
ţ ��������� ��~$\alpha$ �� ������� (����, �����������,
�������� ������ �������~$\alpha$).

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

���������� ������������� ������������ ���������~$Z$ ���ף���
����~$\langle n, x,y,t\rangle$, ���~$n$, $x$ �~$y$\� �����,
� $t$\� �������. ������ �� ���������������,
�� ����� � ����, ��� ��� ���������~$n$ ����� �������~$Z_n$
���������� ��� ������������ ��������� �����.

����� ���� ������������ �������� ����� ����� ���� �
����������, � ������������. �� ����� �������������
�������������� ������������ �������, �� ����� ����������.
������� �������, �� ����� ��������� ����� ������������ ���������~$Z'$
� ������ ����������: ��\� ������, ��� �������~$Z'$ ���������;
��\� ������, ���� �������~$Z_n$ ��� ���������~$n$ ���� ���������,
�� ��� �� ����������~($Z'_n\hm=Z_n$).

��� �������� ������: ����� �����������~$Z$, ���������� (��
��������� �~$Z'$) ��������, ���������� ������� ������ ���������
������� ������������. ����, �� ��������� ������������
���������~$Z'$, ������������� ��� ������ ���������� ������������
��������.

������ ����� ������� ���������� ���������~$W$, ��������
������������� $\alpha$\� ���������� �������. ������,
������~$\langle \langle n,x\rangle, y, t\rangle$ (������ ţ ������
������ �������� ����, ��� ��� ������������� ������� ������� ��
���� ����������) �����������~$W$, ����~$\langle
n,x,y,t\rangle\hm\in Z'$. ����� ������, ��� ���������~$W$ ���������.
��� ������ �������~$\alpha$ ���
���������� ��������� ������ ��������� $\alpha$\� ����������
�������~$U_\alpha$ ���� ����������; ţ $n$\� �� �������
����~$Z'_n[\alpha]$, ��� $Z'_n$\� $n$\� �� ������� ���������~$Z'$.
������� ����� ������� �������~$U_{\alpha}$
����������� ��� $\alpha$\� ����������
�������, ��� � ����������� ��������.
        %
\end{proof}

� ���������������� ������ ���������� �������, �������, �
������ ������� ������� ������������� �������:
$\alpha$\� ���������� ������� ���� ���������� �������� \emph{�������
������������� �������� ��� ������ $\alpha$\� ���������� �������
������ ���������}\index{������� ������������� �������!������������~$\alpha$},
���� ��� $\alpha$\� ���������, ������������ ��� ������
$\alpha$\� ���������� ������� ������ ��������� � ���
������ $\alpha$\� ���������� �������~$V$
���� ���������� ���������� ����� ������̣����
$\alpha$\� ���������� �������~$s$ ������ ��������� (\��
����������\��), ��� �������~$V(n,x)\hm=U(s(n),x)$ ��� ����~$n$ �~$x$.

������� �������������� (�.~\pageref{goedel-numbering-exists},
�������~\ref{goedel-numbering-exists}) ����������,
��� ������� �������������
������� ��� ������ $\alpha$\� ���������� ������� ����������. �����
����, ����� ��������, ��� ����������� ��� ��������������
(��.~����) �������~$s$ ����� �� ������ $\alpha$\� ����������, �� �
������ ���������� (� ����� �� ��������� �������������� �������~$s$ �����
���~$x\hm\mapsto[n,x]$, ��� ���������� ������ ����������
������������� ���������� ��������� ���, � $n$\� ���������
������������� �����).

������, ������ � ������� $\alpha$\� ���������� �������, ����� �
���� �� ������ � ����� \�� ������ �������\��\ ����������\index{������
������� ���������}.
������������ ��������� (���������� ������ ��������)
�������� \�� ������ �������\��\ ����������.

������ � ���������������� ������ ����������, ������ �����������
����� ��������. ����� $A$\� �����\� �� ������������ ���������.
����� ���������, ��� ���� ����� ��������� �����������,
������� ���������~$A$ ������� ����������; ����� �� �����~$x$,
��� ����� ��������, ����� �� ��� � ���������~$A$ ��� ���,
� ��� ��������\� ����� �� ������������ �������� � ��
����������, ��� � ��� ��������� ���� �����. ����� ��� �� ������
���������� ����� ������������� ���������������� ������������~$A$,
�� ��� ����� �������� �� ����� � ������ ������� ����
����������� ������ �� ����� ������� (�� ������� ���) �
���������� �� ����� ���������. ����� ����, ��� ����� ��������
� ���� ������ � �������������\� �� ��, ��� ��� ��� �����
$B$\� ����������, ��� ��� ����� $A$\� $B$\� ���������� (���������� �
����� ���������~$A$ �~$B$).

�������, � ���� �������� �� ����� ���������� ������� ���أ���.

\section{$\bfnull'$\� ����������}\label{jump-computations}

� ���� ������� �� ���������� ������������ ������������
$m$\� ������� ������������� ���������. ����� ��� ����� ���������
$m$\� �������� ���� � �����, � ��� ����� $T$\� �������� ���� �
�����. ������� ���� �����\� �� ������� ��������� ������������
������ �� ���, �� ��� ��������� � ������������ �������. �����
������� �������� \emph{$\bfnull'$\� �����������}%
\index{�������!$\bfnull'$\� ����������}\index{$\bfnull'$\� ���������� �������}.

���������, ��� ��������� ��� $\{\langle p,x\rangle\mid
\text{���������~$p$}$  ��������� ������ �� �����~$x\}$ ��������
����� �� $m$\� ������ ������������ ��������, ����� �������, ���
$\bfnull'$\� ���������� ������� ����������� ��������, �������
������ ����������� ������, �������� �������� ���������: �����
������� �������� ��������� � ����, � �� ��������,
��������������� �� ��� ��������� �� ���� ����� ��� ��
���������������. (��� ���� ���������� �� ����������
���������\� �����
�������, ��� ��������� � �������.)

����, ��� ����� ������������ ��������� ��������
$\bfnull'$\� ����������, ��� ��� �������� � $m$\� �������
������������� ���������. (��������, ��������, �������\�
���������� � ������������� ������������� ��������� �����
$\bfnull'$\� ���������, �� �� �����������.)

������� ��������� ������� �������� $\bfnull'$\� ����������
�������:

\begin{theorem}
        \label{limit-computations}%
(\textsf{�})~����� $T$\� ����� ������̣���� ���������� �������
���� ����������� ����������. �����ģ� � ������� �� ������� ���������,
���������� �������
        $$
 t \colon  x \mapsto \lim_{n\to\infty} T(x,n).
        $$
(��� ������� ��� �� ������� ���� ����� ������̣����, ��� ���
��� ���������~$x$ ��������� ������ ����� �� ������������.)
�������~$t$ ����� $\bfnull'$\� ����������.
        %
(\textsf{�})~������ $\bfnull'$\� ���������� �������~$t$ �����
���� �������� ��������� ������� �� ��������� ����������
����� ������̣���� �������~$T$.
        %
\end{theorem}

\begin{proof}
        %
(a)~����� $T$\� ���������� ����� ������̣���� ������� ����
����������. ����ף� ����~$\langle x,n\rangle$ ����������,
����~$T(x,n)\hm=T(x,m)$ ��� �������~$x$ � ��� ����~$m\hm>n$.
        %
�������, ��� ��������� ������������ ��� ����������� (�����
��� ����~$\langle x,n\rangle$ �~$\langle x,m\rangle$
�~$n\hm<m$ �~$T(x,n)\hm\ne T(x,m)$, �� �������� ����~$\langle
x,n\rangle$ � ������������ ���� ������������ ���). �������
��������� ������������ ��� $\bfnull'$\� ���������. ������� �������,
$\bfnull'$\� �������� ��� ����� ���� ����� ���������,
��������� �� ���.

���������� ������ ��������� $\bfnull'$\� �������� ����������
���������� �������~$t$. ������� ����~$x$, �� ������������� ��
������� ����~$\langle x,0\rangle, \langle x,1\rangle,\dots$ �
��� ������ �� ��� ���������, �������� �� ��� ����������. ���
������ ���������� ����~$\langle x,n\rangle$ ����� ����������,
��������~$T(x,n)$ �������� � �������� ����������. ��������,
��������� $\bfnull'$\� �������� ��������� �������~$t$.

(�)~������� ������ �������� �����������. ����� $t$\� ���������
$\bfnull'$\� ���������� ������� ������ ���������. ��� ����
��������� ���������� (� ������� ������) ����� ������̣����
������� ���� ����������~$T$, ��� �������
        $$
 t (x) = \lim_{n\to\infty} T(x,n)
        $$
��� ����~$x$ (� ��� ����� ����� ��������� ����������
������������). ������ ����� �� ������� ���� ���������
�����������, �������� �������~$T$ ��������� ����� � ���������
����������� ��������, ������� �� ����� ���������� �ף�������.
��� ���� $\displaystyle{\lim_{n\to\infty} T(x,n) \hm= a}$
��������, ��� ��� ���� ����������
�������~$n$ ��������~$T(x,n)$ �����~$a$ (�, � ���������, ��
�����~$\star$).

����� ����������� �� ����� ���� �������������: ���� �
������������������, � ������� ���� �ף������, ������ �� ���
�������� �� ��� ��������� ������ ������ ����� (�ӣ ����� �����),
�� ������������������ ����� ����� ������� ������ (���
��\� �������� �� ����� �������).

������ ��������� �������~$T$. �� ������������� �������~$t$
����������� ��������� ����������~$p$, ������� ������ �
������������������ ������� ���������� ������������� ���������~$K$.
��������� �����~$K_n$ �������� ������������ ���������~$K$,
��������� �� ��� ��� ���������, ������� ������ ������������ ��~$n$~�����
������������ ���������~$K$. ��������~$T(x,n)$, ��
������� $n$~����� ������ ���������~$p$, ��� ����
��������� ������~$K$ ��� �������� �����������~$K_n$. ���� ��
��� $n$~����� ���������~$p$ �� ���� ������ (��� ����� ���� ��
������ ��������\� ����ģ���� �� ����� ����� ���� ������������,
$K_n$~����� ���������� ��~$K$, �� � ������ �������~$t$ ��~$x$
����� ���� �� ����������), ��~$T(x,n)\hm=\star$. ���� �� �� $n$~�����
��������� ����� ����, �� ���� ����� � ����� ���������~$T(x,n)$
(�� ����� �����������, � ������� �� ������ �����).

��������� ��������,
���~$\displaystyle{t(x)\hm=\lim_{n\to\infty}T(x,n)}$.
����� $t(x)$~�����
����������~$a$. ����� ������ ���������~$p$ (� ����������
��������~$K$) ����� ��������� ����� ����������� � ���� �����~$a$.
��� ���� ���������� ������������ ���� �������� �����
�������� � �������. ������� ��� ���������� �������~$n$ ���������~$K_n$
� ���� ������ ��� ����� ��������� �~$K$. ��������~$n$ �ݣ,
���� ���� (����� ��� ��������� ����� ������ ���������~$p$), ��
����� �������������, ��� ��� ����~$n$ � ��� ���� �\'������~$n$
��������~$T(x,n)$ ����� �����~$a$.

�� ��� ���� �ݣ ��������, ��� ���� ������ ���������� � �����~$a$,
��~$t(x)\hm=a$. ����� ��� ������� ���������, ��������� �
���������. ����� ��� ���������~$K$ ������ ���������~$p$ ��
�����������. �� ��� �� ����� ����� ���������� ���, ��� ���
������~$n$ ���� ���������� ���������� �� �ޣ� ����, ���
���������~$K_n$ ���������� �� ����������~$K$, � ���� ��������
��� ��� ���������� ����� ���������� �����.

����� ���������� � ���� ����������, ������� ����������� �������~$T$.
� ������, �����������, ��� ���� ��� ����������~$T(x,n)$ �~$T(x,n-1)$
��������� ��������� � ������� ���� ������� (����������
������ ������� ��� ���� �������� ������ ������ �� ����������
�������), ��~$T(x,n)\hm=\star$. ��� �� ������ ������ �����������
�����������, ��������� ��� ��� �����\'��~$n$ ���������� ������� �
�������� ������ ����� ��, ��� � \�� ���������\��\ ����������.
���� ������ �� ����� ���� �������, ��� ���� ������������������
$T(x,0),T(x,1),\dots$ ����� ������, �� � $t(x)$~����������. �
����� ����, ���� ��� ����� ������, �� �������� �������� �����
�ף������. ������, ��� ���� ���������� �������~$n$ �������
�������� ���� � �� �� ������� � ���������� ���� � �� �� ������.
������, ��� ������ ���������, ��� ��� � ������� $K_n$~��������� �~$K$.
������� ��������� ���������� ����� ����������� (� ���
�� �������).
        %
\end{proof}

\begin{problem}
        \label{computable-real-4}%
�����ģ���� � ������~\ref{computable-real} (�.~\pageref{computable-real})
����������� ����������� ��������������� �����
����� �������������� �������������� ������ ���������~$A$. ��������,
��� ����� $\alpha$ �������� $\bfnull'$\� ���������� ����� �
������ �����, ����� ��� �������� �������� ����������
������������������ ������������ �����.
        %
\end{problem}

\section{����������� ���������}\label{incomparable-sets}

����������� ���������� �� ��������\index{���������� �� ��������}
(��������, ��� $A$~��������
�� �������� �~$B$, ���� ��������� $A$~��������� � �������� ���~$B$)
����� ������������� ��� ������ ���������� ������ ����������
��������� �������� \�� �� ���������\��. (����~$A\hm\leqT B$, ��
������ ���������� ���������~$A$ � ��������� ������ �����, ���
������ ���������� ���������~$B$.)

��������� ��������� ������������ ��������, ��������� � �����
��������������. ��������, ���������� �� ����� ������� � ����
������ ����������, �� ���� ����� ���������~$A$, ���~$B\hm\leqT A$
��� ������ ���������~$B$? �����, ��� ����� ������,
�������������: � ���������������� ������������~$A$ ���� ����
���� ������������ ��������� (� ���� $A$\� ������������
$A$\� ������������ ���������)\� ��������� ��� ��������� �������
������� ������ ����������. (����� ����� ��������, ��� ���������
��������� �������� �ޣ���� �����, �� ��� ����� ���������~$A$
��������� ���� $A$\� ���������� �������� �ޣ���.)

������, ����� ����������� ������ �����: ����� �� ��� ���������
��������?
�����������, ��� ���, ��� ���������� ��������� �������,
���������� ����� � ������.

\begin{theorem}
        \label{kleene-post-theorem}%
���������� ��� ���������~$A$ �~$B$, ��� �������~$A\hm{\not\leqT} B$
�~$B\hm{\not\leqT} A$\index{����������� �� �������� ���������}.
��� ��������� ����� �����
$\bfnull'$\� �����������.
        %
\end{theorem}

\begin{proof}
        %
���������~$A$ �~$B$ ������ ������������� ����� �����������:
������� ���������, � ������� ���\-��\-�\-��\-Σ� $B$\� ������, ��
��������� ���������~$A$, � ������� ���������, � �������
��������Σ� $A$\� ������, �� ��������� ���������~$B$.

����� �������, ������� �ޣ���� ����� ����������
(��������� ����
�ޣ���� ����� ��������). �� ����� ����������� ��
�� �������, ������
�� ������ ����\� ��������� ���������� ���������� ����������, ��
��� � ���� ������������ �� �����. ����� ������� ���� �����
����������� ��������� ��������~$A$ �~$B$ �� ��������� ��������
������������ ����, ������������� ���������� ��� �������������
����������. �� ��������� ���� ��� ������� ����� ������, � ��� �����\� �
������� ��������� ��� ���������~$A$ �~$B$, ���������������
���� �����������. ��� ����������� ����� $\bfnull'$\� ����������,
��� ��� �������������� ��������� �����
$\bfnull'$\� �����������.

������ ����������� ����� ��������. ����ף� \emph{����������}\index{��������}
�������, ������� ���������� �� ��������� (��������) ���������
������� ������������ ���� � ��������� ��������~$0$ �~$1$. �����
��������, ��� ��������� $A$~\emph{�����������} � ����������~$a$, ����
������������������ ������� ���������~$A$ ����������~$a$. �������
�������, ��������������� � ������ ���������� ��������
������̣���� ��������� ��������� �� ��������� �������
������������ ����.

���� ��������~$a_2$ ���������� ��������~$a_1$ (�� ���� ������̣�
�� ������� ������� � ����������� ������� �������� �� �������),
��, ��������, ��������������� � ��� ����������� ������
����������� �� ���������.

\lemma{�����.} ����� $a$ �~$b$\� ��� ���������, � $p$\� ���������,
���������� ������ ������� ���������.
����� ����������
�����������~$a'$ �~$b'$ ���� ���������� � ����� ���������:
�� ��� ����� ��������~$A$ �~$B$, ������������� �~$a'$ �~$b'$,
���������~$p$, ���� ������ � ������������������ ������� ���~$B$,
�� ����� ��������� ���������~$A$.

������� ��� �����, ����� �����ң��� ������������� ��� ���������
� �������������, ��� �� ���� �� ��� �� ���������~$A$
������������~$B$. ���� ��� ���� ����������~$A$ �~$B$ �
���������� ���� �����, �� ������������ ����� �������������, ���
�� ���� ��������� �� ���������~$B$ ������������~$A$.

(���������. ��������, ����� ������������, ���~$a'$ �~$b'$
�������~$a$ �~$b$\� �� ������ �����
������������ ��������. ����� � ������� �� ������� �����������
������������������, ����������
������������������� ��������� ���� ������� ��������. �������, ���
�� �����������: ���� � ������� ����� ��������� ��������
���������\� ����ͣ� ����� ���������, � ���� �������������.)

����, ��� ���������� ��������~$A$ �~$B$ �������� �������� �����.
(� ������� � $\bfnull'$\� ������������ �� �ݣ ���Σ���.)

� ������������ ����� ���������~$A$ �~$B$ ������ �������������,
������� � ����������� ����� ��������������. ��������� ���������
�����~$x$, ������� �� ������ � ������� ����������� ���������~$a$,
� ������� ���� ������: ���������� �� ����� ���������~$B$,
������������� � ����������~$b$, ��� ����� ������������� ���
������������������ ������� � ���������~$p$ ��� ��������� ���� ��
�����~$x$ �����\� �� �� ������� \�� ��\��\ � \�� ���\��. ����
������ ��������� ���, �� ������ ���������� �� � ���\� �����������
����� ����� ������, ���� ������ ��������~$a'\hm=a$,~$b'\hm=b$.

����� ����� ���������~$B$ ����������. ��������� �� �������
���������~$p$ �� �����~$x$ ��� ����� ���������~$B$.
������ ��� ������ ���� �����,
��������� ����� ��������� �������� ����� ��� �������� ������������������
������� ���������~$B$. ����ͣ� ��������~$b'$, � ������� $B$~�����������,
� ������ ���������� �������, ����� ������� � �������������
��� �� �����, � ������� ���������� ���������~$p$. �����
���������~$p$ ����� ������ ��� �� ����� ����� �� ������
��� ���������~$B$, �� � ��� ����� ��������, �������������
�~$b'$. �������� ����������, ����� ���� ����� ��� ��������,
��� ����� �������, �������~$x$ � ������� �����������~$a'$ �
������~$a'(x)$ �������������� ����� ������.
        %
����� ��������.

�������� ���� �������� ����������� �������, ����������� �
$\bfnull'$\� ������������, ��� ���� ���� ���������, ���
����������~$a'$ �~$b'$ � �������������� ����� ����� �������
$\bfnull'$\� ���������������. �������� ������ �����\� �����
�� ���������������� ��� �������������� ����� ������. �������,
��������� ��������� ��������� ��������� ��������~$B$,
������������� � ����������~$b$, ����������. �� ��� � ��
���������\� ���� ������ ������������� ��� ��������
������ ���������~$p$. ����� ��� ������ ������ ��� �� ��������
�~$b$ �����, �������� ������������� �� ��� ����������� �
����������� �� ���� ������������. ���������� ����������
������ ���������, � ������ �������
� ���, ���������� �� �����
\�� ��\��\ ��� \�� ���\��\ ���� �� �����\� �� �����. � ����
������ ����� ����������������� ��� ������ � ���, �����������
�� ��������� ��������� (� ������, ���������, ���������������
����������� ��� ����� � �����������������, ��� ������ �� �����
�� ��� �������� ����� \�� ��\��\ ��� \�� ���\��).

��� ��������� � ��������� �������������� �������.
        %
\end{proof}

������� ����� ������ ������ � ���, ���������� �� �� ������
$\bfnull'$\� ���������� ����������� �� �������� ���������, �
������������ ����������� �� �������� ���������. ��� ��������
(��� ���������� \emph{�������� �����}\index{��������!�����})\index{����� ��������}
���������� ������ ������������ ��������� �������� � ������� ���������
        \glossary{��������@\��������}%
        \glossary{��������@\��������}%
        \glossary{����@\����}%
����\'��; ���������, ��� ��� ���������� ������������ ����������� ��������
��� ������������ ���� � ��� �� ������,
������� ������� �������� \�� ����� ����������\��.
