% ����������� �������� 20.04.2000
\chapter{������� � ����������� �����}\label{chapt05}%
        \index{����������� �����}%

\section[����������� ����� � ��������� ���������������]
{����������� ����� � ���������\\ ���������������}\label{chapt05-1}

\begin{theorem}
        \label{fixed-point}%
����� $U$\� ������� ���������� ������������� ������� ��� ������
���������� ������� ������ ���������, � $h$\� ������������
����� ������̣����
        ����������
������� ������ ���������. ����� ����������
����� �����~$n$, ���~$U_{n}\hm=U_{h(n)}$, �� ����~$n$ �~$h(n)$\�
������ ����� �������.
        %
\end{theorem}

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

\begin{proof}
        %
�� ����� ����������� �� �������� � ����������� ����������
�������, �� ������� ����� ������̣����� ����������� �����������
(�����~\ref{chapt02}).

���������� ������������ ��������� ��������������� (������� ��
����� ����������~$x\hm\equiv y$) �� ��������� ����������� �����.
�� �������, ���
��������� ��� �������� ����� ��������� �� ����� �����������
������������:
        %
\begin{itemize}
        \item
��� ������ ���������� �������~$f$ ���������� ����� ������̣����
���������� �������~$g$, ���������� ţ $\equiv$\� ������������
(��� ��������, ��� ����
$f(x)$~���������� ��� ���������~$x$, ��~$g(x)\hm\equiv f(x)$).
        \item
���������� ����� ������̣����
        ����������
�������~$h$, �� �������
$\equiv$\� ����������� ����� (�� ���� �������, ���
�������~$n\hm{\not\equiv} h(n)$ ��� ����~$n$).
        %
\end{itemize}

���� $x\hm\equiv y$\� ��������� ���������~($x\hm=y$), �� ������ ��������
��������� (�������, ��������,~$h(n)\hm=n\hm+1$), ������� �� ��������� ������.
������� � ����������� ����� ���������, ����~$x\hm\equiv y$ ��������
���~$U_{x}\hm=U_{y}$ ($x$ �~$y$\� ������ ����� � ��� �� �������). � ����
������ ��������� ������ ��������, ��� �� ������ ��������, � ������
�� ��������� ������.

������ ��������� ������ ��������? ����� $f$\� ������������
���������� ������� ������ ���������. ���������� �������~$V(n,x)\hm=U(f(n),x)$.
��������� $U$~�������� ������� �������������
��������, ���ģ��� ����� ������̣���� �������~$s$, ���
�������~$V(n,x)\hm=U(s(n),x)$ ��� ����~$n$ �~$x$. ��� ������� � �����
������� $\equiv$\� ������������. � ����� ����, ����
$f(n)$~����������, �� $s(n)$~����� ������ ������� ��� �� �������,
��� �~$f(n)$.
(�������, ��� ���� $f(n)$~�� ����������, �� $s(n)$~����� �����
�� ������� ����� �� ������̣���� �������.)

��� ���������� �������������� ������� � ����������� ����� �������� ���������,
��� ��������� ��� �������� ���������
��������������� �����������. ��� �������� ��� ��, ��� � �������~\ref{diagonal}
(������~\ref{diagonal-construction}).
����ͣ�
        ����������
�������~$f$, �� ������� �������
���������� ������� �� ����� ���������� ����� (��������,
������������ �������~$x\hm\mapsto U(x,x)$ ��� ���������
        ����������
�������������
�������~$U$). �� ������������� ���������� ����� ������̣����
        ����������
$\equiv$\� �����������~$g$ �������~$f$.
���������� �������~$t(x)\hm=h(g(x))$,
���~$h$\�
        ���������� ����� ������̣����
�������, �� �������
$\equiv$\� ����������� �����. ����� $t$ ����� ����� ����������
��~$f$. � ����� ����, ���� $f(x)$~����������, �� $f(x)\hm\equiv
g(x)\hm{\not\equiv} h(g(x))\hm=t(x)$, � ������~$f(x)\hm\ne t(x)$. ���� ��
$f(x)$~�� ����������, �� ���� ���� ��� �� ���� ��� ��������~$f(x)$ �~$t(x)$.
        %
\end{proof}

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

