% �������� ���������� 19.04.2000

\chapter{��������� � ��������}\label{chapt03a}%
\index{���������}

\section{������� ������������� �������}\label{chapt03a-1}

��������, ����������\index{���������� �������} ���� ���������� �������
���������. ��� ����
��� ����������� ������� \�� �����������\��\ � ��� ������, ��� ��
���������� ���� ������� ����� �������������� �������� ���������
�� ����������. � �������� ����� ���������������� ��� �����
�������� �� ���� �����������, ��������������� ���� ����������
��������, � ������� ��������� � ������������ �������
\�� \verb|return (f(g(x)))|\��.

������ �� ����� �������� �� � ���������� (����� �� ��������� �
������ ����� ����������������), � � ������� �������. ��� ����� �
��� ���� ��������. ������, ������ ������������� �������~$U$
��� ������ ���������� ������� ������ ��������� ������
��������� ����� ������: �����~$n$ �������� �������
�������~$U_n\colon  x\hm\mapsto U(n,x)$.

������ \emph{����������}\index{���������} (����� �����, \emph{�����������
����������}\index{����������� ���������}\index{���������!�����������})
������������� ���������~$\calF$ ��������
����� ������̣���� �����������~$\nu\colon \bbN\hm\to\calF$,
������� �������� �������� ���� �ӣ ���������~$\calF$.
����~$\nu(n)\hm=f$, �� �����~$n$ �������� \emph{�������}\index{�����}
�������~$f$.
����� �������, ������ ������� ���� ���������� ������ ���������
���������� ������ ������� ������ ��������� (� ��������
������������� ��� ����� ������).

���� ����\� �������������� � �������� ����� ��\-����\-��\-���: (���
��������� �������� �� ��������� ���������� �������) ����������
��������, ������� �� ����� ���� ������� ���������� ������� ����
��������� ����� �� ����������.

������ ����� �� ���������, ����� ������������� �������, ��������
���������\index{���������}, ���� ����������. (����� ��������� ��������
\emph{�����������}\index{���������� ���������}\index{���������!����������}.)
������ ����� ������� ����: ��� �����������,
����� ��������� ����, ��� �������,
\emph{�������}\index{������� (ǣ������) ���������}%
\index{���������!������� (ǣ������)} (\emph{ǣ�������}).

����� $U$\� ����������
���������� ������������� ������� ��� ������
�����������
���������� �������
(������ \�� $k$-������� �������\��\ ��������
\�� ������� $k$ ����������\��).
� �������� \emph{�������}\index{�������
������������� �������}
������������� ��������, ���� ��� ����� ���������� ���������� �������~$V$
���������� ����� ������̣���� ����������
�������~$s(m)$, ��� �������
        $$
V(m,x) = U(s(m),x)
        $$
��� ����~$m$ �~$x$ (��������� ����������, ��� ������,
� ��� ������, ��� ���� ��� �������� �� ����������,
���� ���������� � �����).


������� �������, $V_m\hm=U_{s(m)}$, �� ���� �������~$s$ ���� ��
$V$\� ������ ��������� ������� ��������� $U$\� ����� ��� �� �������.

\begin{theorem}
        \label{goedel-numbering-exists}%
���������� �������
������������� �������.\index{������� ������������� �������}
        %
\end{theorem}

\begin{proof}
        %
(������ ������.) �������, ��� ��������� � ��������������
�������~\ref{universal-function} (�.~\pageref{universal-function})
����������
������������� ������� ���� ������� ������������� �������.
��������, ��� �� ����������� ��� ��������� $p_0,p_1,p_2,\dots$
������\� �� ������������� ����� ����������������\index{����
����������������} � �������
����������� �� ���� � ��������~$U(n,x)$ ������ ����������
���������� ���������~$p_n$ � �����~$x$. ����� ������ ����
�����\� �� ������ ���������� �������~$V$ ���� ����������. ��� ����
�� ������ ������������~$m$ �������� ��������� �������~$V_m$, ��
���� �������, ������� ���������, ���� �~$V$ ������������� ������
�������� ������~$m$. ����, ��� ����� ��������� (� �����������
������ ����������������) �������� �����\� ����
������ � ��������� ���~$V$ �������� ������ �������� ��
����������� ��������� (��� ������������ ��������� ���~$V$ �
�������� ������������, � � �������� ��������� ��������~$V$ �
������������� ������ ����������).

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