\begin{theorem}
        \label{fixed-point-2}%
����� $U(n,x)$\� ������� ���������� ������������� ������� ���
������ ���������� ������� ������ ���������. ����� $V(n,x)$\�
������������ ���������� �������. ����� �������~$U$ �~$V$
��������� �� ��������� �������: ���ģ��� �����~$p$,
���~$U_{p}\hm=V_{p}$, �� ����~$U(p,n)\hm=V(p,n)$ ��� ������~$n$.
        %
\end{theorem}

\begin{proof}
        %
��� ��� �������~$U$ �������� �������, ���ģ� ����� ����� ������̣����
        ����������
�������~$h$, ���~$V(n,x)\hm=U(h(n),x)$ ��� ����~$n$ �~$x$. ��������
����� � ��������~$p$ ����������� ����� �������~$h$.
        %
\end{proof}

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

����������� ���������� ������� �����ģ���� ����������� �
����������, ��� �������� ����������� �����. ��� �����������
������~$U(n,x)$ �� ����� ������~$[n](x)$ � ������ ��� \��
��������� ���������� ���������~$n$ � �����~$x$\��;

����������� ���������� � ������������ \�� ������������\index{������������
�������}\index{�������!������������}\��\
�������~$U(x,x)$, ������� ������ ����� �������� ���~$[x](x)$
(��������� ���������� ���������~$x$ � ����). ����� �� ������ ţ
����� ������̣���� $\equiv$\� �����������. ��� �������� ���.
���������~$[[x](x)](y)$ ��������� ������� �� ���� ����������. ��
����������, ��� $U$~���� ������� ������������� �������, �
������� ����� ���������~$g$, ��� $[[g](x)](y)\hm=[[x](x)](y)$ ���
����~$x$ �~$y$. ��� ���� $[g](x)$~���������� ��� ����~$x$. �����
�� ����� ����� ����������� ����� ���������~$h$. �� �������������
����������~$[h]([g](x))$. ��� ��������� ��������� ������� ��~$x$,
� ������ ���������� ���������~$t$, ���
�������~$[t](x)\hm=[h]([g](x))$ ��� ����~$x$. ��� ��������� ���������
�� ����~$x$, ��������� ������~$h$ �~$g$. ������ �����������
������ �����~$[g](t)$. ����� ��������� � ����, �� ������
���������, ��� $[[g](t)](x)\hm=[[h]([g](t))](x)$ ��� ����~$x$. �
����� ����, �� ��������~$g$ �����~$[[g](t)](x)\hm=[[t](t)](x)$.
��������� �����������~$t$, ��� ��������� ����� ���������� ���
$[[h]([g](t))](x)$\� ��� ��� ��� � �����������.

\section{���������, ���������� ���� �����}\label{chapt05-2}%
         \index{���������, ���������� ���� �����}

������������ �������� ���������� ������� � ����������� �����
�������� ����� ţ ���������: ���������� ���������, ���������� (��
����� �����) ���� ����������� �����. � ����� ����, ���� �� �����
��������� �� ����, �� ��������������
        $$
 p \mapsto (\text{���������, ������� �� ����� ����� ��������~$p$})
        $$
�� ����� �� ����������� �����.

��������� ������, ��� ��������� ����� �������� ���:

\begin{theorem}
        \label{fixed-point-3}%
����� $U(n,x)$\� ������� ���������� ������������� ������� ���
������ ���� ���������� ������� ������ ���������. ����� ����������
����� �����~$p$, ���~$U(p,x)\hm=p$ ��� ������~$x$.
        %
\end{theorem}

� ��������������� ��������: ����� $U(p,x)$\� ���������
���������� �������\� ���������~$p$ � ������������ �����~$x$.
(���������: (1)~�� ������������� ����� � ������������������
������; (2)~���� ��������� �� ��������� ������, �� �������, ���
��������� �� ������̣�, ���� ���� �� ����������� ����� ���\� ��
�������.) ����, ��� �������~$U$ ����� ������� �������������
��������. ������� � ��� ����� ��������� ���������������� ������
��� �����������; ������� ���������~$p$, ������� ��� ����� ����� ��
������ ����~$p$.

����, ��� ��� ����������� ��������� ��� ������ �����
����������������; ��, ��� �� ��������� ���� �������, ���� ��
������.

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

\begin{problem}
        %
��������, ��� ���� ��� ���������
�������\� ��������� $P$ � $Q$ � ������ ����������:
���������~$P$ �������� ����� ���������~$Q$, � ���������~$Q$
�������� ����� ��������� $P$. (���� �� ��������� ��������
����� $P$ � $Q$, �� � ��������~$P$ �~$Q$ ����� �����
���� � �� �� ���������, ���������� ���� �����.)
        %
\end{problem}

������� ���� ��������� �� �������, ���������� ���� �����. (���\�
������� ������ ��� ��������� ����������������.) ��� ������
������� ������������ ���������� �� ������� �����:
        %
\quot{%
        %
���������� ��� ����, ������ ��� � ��������, ����� �����:
\�� ���������� ��� ����, ������ ��� � ��������, ����� �����:\��
        %
}

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

\begin{verbatim}
program selfprint;
 var a:array[1..100]of string;i:integer;
begin
a[1]:='program selfprint;';
a[2]:=' var a:array[1..100]of string;i:integer;';
a[3]:='begin';
a[4]:='for i:=1 to 3 do writeln(a[i]);';
a[5]:='for i:=1 to 11 do begin';
a[6]:='  write(chr(97),chr(91),i);';
a[7]:='  write(chr(93),chr(58),chr(61));';
a[8]:='  writeln(chr(39),a[i],chr(39),chr(59));';
a[9]:='end;';
a[10]:='for i:=4 to 11 do writeln(a[i]);';
a[11]:='end.';
for i:=1 to 3 do writeln(a[i]);
for i:=1 to 11 do begin
  write(chr(97),chr(91),i);
  write(chr(93),chr(58),chr(61));
  writeln(chr(39),a[i],chr(39),chr(59));
end;
for i:=4 to 11 do writeln(a[i]);
end.
\end{verbatim}

����� ��� ���������, ������� ����� � ���� ������������ �����
��������� � �� ������:
        $$