������� �������, ��� ���������� ���������� ������� �ң�
����������, ������������� ��� ������ ���������� ������� ����
����������\index{������������� ������� �ң� ����������}, �� ����
����� �������~$T$, ��� ��� ��������
������� ��������� ����� �������
$T_n(u,v)\hm=T(n,u,v)$ ����������� ���
���������� ������� ���� ����������.

����� ������� ����� ��������� ���. ��������� ���������
���������� ��������� ���\index{��� ���������}, �� ���� ����������
������� �����������
������������ $\langle u,v\rangle \hm\leftrightarrow [u,v]$
�����~$\bbN\hm\times\bbN$ �~$\bbN$; �����~$[u,v]$,
��������������� ����~$\langle u,v\rangle$, �� ����� ��������
������� ���� ����\index{�����!����}. ���� ������ $R$\� ����������
  ����������
�������������
������� ��� ���������� ����������� �������, ��
  ����������
�������~$T$,
������̣���� �������� $T(n,u,v)\hm=R(n,[u,v])$, �����
������������� ��� ���������� ���������� �������. � ����� ����, �����
$F$\� ������������ ���������� ������� ���� ����������.
���������� ���������� ����������� �������~$f$, ������̣����
������������ $f([u,v])\hm=F(u,v)$. ��������� $R$~������������,
���ģ��� �����~$n$, ��� �������� $R(n,x)\hm=f(x)$ ��� ����~$x$.
��� �����~$n$ ��������� ���������
$T(n,u,v)\hm=R(n,[u,v])\hm=f([u,v])\hm=F(u,v)$, � ������ $n$\�
�� ������� �������~$T$ ��������� �~$F$. ����, �������������
������� �ң� ���������� ���������.

������ ���������� ţ ��� ����������� ������� �������������
�������~$U$ ���� ����������. ����������� ������, �� �������
������~$U$ ��� ������ ���������� ������� ���� ����������, �
��� ����� $U$~������ �������. ��������� ������, �������
$U([n,u],v)\hm=T(n,u,v)$ � ��������, ��� �������~$U$ ����� �������.
�����
  ����������
�������~$V$ ���� ����������
����������� ����� ������� �������~$T$: ����� �����
�����~$n$, ��� $V(u,v)\hm=T(n,u,v)$ ��� ����~$u$ �~$v$.
����� $V(u,v)\hm=U([n,u],v)$ ��� ����~$u$ �~$v$ � ������
�������~$s$, ������̣���� ��������~$s(u)\hm=[n,u]$, �������������
����������� �� ����������� ������� ������������� �������.
        %
\end{proof}

���������, ��������������� ������� ������������� ��������,
��������
\emph{��������},\index{������� (ǣ������) ���������}
     \index{���������!������� (ǣ������)}%
��� \emph{ǣ��������}.

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

\begin{theorem}
        \label{number-of-composition}%
����� $U$\� ���������� ������� ������������� ������� ���
������ ���������� ������� ������ ���������. ����� ����������
����� ������̣���� �������~$c$, ������� �� �������~$p$ �~$q$
���� ������� ������ ��������� ���� �����~$c(p,q)$ �� ����������%
\index{���������� �������}:
$U_{c(p,q)}$~���� ����������~$U_p \hm\circ U_q$, �� ����
        $$
U(c(p,q),x) = U(p, U(q,x))
        $$
��� ����~$p$, $q$ �~$x$.
        %
\end{theorem}

\begin{proof}
        %
���������� ����������
        ����������
�������~$V$, ��� �������
$V([p,q],x)\hm=U(p,U(q,x))$. �� ����������� ������� �������������
�������, ���ģ��� ����� ����� ������̣���� �����������
        ����������
�������~$s$,
��� $V(m,x)\hm=U(s(m),x)$ ��� ����~$m$ �~$x$. �����
$V([p,q],x)\hm=U(s([p,q]),x)$ � ������ �������~$c$, ������̣����
������������ $c(p,q)\hm=s([p,q])$, ����� �������.
        %
\end{proof}

�������� ��� �������������� �����������. ����������� �������
������������� ������� �������, ����� ��� ������ ������� �����
����������������, ��� �������� ������� ����������
�������������~$V$, ����������� �� ���������� ����������~$s$ �������� �����
����� � ��������� �����~$U$. (��� ��������� �� �� ���������
��������� � �� ������ � ������������� �����~$m$ ��� $U$\� ���������
�������~$U_m$.)

������ ���������� ����� ������ ����������������, ��� �������
����~$\langle p,q \rangle$ ����������� ���������� ����������
������� � $U$\� �����������~$p$ �~$q$. �� �������, ����� ���������
����� �������������� ������������� � $U$\� ���������, ��� �
����������� ��������.

���������, ��� ����� � �������� � �������~\ref{number-of-composition}
�����������:

\begin{problem}
        %
����� $U$\� ����������
        ����������
������������� ������� ��� ������ ����������
������� ������ ���������. ���� ���������� ����� ������̣����
�������, ������� �� ������� $p$ � $q$ ���� ������� ������
��������� ���� �����\� ���� ����� �� ����������, �� �������
$U$ �������� �������. (��������: ��������, ��� ��~$k$ ����� ��������������
�������� $U$\� ����� �������~$x\hm\mapsto [k,x]$.)
        %
\end{problem}

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

\begin{problem}
        %
������� ����������� ������� ������������� �������\index{�������
������������� �������} � �����
��������� ������������� \�� �����������\��~$s$ ���� ���
������������� ���������� �������~$V$ (� �� ��� �����, ���
������). ��������, ��� ����� ����������� ������������ �������.
(��������: ����� ������� ����� ������������ ���������� �
�������������, \�� ���������\��\ � ��� ����� ������
������������� �������.)
        %
\end{problem}

\begin{problem}
        %
����� $U$\� ������� ������������� �������. ��������, ��� ���
����� ���������� �������~$V(m,n,x)$ ���������� ����� �����
������̣���� ���������� �������~$s(m,n)$, ���
$V(m,n,x)\hm=U(s(m,n),x)$ ��� ����~$m$, $n$ �~$x$. (��������:
����������~$m$ �~$n$ � ����.)
        %
\end{problem}

\section[���������� ������������������ �������]
{���������� ������������������\\���������� �������}\label{chapt03a-2}

����� ���� ��������� ������������������ $f_0,f_1,\dots$
���������� ������� ������ ���������. �� ����� ������� �����
��������� \�� ������������������~$i\mapsto f_i$
���������\��. ��� ����� ������� ����� ���������:

\begin{itemize}
        \item
����� �������� ��� ������������������ ����������, ����
�������~$F$ ���� ����������, ��������
��������~$F(i,n)\hm=f_i(n)$, �������� ����������.
        \item
����� �������� ��� ������������������ ����������, ����
���������� ���������� ������������������ ����� $c_0,c_1,\dots$,
��� ������� $c_i$~�������� ����� �� ������� �������~$f_i$.
        %
\end{itemize}

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

\begin{theorem}
        %
���� ��������� �������� ���������� (�� ���� ���������������
������������� ������� ���������), �� �� ������� �����������
������� ������. ���� ��������� �������� � ���� ��
�������, �� ��
������� ����������� ������� ������.
        %
\end{theorem}

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

\begin{proof}
        %
���� $U$\� ���������� ������������� �������, �
������������������~$i\hm\mapsto c_i$ ���������, �� �������
$F\colon \langle i,x\rangle\hm\mapsto f_i(x)\hm=U(c_i,x)$ ��������� ���
��������� ����������� ����� ���������� ������� � ������.

��������, ���� �������~$F$ ���������, � ������������� �������~$U$
�������� �������, �� �������\� ����������, ������������ ��
����������� ������� ������������� �������, ��� ��� � ���� ��~$i$
���� �� ������� �������~$f_i$.
        %
\end{proof}

\begin{problem}
        \label{computable-real-3}%
����� ����������� ������� ������������� ������� ��� ������
���������� ������� ������ ���������. ����� ��������� ���������
���������� �������������� ����� � ������������ � ������������ ��
�.~\pageref{computable-real}: ������� �����~$\alpha$ ��������
����� ����� ����� �������, ������� �� �������������
$\varepsilon>0$ ���� $\varepsilon$\� ����������� � $\alpha$.

        (\textbf{�})~%
��������, ��� ���������� ��������, ������� �� ����� ���� �������
���� ���������� �������������� ����� ���� (���������) ����� ��
�����.

        (\textbf{�})~%
��������, ��� �� ���������� ���������, ������� �� ������ ������
������ ����������� ��������������� ����� �������� �� ������,
����� �� ��� ����� ����.

        (\textbf{�})~%
��� �� ������ � ������~\ref{computable-real}, ������ ����������
�������������� ����� ����� ���������� ���������� ����������.
��������, ��� ��� �� ����� ��� ���������, ������� �� ������
������ ������ ����������� ��������������� ����� ���� �����
���������� �������, �������� ��� ���������� ����������.
        %
\end{problem}

\section{������� ������������� ���������}\label{chapt03a-3}%
        \index{������� ������������� ���������}