\begin{tabular}{cccccccc}
 {\texttt{a}} &
  {\texttt{[}} &
   {\texttt{]}} &
    {\texttt{:}} &
     {\texttt{=}} &
      {\texttt{'}} &
       {\texttt{;}} \\
   $97$ & $91$ & $93$ & $58$ & $61$ & $39$ & $59$
\end{tabular}
        $$
�����, ��� ��� ��������� ����� ��������������, ����� ���,
������, �������� ���� ����� ����� ����ң�\� ������ ������
\verb|write| � \verb|writeln|, ���������� �����, ���� ��������
�������, ������������ ��� � ���� (��� � ������ ������), � �����
�������, ���������� ���� ���� ��� ������ � �������� �������.

������ �ݣ ���� ���, ����� �������� � �������������� ������� �
����������� �����. ����� $h$\� ��������� ��������������
�������\� ��������, � �������� �� ����� ����� ����������� �����.
����� ������� ��������� ��������� ������ ��� �����ģ����,
������� ����� ���������� ���� ����� � ������~\verb|p|, �����
���������~$h$ �~\verb|p|, ������� ��������� ������
������~\verb|q|, � ����� ��������� ������������� ������� ��
������~\verb|q| (��������� � �������� ����� ���������~\verb|q|
���� �������� ���������). �������, ��� ��������� ��� �� �����
����� ��������, ��� ��� ����� �������� � ���� (� ���� ��� ����\�
������ ��� ������ ���, � ������ ��� � ��������) �������������
�������, ���������� �� �������.

����, ��� ����� ��������� ����� ����������� ������
��������������~$h$, ��� ��� ţ ���������� ���������� ����� �
����, ��� ����������� �������� �������~$h$ �� ţ ������, �����
���� ��� �������� �������������� ��� ��������� � ����������� �
�����.

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

\section{��������� ����: �ݣ ���� ��������������}\label{chapt05-3}

���� ��������� ��������� ������ ������ ����������������
�������� �� ��ϣ� ������� ����� �� ����������� ��������
���������, ������� �� �������� ���� �������� �����, ��
���������, ������ �����, �������� �������� ���������
�� �������\index{������}:
\begin{verbatim}
    10 LIST
\end{verbatim}
���� � ���, ��� � ������� ���� �������~\verb|LIST|, �������
�������� ����� ��������� � ����� ���� �������� �������
���������.

������ �����, ��� ������� �����. �� ����� ��������� � ���
���������� ���أ��� � ������������ ��� ���� � �ݣ �����
�������������� ������� � ����������� ����� (������, � �ݣ
����� �������� ���� �� ��������������).

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

������ ���������� ���� ����������������, � ������� ������
������� ������������ ���� ���������� ���������
        %
\begin{verbatim}
   GetProgramText (var s: string)
\end{verbatim}
        \index{GetProgramText, ���������}%
��� ��������� �������� ����� �������� ��������� �
������~\verb|s|. �������� �� ��������� ����������� ���� ����, ������
����� ����������� ���� ������������� ����� �����\� �
������������� ���� ��������� �� ������������ �����, ��� ���
��������������, ����������, �������� ����� ���������.
������� �ݣ ���� ��� � ���������� ����, ��� � ���� �����
���� ����� ���������
        %
\begin{verbatim}
   ExecuteProgram(s: string)
\end{verbatim}
        \index{ExecuteProgram, ���������}%
��� ��������� �������� ���������� ���������, ����� �������
��������� � ������~\verb|s|, ������ ������ ���� ��������� ����
�������� ��������� (��� ������ �� ��������� �����������, \��
��������� ���������~\verb|s| ���������� �������� ������\��). � �
���� ������ �������, ��� ������ ����������� ������������� �����:
�� ������ ���������� ������� ���� �� ���������� ������~\verb|s|
� ������� ������.

��� �����ݣ���� ���� ����������������, ����������, ���������
���������� � ���� � ������� ����� (��������� ����� �������������)
� �������� (��� ��� ����� �� ������������ ������ �������������).
������� ���������� �� ��������� ���������� ������� �������� �������.
����� $h$\� ����� ������̣����
����������
�������, � ������� �� ����� ����� ����������� �����. �������
����������� ţ �������� � ���� ��������� ������ �����:
        %
\begin{verbatim}
function Compute_h (x: string) : string;
begin
  ...
end;
\end{verbatim}
        %
(��� ���� ��� ���� �� ����� ����� �����������.) ������ �������
���������, ���������� ����������� ������ �������~$h$:
        %
\begin{verbatim}
program fixed_point;
   var s: string;
   function Compute_h (x:string) : string;
   begin
     ...
   end;
begin
   GetProgramText (s);
   s := Compute_h (s);
   ExecuteProgram (s);
end.
\end{verbatim}

���������� ���� ��������� ����� �� �������� � ����������
���������, ������������ ����������� � ��� �������~$h$,
��� ��� ��� ����� ����������� ������ �� ����������.

\begin{problem}
        %
����� $h$\� ������������� �������, �� ����~$h(x)\hm=x$.
(�����, ����������, ����� ��������� ����� ţ �����������
������.) ����� ������ ��������� ���� ��� ������ ��� ���������
�����������? (�����: ���������, ������� ������������� �� �����
�����.)
        %
\end{problem}

�� ������ ��� ���������, ��� � ������� ����� � ��������������
���������� \�� �������� ����� ���������\��\ ����� ��������
������� � ����������� �����. �� ����� ���������� � � ��������
����������� � ���������, ������ ���������� ������� � �����������
����� �������� ����� �������������� ���������.

� ����� ����, ����� �� ����� ���������~$p$, � ������� ����
������ \verb|GetProgramText(s)|. ������� ��� ������ ��
�������� ������������~\verb|s := |$t$, ��� $t$\� ���������
��������� ���������. ��������� ����� ���������, ���������
��~$t$. ����ף� ţ~$p(t)$. �������� ������� � ����������� �����,
���������� ����� ��������~$t$, ��� ������� ���������~$t$ �~$p(t)$
������������. ��� ����~$t$ ���������� ���������~$t$
������������ ���������� ţ ������, � ������� � ������ ������
��������� \verb|GetProgramText(s)| � ������~\verb|s|
���������� ����� ��������� $t$\� ���� �� � ������.

������ ���������� ��������, ������ ������� � ����������� �����
���������� �ݣ �������� � ��������. � ����� ����, ��������
������� � ���, ��� �� �������� ��������� ������� ţ �����. �����
���������� ���� ������: �� �� ������ ����� ����� �������
���������, �� � ����� �������� ������ � ţ ������! ������� �����
������������� �������� ������� ������� ������� � ������, ��� ���
�� ����� ������� ��������� ������������� �� ���� ������.
(�������, ��� ���� ��� ����������� �������� � ������ ���������
����� �������������� ������ ����� ����������������, ����������
�� ���� �����.)

\section{��������� ���������}\label{chapt05-4}

\subsection*{����������� ��������� ����������� �����}

�������~\ref{fixed-point} (� ����������� �����) ����������
������������� ���� �� ����� ����������� �����. ����� ������, ���
�� ����� ���� �� ���������� �����: � ������������ ���� �������
���������� ���������� ����� �����~$n$, ��� �������
$U_n\hm=U_{h(n)}$

��� ����� ���������, ��������, ���: ���� �� ����������� �����
���� �� �������� �����, �� ����� ���� �� �������� �������~$h$ �
���� ������ ���, ����� ����������� ����� �� ��������. ����������
����� ����������� � ���, ��� ��� �� ��������� ����������
����������� ����������� ����� (������� ��� ������ �������~$h$
����������� ������������ ���������, ��������� �� ţ �����������
�����). ����� ������� � ���, ���� ��������� ��������������
�������~\ref{fixed-point}. � Σ� ������������ �������
����������� ����� $[g](t)$, � ������� $g$ ����� ������� ���,
����� ��� ţ �������� ���� ������ ������ ����ң� ��������� �����
(�������~\ref{many-numbers}, �.~\pageref{many-numbers}).

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

\subsection*{����������� ����� � ����������}

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

\begin{theorem}
        \label{fixed-point-parameter}%
        \index{�������!� ����������� ����� � ����������}
����� $U$\� ������� ������������� ������� ��� ������
���������� ������� ������ ���������, � $h$\� �����
������̣����
        ����������
������� ���� ����������. ����� ���������� �����
������̣����
        ����������
�������~$n$ ������ ���������, ������� �� ������~$p$
��������� ����������� ����� ��� �������~$h_p$, ��� ���
$U_{h(p,n(p))}\hm=U_{n(p)}$, ���, ������� �������,
        $$
U(h(p,n(p)),x) = U (n(p),x)
        $$
��� ����~$p$ �~$x$ (��� ������, ��� ����� ����� ���� ������������
�� ����������).
        %
\end{theorem}

\begin{proof}
        %
�� ������, ��� ����������� ����� �������� �������������. �������
���� �� ���� ����������� ����� ��� �������~$h_p$, ���������
��������� �� ���������~$p$, �� � ��������� ������ ����������
����� ��������� �������� �� ���������~$p$.

�������, ����� ���� �� ��������� �������� �����������,
����������� ���� ����, �� ��� �������� ��������� (� ���� ��
�� ����� �������������� ������ ����� ��������).
        %
\end{proof}

� ���� ������� �� ������������, ��� ��������� ������� $h_p$
������� �� ����� ������̣���� �������. �� ����� ���� ��� ��
�����������: ��� �������������
        �����������
��������� ����������
�������~$h_p$ (������� �������, ��� ������������
        ����������
�������~$h$ ����
����������) ���������� �����
������̣����
        ����������
�������~$n$ ������
��������� � ����� ���������: ��� ������~$p$ ���� ������� $h_p$
�� ���������� � ����� $n(p)$, ���� $n(p)$ �������� �����������
������ �������~$h_p$.

\begin{problem}
        %
���������, ��� �����ģ���� � ��������������
�������~\ref{fixed-point-parameter} �����������
��� ��� � ���� ������� $n(p)$ � ����� ���������.
        %
\end{problem}

\begin{problem}
        %
��������� ��������� ���� ���������, ��������,
��� �� ����� ���������� ������� $h$ (�������� ����� �������
������������ ������������� ������� ������������� �������) �����
���������� ������� ���������� ����� �����, ������ �� ������� ����
����� ����������� ������ ��� �������~$h$, ���� ������,
��� ��� ������� �� ����������.
        %
\end{problem}

\subsection*{����������� ����� ��� ������������ ��������}

�ӣ ��������� ����� ��� ��������� ����������� �� �������
��������� ������������ ��������\index{�������!� �����������
����� ��� ��������} (���� $W$\� ������� �������������
������������ ���������, �� ������ ���������� ����� ������̣����
�������~$h$ ����� ����������� �����~$n$, ��� �������
$W_n=W_{h(n)}$).

� ����� ����, ���� $W$\� ������� ������������� ������������
���������, �� � ��������� ���������������
        $$
a \equiv b \Leftrightarrow W_a = W_b
        $$
��������� ����������� �� ��������������
�������~\ref{fixed-point}, ��������� ����� ����������
�������~$f$ ����� ���������� ����� ������̣���� $\equiv$\�
�����������.

�������� ���. ��� ����� ���������� ���������
        $$
V = \{ \langle p,x\rangle\mid \text{$f(p)$ ���������� �
          $\langle f(p), x\rangle \in W$}\}.
        $$
����� ������, ��� ��� ��������� ����������� (��������, ��� ����
������� ����������� ���������� �������~$\langle p,x\rangle\hm\mapsto
w(f(p),x)$, ��� $w$\� ���������� ������� � ��������
�����������~$W$). ��� ����~$V_p\hm=W_{f(p)}$, ����
$f(p)$~����������, �~$V_p\hm=\varnothing$, ���� $f(p)$~�� ����������.
���������, ��� $W$ �������� ������� ������������� ����������, ��
������� ����� ������̣���� �������~$s$, ���
�������~$V_p\hm=W_{s(p)}$. ����� �������,~$W_{s(p)}\hm=W_{f(p)}$ ��� ���~$p$,
��� ������� $f(p)$~����������, ��� � �����������.

\begin{problem}
        %
����� $W$\� ������� ������������� ��������� (��� ������ ����
������������
����������� ������������ ����). \textbf{(�)}~��������, ��� ���ģ���
�����~$x$, ��� �������� $W_x\hm=\{x\}$.
\textbf{(�)}~��������, ��� �������� ��������� �����
$x$ �~$y$, ��� ������� $W_x\hm=\{y\}$ �~$W_y=\{x\}$.
        %
\end{problem}


\subsection*{������ �������������}

���������� (���� �� ����� ��������) ���������� ������� �
����������� �����\� �ݣ ���� �������������� �������~\ref{uspensky-rice}
� ��������������
������� ���������� �������. � ����� ����, ����� ���� �������������
��������~$\calA$ ���������� �������, ������� ����� ������������
�� ������� ������� � ������� ���������~$U$.
����� $p$\� �����\� �� ����� �����\� �� �������~$U_p$,
���������� ���� ���������, � $q$\� �����\� �� ����� �����\� �� �������~$U_q$,
�� �� ����������. ����� �������
        $$
h(x)=\left\{
        \begin{aligned}
           &q,\text{ ���� �������~$U_x$ �������� ���������~$\calA$,}\\
           &p,\text{ ���� �������~$U_x$ �� �������� ���������~$\calA$}
        \end{aligned}
     \right.
        $$
����� ���������� �
�� ����� ����� ����������� �����.


\subsection*{���������� ������������� ��������}
        \label{universal-set-isomorphism}%
        \index{����������!������������� ��������}%

�����~$U_1$ �~$U_2$\� ��� ��������� ��� �����������
�����. �� ����� �������� �� \emph{��������� �����������},
        \index{��������� ���������� ���������}%
���� ����� ����� ���������� ������������ (�������)
$i\colon\bbN\hm\to\bbN$ � ����� ���������:
        $$
\langle x,y\rangle \in U_1 \Leftrightarrow
\langle i(x),i(y)\rangle \in U_2.
        $$

\begin{theorem}
        \label{computational-structure-isomorphism}
����� ��� ������� ������������� ��������� ��� ������
������������ ����������� ������������ ���� ���������
���������.
        %
\end{theorem}

\begin{proof}
        %
��� ������ �������� ������� ����� ���� �������� � ��������
�� ����������� ������� ��������� ������������ ��������
(��.~��������� � ����� �������~\ref{chapt03-4}). ��� ��
��������� ���������� ������������ ������ � �������, �� �� �
��������� ��������. � ���������� ������������ �������
�� ����������� ������� ��������� ����� �������� ���:
        $$
\langle x,y\rangle \in U_1 \Leftrightarrow
\langle i(x),y\rangle \in U_2.
        $$
\looseness=-1
�������, ��� ���������� ������������ �� �������
��������� ��������� ���������������: ����
$U\hm\subset\bbN^2$\� ������� ������������� ���������, �
$i\colon\bbN\hm\to\bbN$\� ���������� ������������, ��
��������� ��� $\langle x,y\rangle$, ��� ������� $\langle
x, i(y)\rangle\hm\in U$, ����� �������� �������
������������� ����������. ������� �� ������� ��
����������� ������� ��������� ������������ ��������
����� ������� ����� ���������: ��� ������ ����������
������������ $i$ ���ģ��� ����� ���������� ������������~$i'$,
���
        $$
\langle x,y\rangle \in U_1 \Leftrightarrow
\langle i'(x), i(y)\rangle \in U_2.
        $$
���� ��� ������� �~$i'$ ������� �~$i$, �� ������������~$i$
����� ���������. �� ����� �������� ������� ������� �� �������
� ����������� �����. �� ���� ���� ���� ��������� �����������,
�� ��� ��� ����������\� � �� ������ ������� ������, ���.

������ ����� ���� ��������� �������������� ������� ��
����������� ������� ��������� � ������, ��� �������~$i'$
(ţ �����) �������������� �������� �� ������� $i$. �����
�� ����� ��������� �� ������� � ����������� �����, ��
�������� � ���, ��� ��� ���������� �������� ������ ���
������, ����� �������~$i$ �������� ��������. ������� ��
������ �������������� ����������� �� ������� ��
����������� ���, ����� ��� ���� ��������� �� ������
        ����������
�������~$i$ � ������ ������ �� �����\� �� �������~$i'$;
����� ����������� ����� ������������� ����� ��������.

������������ ��������������� ��������� ������� ��
����������� ������� ���������. ����� �������������� ����
��������������� �����������. ����� $I\colon
\bbN\hm\to\bbN$\� ������������ �������. �����
��������, ��� ��������� $A$ \emph{$I$\� �������������}
��������� $B$, ���� ����~$B$ ���� �����~$A$ ���
�����������~$I$, ����~$A$ ���� ��������~$B$ ��� ����
�����������. (����~$I$\� �������, ��� ��������
�����������.)

����� $U_1$ � $U_2$\� ������������ ������� ���������
������������ ��������, � $I\colon\bbN\hm\to\bbN$\�
���������� �������. ����� ���������� �����
        ����������
�������
$i'\colon\bbN\hm\to\bbN$, ��� ��� ����� $k$ ��������� �
�������~$k$ � ��������� $U_1$ $I$\� �������������
��������� � �������~$i'(k)$ � ���������~$U_2$.

��� ��������� ������� �� ����������� ������� ���������
������������ ��� ��, ��� � ���� �������, � ����� �������~$i'$
����� ���� ���������� ������� �� ������ �������~$I$. ���
��������� ��������� ��������� ���� � ����� �������~$I$, ���
�������~$i'=I$, ��� � �����������.
        %
\end{proof}

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


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

\begin{theorem}
        %
����� $F_1,F_2\colon \bbN\hm\to\bbN$\� ��� ������� �������������
������� ��� ���������� ������� ������ ���������. ����� ���ģ��� �����
���������� ������������~$i$, ���
        $$
F_1(x,y)=z \Leftrightarrow F_2(i(x),i(y))=i(z)
        $$
��� ����� �����������~$x$, $y$~�~$z$.
        %
\end{theorem}

\begin{problem}
        %
��������� �������������� ���� ������� �� �������� � ����������,
��������� ������� �������� �� ����������� ������� ���������
(�.~\pageref{rogers-theorem}, �������~\ref{rogers-theorem}).
        \index{�������!��������}%
        \glossary{�������@\�������}%
        \index{�������� �������}%
        %
\end{problem}