�� �������� � ���������, ������������
���������~$W\hm\subset\bbN\hm\times\bbN$ ����������
\emph{������� ������������� ������������
����������}\index{������� ������������� ���������} (��� ������
���� ������������ �����������~$\bbN$), ���� ��� ������ �������
������������� ���������~$V\hm\subset\bbN\hm\times\bbN$ ���ģ���
����� ����� ������̣���� ���������� �������~$s\colon
\bbN\hm\to\bbN$, ���
        $$
\langle n,x\rangle \in V \Leftrightarrow \langle s(n),x\rangle \in W
        $$
��� ����~$n$ �~$x$. (��������, ��� �� ����� �������� �������
���������������.)

��� � ��� �������, ����� ������� � ����������. ������ ���������
$U\hm\subset\bbN\hm\times\bbN$ ������ ��������� ����������
��������� ����������� ������������ ����: �����~$n$ ��������
������� $n$\� �� ������� $U_n=\{x\mid \langle n,x\rangle\in
U\}$. ������������ ������������ ���������~$\bbN\hm\times\bbN$
������ ��������� ���������� ��������� ������������ �����������
������������ ����; ����� ��������� �������� \emph{�����������}.
        \index{���������� ���������}%
        \index{���������!����������}%
������������
��������� $W\hm\subset\bbN\hm\times\bbN$ ������������, ����
� ������ ����
������
������������ ������������ ������������ ���� ����� $W$\� �����;
��� �������� ������� ����� � ������ �����, �����
����� ���������� ���������~$V$ (������ ��������� ������������
��������)
��������� �������� � $W$\� ��������� �
��� ������, ��� $V_n\hm=W_{s(n)}$ ��� ��������� ����������
�������~$s$ � ��� ����~$n$.

\begin{theorem}
        %
���������� ������� ������������� ������������\index{������� �������������
���������}
���������~$W\subset\bbN\hm\times\bbN$.
        %
\end{theorem}

\begin{proof}
        %
��� ������� �������� ��������� ���������� ������ �����������:

\lemma{�����.} ������� ����������� ������� ������������� ������� ��� ������
���������� ������� ������ ��������� �������� ������� �������������
���������� ��� ������ ������������ �����������~$\bbN$.

�������������� �����. ����� $U$\� ������� �������������
�������, � $W$\� ������� ţ �����������.
�����~$V\hm\subset\bbN\hm\times\bbN$\� ������������
������������ ���������. ���������� ���������� �������~$G$ � ��������
�����������~$V$. ��������� �������~$U$ �������� �������, ���ģ���
����� ������̣���� ���������� �������~$s\colon \bbN\hm\to\bbN$,
��� ������� $G_n\hm=U_{s(n)}$ ��� ����~$n$. ����� ����� � �������
����������� �������~$G_n$ �~$U_{s(n)}$, �� ����~$V_n\hm=W_{s(n)}$.
        %
\end{proof}

\begin{problem}
        %
��������� ������� ������������� ��������� ���������������,
��������� ������������� ������������~$\bbN^3$ (�� ��������
� ���� �����ģ���� ����������� ������� ������������� �������).
        %
\end{problem}

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

\begin{theorem}
        %
����� $W\hm\subset\bbN\hm\times\bbN$\� ������� �������������
������������ ���������. ����� �� $W$\� ������� ���� ������������
�������� ����� �������������� �������� ����� �� �����������\index{�����������
������������ ��������}:
���������� ����� ���������� ����� ������̣���� ������� ����
����������~$s$, ���
        $$
W_{s(m,n)} = W_m \cap W_n
        $$
��� ����� ���� $m$ � $n$.
        %
\end{theorem}

\begin{proof}
        %
���������� ���������~$V\hm\subset\bbN\hm\times\bbN$, ������̣����
���:
        $$
\langle [m,n], x\rangle \in V \Leftrightarrow
                 x \in (W_m \cap W_n)
        $$
(����� ���������� ������ ���������� ����� ����) � �������� � ����
����������� �������� �������������� ���������.
        %
\end{proof}

��� � ��� �������, ������� ������������ ������������������
������������ �������� ����� ���� ���������� ������: �����
������� ���������� ������������������ $V_0,V_1,\dots$ �������
������������� ������������� ���������~$V$, � ����� ���������,
����� ��~$i$ ����� ���� �������������� ������� ���� �� �������
$i$\� �� ����� ������������������ � ������� ���������. ���
����������� ����������� (�������������� ��������� ����������
����������� ��� �������).

