%&latex --translate-file=win2t2
\documentclass[11pt,a4paper]{article}

\usepackage{inputenc}
\usepackage[russian,english]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{latexsym}
\usepackage{indentfirst}
\usepackage{graphicx}
\usepackage{color}

% \tolerance 8000

\pagestyle{myheadings}

\oddsidemargin=-10mm   \textwidth=180mm 
\topmargin=-5.4mm \textheight=245mm
\topmargin=0mm

\font\pagef=lasx700 at 32pt
\font\bfont=labx2985 at 12pt \def\bff{\bfont}

\makeatletter
\def\@oddhead{\smash{\includegraphics{hilb.3}}%
     \hfil %\LARGE\pagef Десятая проблема Гильберта      
     \hfil\llap{\pagef\the\count0}}
\makeatother

\parskip=\smallskipamount



%\makeindex
\begin{document}


%\binoppenalty=9000
%\relpenalty=9000

\def\mychapter#1{\section*{\hfil\LARGE#1}}
\def\mysection#1{\subsection*{\Large#1}}
\def\medskip{\vskip\medskipamount}

\def\prenum{\llap{\hbox to \parindent{$\blacklozenge$\hfil}}}

\def\lbracket{\delimiter 164608 }
\def\rbracket{\delimiter 168705 }
{
\catcode`\(=13 \catcode`\)=13
\gdef\lbr{\ifmmode\lbracket\else{\rm\char`(}\fi}
\gdef\rbr{\ifmmode\rbracket\else{\rm\char`)}\fi}
\gdef\normalbrackets{\catcode`\(=13 \catcode`\)=13 \let(\lbr \let)\rbr}
}

\long\def\myempty#1{}
\def\task#1{\par\medbreak\textbf{\textbf{\prenum#1.\enspace}}\begingroup
   \normalbrackets 
   \sl\def\par{\endgraf\endgroup\medbreak}\interlinepenalty9999 \ignorespaces}

\def\ui{\fontshape{ui}\selectfont}
\let\pt\it
\def\gen<#1>{\left<#1\right>}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$\mathsurround=0pt #1$}}{}}
\def\defis{\hskip 0em\nobreak-\hskip0em }
% \def\risunok{\refstepcounter{figure}рис.~\arabic{figure}}
\def\myfrac#1/#2{{}^{#1}\!/\!_{#2}}

\let\leq\leqslant\let\le\leq
\let\geq\geqslant\let\ge\geq

\def\rem{\mathop{\rm rem}}
\def\arem{\mathop{\rm arem}}
\def\Elem{\mathop{\bf Elem}\nolimits}
\def\Cantor{\mathop{\bf Cantor}\nolimits}
\def\ElemA{\mathop{\bf ElemA}\nolimits}
\def\ElemB{\mathop{\bf ElemB}\nolimits}

\def\Concat{\mathop{\rm Concat}}
\def\PNotGreater{\mathop{\rm PNotGreater}}
\def\PSmall{\mathop{\rm PSmall}}
\def\Equal{\mathop{\rm Equal}}

\def\AfterP{\mathop{\rm AfterP}}
\def\AfterT{\mathop{\rm AfterT}}
\def\NextP{\mathop{\rm NextP}}
\def\NextT{\mathop{\rm NextT}}

\def\amod#1{\pod{{\rm amod}\mkern 6mu #1}}

%\renewcommand{\baselinestretch}{0.85}
\renewcommand{\labelenumi}{[\theenumi]}

\def\sqclose{\char`\]}
\def\x{\bgroup\catcode`\]=2 \aftergroup\sqclose \color{blue}}

\large
%\boldmath

\mychapter{\boldmath $10^{th}$ Hilbert Problem}

%\mysection{Аннотация}


{\centering\leftskip 0pt plus .4\hsize \rightskip\leftskip

\bf Yu.~V.~Matiyasevich, Ya.~Abramov, A.~Ya.~Belov-Kanel, I.~A.~Ivanov-Pogodaev, A.~S.~Malistov

}

Equations both parts of which are polynomial functions with integer coefficients, and the solutions are to be expressed in integer numbers are quite
 common in mathemetics.

In 1900 David Hilbert [1900] delivered his famous lecture entitled "Mathematische Probleme" before the Second International Congress of Mathematicians.
 This paper contains 23 problems, or, more precisely, 23 groups of related problems, that the nineteenth century left for the twentieth century to
 solve. Problem number ten is about Diophantine equations: 

\begin{quote}
{\bff 10. Determination of the solvability of a Diophantine equation }

\sl
Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according 
to which it can be determined by a finite number of operations whether the equation is solvable in rational integers. 
\end{quote}

Today we read the words ``devise a process'' to mean ``find an algorithm.'' When Hilbert's Problems were posed, there was no mathematically rigorous 
general notion of algorithm available. The lack of such a notion was not in itself an obstacle to a positive solution of Hilbert's Tenth Problem, 
because for any particular algorithm it was always clear that it actually gave the desired general method for solving the corresponding problem. 

During the 1930's, Kurt Godel, Alonzo Church, Alan Turing, and other logicians provided a rigorous formulation of the notion of computability; this
 made it possible to establish algorithmic unsolvability, i.e., the impossibility of the existence of an algorithm with certain properties. Soon
 afterwards the first examples of algorithmically unsolvable problems were found, first in mathematical logic itself and then in other branches of
 mathematics. 

Computability theory produced all the necessary tools for tackling the unsolvability of Hilbert's Tenth Problem. The first in a series of papers 
in this direction appeared at the beginning of the 1950's. The continuing effort culminated in a ``negative solution'' of Hilbert's Tenth Problem
 in 1970 by Yury Matiyasevich.

We will follow that proof.


\mysection{A. Diophantine Sets}


We will seek only nonnegative integer solutions of the equations in this problem.

Consider an equality $D(a_1, \dots, a_n, x_1, \dots, x_m)=0$, where $D$ is a polynomial with integer coefficients with respect to all the variables
$a_1$, $\dots$, $a_n$, $x_1$, $\dots$, $x_m$. Suppose that the variables are separated into {\it parameters} $a_1, \dots a_n$ and {\it unknowns} 
$x_1, \dots x_m$.Fixing values of the parameters results in the particular
Diophantine equations that comprise the family. (Note: we consider {\it integer} parameters and coefficients and seek 
{\it nonnegative integer} solutions).

For example, consider $D(a_1, a_2, x)=a_1x^2+a_2x$. The equations (for example) $x^2=0$, $2x^2+6x=0$, $3x^2-17x=0$ are in the family.
In the first case we choose $a_1=1$, $a_2=0$. In the second case we do $a_1=2$, $a_2=6$, in the third case we do $a_1=3$, $a_2=-17$.

The family of Diophantine equations $D(a_1, \dots, a_n, x_1, \dots, x_m)=0$ deines a set $M$ 
consisting of the $n$-tuples ($a_1, \dots, a_n$) of values of the parameters $a_1, \dots, a_n$ for which there are values of the unknowns 
$x_1, \dots x_m$ satisfying the equality $D(a_1, \dots, a_n, x_1, \dots, x_m)=0$.
The number $n$ is called the dimension of the set $M$ and equivalence $D(a_1, \dots, a_n, x_1, \dots, x_m)=0$ is called
a Diophantine representation of $M$.  Sets having Diophantine representations are also called Diophantine. 

The set of even numbers is Diophantine: the equation $2x=a$ has an integer solution if and only if  $a$ is even.
Also, consider the set of pairs $(a, b)$ such that $a$ is odd and $b$ is even and $b>2$. To prove that this set is Diophantine we
should consider the representation $2(2x+1)=a^2(b^3-14)$.


\medskip


\task{A1} Prove that the following number sets are Diophantine:
\\
a) the set of even positive numbers;
\\
b) the set of odd numbers;
\\
c) the set of squares;
\\
d) the set of cubes.

\task{A2} Prove that any system of Diophantine equations are equivalent to some unique Diophantine equation.
(i.e. the sets of solutions are the same.)


\task{A3} Prove that the union and intersection of two Diophantine sets of the same dimension is also Diophantine. 

\task{A4} Suppose that the $n$-tuples set $\mathfrak{M}$ are Diophantine. Consider the $m$-tuples set $(a_1, \ldots , a_m)$ such that
there exist $a_{m+1}, \ldots , a_n$ with $(a_1, \ldots , a_n)\in \mathfrak{M}$. Prove that this $m$-tuples set $(a_1, \ldots , a_m)$ is Diophantine.


It is often more convenient to use, instead of the language of sets, an essentially
equivalent language of properties and relations. For example, instead of saying
that the set of even numbers is Diophantine, one can say that {\it the property is an
even number} is Diophantine. Similarly, instead of considering the set with the
representation $(a_1-a_2)^2=x+1$, one can say that the relation $\ne$ is Diophantine.
More formally, we say that a property $P$ of natural numbers is a Diophantine
property if the set of numbers having this property is Diophantine. Correspondingly,
an equivalence of the form
$P(a) \Leftrightarrow \exists x_1 \dots x_m [D(a,x_1, \dots, x_m)=0]$
is called a Diophantine representation of property $P$.

Similarly, a relation $R$ among
$n$ natural numbers is called a Diophantine relation if the set of all $n$-tuples for which
the relation holds is Diophantine. Correspondingly, an equivalence of the form
$$R(a_1, \dots, a_n) \Leftrightarrow \exists x_1 \dots x_m [D(a_1, \dots, a_n, x_1, \dots, x_m)=0]$$
is called a Diophantine representation of relation $R$.

At last, function $a=F(b_1, \dots b_k)$  is called a Diophantine function if the set of 
all $k+1$-tuples $[a, b_1, \dots, b_k]$ for which the equality $a=F(b_1, \dots b_k)$ holds is Diophantine.



\task{A5} Prove that the following relations are Diophantine:
a) ``greater'' relation  ($a>b$);

b) ``divisibility'' relation ($a$ divide $b$).

c) Consider the set of triples $(a, b, c)$ such that $a$ is a remainder of division $b$ with $c$.
({\bfseries notation: $\mathbf{a=b\ (mod\ c)}$}) Prove that this set is Diophantine.


d) Consider the set of triples $(a, b, c)$ such that
$a=\min\{b \pmod{c}, (c-b) \pmod{c}\}$\linebreak
({\bfseries notation: $\mathbf{a=b\ (amod\ c)}$}) (This is the distance to the nearest integer number dividing by $c$.)


e) Prove that the set of triples $(a, b, c)$ such that $a=\left[\frac{b}c\right]$ is Diophantine.


\task{A6} Prove that the ``relative primality'' relation and  $GCD$ and $LCM$ functions are Diophantine.



\task{A7} Prove that the following sets are Diophantine:
\\
a) the set of all integer numbers which are not squares;
\\
b) the set of pairs $(a, b)$ such that $a$ is not power of $b$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\abs#1{\mathopen|#1\mathclose|}

\section*{Pell equation}

{\bf Definition.} Equation $x^2-dy^2=1, d\in\mathbb{N}$\quad is called {\it Pell Equation}.

\task{A8} Pell Equation.

\removelastskip
a) Solution $(x,y)$ is called {\it nontrivial}, if $y\ne 0$. Let $d$
be a square. Prove that Pell equation has no nontrivial solution.

b) Let $(u_1,v_1)$ and $(u_2,v_2)$ be the solutions of the Pell equation $x^2-dy^2=1$.
So if $u_3+\sqrt{d}v_3=(u_1+\sqrt{d}v_1)\cdot (u_2+\sqrt{d}v_2)$ then $(u_3,v_3)$ is
solution too.
%
In particular, if $(x,y)$ is a solution then $(x_n,y_n)$ is solution with
$x_n+\sqrt{d}y_n=(x+\sqrt{d}y)^n$.

c) The solution is called {\it minimal} if it is nontrivial and $\abs{x+y}$
is minimum. Prove that any solution is a minimal one in some degree.

It is known that for any $d$ which is not a square some solution does exist. It is a hard
problem so we do not include it into this list. You can find a proof e.g. in Bugayenko
"Pell Equation"


\task{A9} Special case of Pell equation.
a) $d=k^2-1$ $\Rightarrow$ $(k,1)$ is a minimal solution.

b) $d=k^2-1$, $(x_1,y_1)$ is a minimal solution, $(x_n,y_n)=(x_1,y_1)^n$.
Prove that $y_n\equiv n mod (k-1)$.

c) Another case of Pell equation. Find the solutions of $x^2-(\frac{b^2}{4}-1)y^2=1$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Consider the following sequence:
$\alpha_0(b)=0$, $\alpha_1(b)=1 $, $\alpha_{n+2}(b)=b\alpha_{n+1}(b)-\alpha_n(b), $
где $b\geqslant 2$.

\task{A10}
Prove that $x^2-bxy+y^2=1, x, y\geqslant 0$, if and only if
%\centerline
$$\hbox{
$\ \kern 4em
 \left\{
  \begin{aligned}
   x&=\alpha_{m+1}(b)\\ 
   y&=\alpha_m(b)\\
  \end{aligned}
 \right.
$
\qquad or \qquad
$
 \left\{
  \begin{aligned}
   x&=\alpha_m(b) \\
   y&=\alpha_{m+1}(b)\\
  \end{aligned}
 \right.
$ }$$
for some integer~$m$.

{
\medskipamount=\smallskipamount

\task{A11}
Prove that $\alpha_n(2)=n$;


\task{A12}
Prove that $\alpha_{k+l}(b)=\
\alpha_{k}(b)\cdot\alpha_{\ell+1}(b)-
\alpha_{k-1}(b)\cdot\alpha_{\ell}(b)$.

\task{A13}
Prove that $\alpha_n(b)\equiv \alpha_{n+4m}(b)\pmod{v}$, 
where $v=\alpha_{m+1}(b)\hm-\alpha_{m-1}(b)$; 


\task{A14}
Suppose that $b_1\equiv b_2\pmod{q}$. Prove that 
$\alpha_n(b_1)\equiv \alpha_n(b_2)\pmod{q}$.

\task{A15} Prove that $2m$ is the value of the number $k$ such that for fixed $n$ the
following statement holds:  
$ \alpha_n(w)\amod v = \alpha_{n+k}(w)\amod v,$
   where $w\equiv b\pmod{v}$, $v=\alpha_{m+1}(b)\hm-\alpha_{m-1}(b)$.


\task{A16}
Suppose that
$ w\equiv b\pmod{v},\ w\equiv 2\pmod{u}$,
 where $v>2\alpha_k(b),\ u>2k$.
Prove that the first $k$ elements of the sequence
$$ \bigl(\alpha_0(b), 0\bigr), 
\ldots , 
\bigl(\alpha_n(b), n\bigr), 
\ldots $$
are coincide with the first $k$ elements of the sequence
$$
\Bigl(\alpha_0(w)\amod v, 
\alpha_0(w) \amod u\Bigr), 
\ldots ,
\Bigl(\alpha_n(w)\amod v,
\alpha_n(w)\amod u\Bigr),
\ldots
$$

\task{A17}
Suppose that $(\alpha_k(b))^2$ divides $\alpha_m(b)$. Prove that $\alpha_k(b)$ divides $m$.

\task{A18} Prove that $2\alpha_k(b)<u \Rightarrow 2k<u$.
\task{A19} Prove that the set $\{(a,\ b,\ c)\mid\ a=\alpha_c(b),\ b>3\}$ is Diophantine.

\task{A20}Prove that $(k-1)^n\leqslant\alpha_{n+1}(k)\leqslant k^n$;

\task{A21}
Prove that $(1+s)^n\geqslant 1+ns$ при $s\in\mathbb R$, $s>-1$,
$n$ --- nonnegative integer.

\task{A22} Prove that
$ b^c=\lim_{n\to\infty}\frac{\alpha_{c+1}(bn+4)}{\alpha_{c+1}(n)}. $

\task{A23} Prove that the set
$\bigl\{(a, b, c)\ \bigl|\ a=b^c\bigr\}$ is Diophantine.

}


\mysection{ B. Coding}

Consider the following regulation of the natural numbers pairs: 
$$\gen<0,0>, \gen<0,1>, \gen<1,0>, \gen<0,2>, \gen<1,1>, \gen<2,0>, \gen<0,3> \dots$$

Note that the number of the pair $\gen<a,b>$ in this sequence can be represented in the polynomial form:
$\Cantor(a,b)=((a+b)^2+3a+b)/2.$
%
The functions $\ElemA(c)$ and $\ElemB(c)$ which are represent the first and the second elements of the pair are also Diophantine:
$$a=\ElemA(c) \quad\Longleftrightarrow\quad \exists y\colon [(a+y)^2+3a+y=2c];$$
$$b=\ElemB(c) \quad\Longleftrightarrow\quad \exists x\colon [(x+b)^2+3x+b=2c]$$

This numeration can be easily generalized for triples, fours, etc. For example, we can assign: 

$\Cantor_1(a_1)=a_1,$
$\Cantor_{n+1}(a_1, \dots a_{n+1}) =
\Cantor_n(a_1, \dots a_{n-1}, \Cantor(a_n,a_{n+1}))$

Further, the number $\Cantor_n(a_1,\dots a_n)$ is called {\it cantor number} of the tuple $\gen<a_1, \dots a_n>$.
Let $c$ be the cantor number of the $n$-tuple. Suppose that $\Elem_{n,m}(c)$ is the value of $m$-component of
that $n$-tuple with number $c$. The function $\Elem_{n,m}(c)$ is Diophantine:
$$a=\Elem_{n,m}(c)
\quad\Longleftrightarrow\quad
   \exists x_1\dots x_{m-1}x_{m+1}\dots x_n\colon
   [2^{2^n}\Cantor_n(x_1,\dots x_{m-1},a,x_{m+1}\dots x_n)=2^{2^n}c]$$
(${\rm Cantor_n}$ is not a polinomial with integer coefficients so we add $2^{2^n}$ factor.)


We should note that this numeration has one serious defect: if $n$ and $m$ are fixed then function $\Elem_{n,m}(c)$ is Diophantine.
However, it is hard to prove that three arguments function $\Elem_{n,m}(c)$ is Diophantine. To deal with
tuples with non fixed lenght we should use some different methods. 


\mysection{Positional Code}

Suppose that $\langle a_1, \dots, a_n \rangle$ is a sequence of integer numbers ($n$-tuple). Let us choose $b>a_i$ for all~$i$.
Suppose that 
$$a=a_nb^{n-1}+a_{n-1}b^{n-2}+\dots +a_1b^0.$$

In other words, $a_1, \dots, a_n$ are the digits in the positional notation of $a$ with base $b$. So, using the triple $(a,b,n)$ we can restore
the $n$-tuple $\gen<a_1, \dots, a_n>$. The triple $(a,b,n)$ is called {\it positional code} of the $n$-tuple $\gen<a_1, \dots, a_n>$.
$(0,b,0)$ is the positional code of the empty tuple. Note that there are some triples which are not codes of any tuple. But, we can
easily prove that the relation ``to be positionsal code'' is Diophantine:
$${\bf Code}(a,b,c)\quad\Longleftrightarrow\quad 
\begin{cases}b\geq 2, \\ a<b^c.
\end{cases}
$$
  

\task{B1}
Prove that the set of qudruples $(a, b, k, c)$,
such that the pair $(a, b)$ encode the sequence and $c$ 
equals to the $k$-th member of this sequence.


\task{B2}
a) Encode the sequence $c_i=\binom{n}{i}$ and show that
the set of triples $(c, m, n)$, such that 
$c=\binom{m}{n}$, is diophantine.
\\
b) Prove that 
$\displaystyle m!=\lim_{n\to\infty} \frac{n^m}
{\binom nm} $
and that the set of numbers, that are factorials, is diophantine.


\task{B3} Prove that the set of prime numbers is diophantine.


\task{B4}
Prove that equation $D(a, x_1, \ldots , x_m)=0$ has a
solution in variables of $x_1, \ldots , x_m$ if and only if then
equation 
$$ a=(x_0+1)(1-D(x_0, x_1, \ldots, x_m)^2)-1 $$
has a solution in variables of $x_0, x_1, \ldots , x_m$.



\task{B5} 
Prove that there exists such a polynomial with 
integer coefficients, such that the set of its positive
values is the set of prime numbers.


Further we will get the skill to unite two sequence into one,
to compare their corresponding elements, 
to check if two triples encode the same sequence, --- 
and all this by solving the corresponding diophantine equation.


\task{B6} 
{\bfseries (Kummer theorem)}
a) Prove that the number $k$, such that $n!$ divides on $p^k$, 
but doesn't divide on $p^{k+1}$, equals 
$$
\Bigl[\frac np\Bigr]+\Bigl[\frac n{p^2}\Bigr]+\Bigl[\frac n{p^3}\Bigr] + \ldots
$$
\\ 
b) Prove that the number $l$, such that $\binom{m+n}n$ 
divides on $p^l$, but doesn't divide on $p^{l+1}$, 
is equal to the number of carries over the next columns 
in $p$-positional sistem of countering,
if we add together numbers $m$ and $n$

\task{B7} 
Consider the set of triples $(a_1, a_2, p)$, where $p$ is prime and 
pairs $(a_1, p)$ and $(a_2, p)$ encode the sequences such that 
for any $k$ the $k$-th element of the first sequence not greater than 
the $k$-th element of the second sequence. 
Prove that this set is diophantine. 
\\
{\bfseries Prompt.} What will you get, if you add together $a_1$ and $a_2-a_1$?


\task{B8} 
Consider the set of quadruples $(a, p, n, e)$, where $p$ is prime and 
triple $(a, p, n)$ encode the sequence, such that
each element of this sequence not greater than $e$.
Prove that this set is diophantine.


\task{B9}
Let $(a_1, b_1, n)$ and $(a_2, b_2, n)$ encode the same sequence 
and $b_1<b_2$. Prove that $a_1\equiv a_2\pmod{b_2-b_1}$.

\task{B10} 
Let, in the proposes of the previous problem, $b_1^n<b_2-b_1$. 
Prove that $a_1$ is defined uniquely by the numbers $a_2,\ b_1,\ b_2,\ n$.


\task{B11}
Prove  that the set of quadruples $(a_1, b_1, a_2, b_2)$, such that
$(a_1, b_1)$ and $(a_2, b_2)$ encode the same sequence, is diophantine.

\task{B12}
Consider the set of quadruples $(a_1, b_1, a_2, b_2)$, such that 
pairs $(a_1, b_1)$ and $(a_2, b_2)$ encode the sequences and 
for any $k$ the $k$-th member of the first sequence 
not greater than the $k$-th member of the second sequence.
Prove that this set is diophantine.

\task{B13} 
Consider the set of quadruples $(a, b, n, e)$, where triple $(a, b, n)$
encode the sequence, such that each element of this sequence not greater than $e$.
Prove that this set is diophantine.



\task{B14}
Consider the set of octoples $(A, B, a_1, b_1, n_1, a_2, b_2, n_2)$, 
such that the pair $(A, B)$ encode the sequence, 
that can be constructed from the sequence, encodable 
by the triple $(a_1, b_1, n_1)$, by continuing it by 
the sequence, encodable by the triple $(a_2, b_2, n_2)$.
Prove that this set is diophantine.


\task{B15} 
Show how to encode the sequences 
$p_1\hm+q_1,\ p_1\hm+q_2, \ldots ,\ p_1\hm+q_m,\ p_2\hm+q_1,\ p_2\hm+q_2, \ldots ,\ 
 p_2\hm+q_m, \ldots ,\ p_n\hm+q_m$ and
$p_1\hm\cdot q_1,\ p_1\hm\cdot q_2, \ldots ,\ p_1\hm\cdot q_m,\ 
p_2\hm\cdot q_1,\ p_2\hm\cdot q_2, \ldots ,\ p_2\hm\cdot q_m, \ldots ,\ p_n\hm\cdot q_m$
by using the codes of
$p_1, \ldots , p_n$ and $q_1, \ldots , q_m$.



\end{document}

\medskip


\mysection{C. Универсальные диофантовы уравнения}

Рассмотрим семейство уравнений $U(a_1,\dots , a_n,\penalty 50 k_1, \dots k_u,\penalty 50 y_1, \dots, y_v )=0$. Будем выделять в нем две группы параметров:
параметры-элементы $a_1$, $\dots$, $a_n$ и параметры-коды $y_1$, $\dots$, $y_v$. Будем называть такое уравнение универсальным, если
для любого диофантового уравнения с $n$ параметрами: $D(a_1,\dots , a_n,\penalty 50 x_1, \dots, x_m)=0$ можно так выбрать значения параметров кодов 
$k_1(D)$, $\dots$, $k_u(D)$, что уравнение $D=0$ разрешимо относительно $x_1, \dots x_n$ при тех и только тех наборах параметров $a_1,\dots , a_n$,
при которых разрешимо уравнение $U(a_1,\dots , a_n, k_1(D), \dots, k_u(D), y_1, \dots, y_v )=0$ относительно $ y_1, \dots y_v$. Можно сказать,
каждое универсальное диофантово уравнение порождает кодирование диофантовых множеств {\it данной размерности}, и для данного уравнения $D=0$ 
этим кодом можно считать кортеж $[k_1(D), \dots, k_u(D)]$.

\task{C1} Покажите, что ценой увеличения количества неизвестных любое универсальное уравнение может быть преобразовано в уравнение с
тем же количеством параметров-элементов, но всего с одним параметром-кодом.

\task{C2} Покажите, что если существует универсальное диофантово уравнение, кодирующее одномерные диофантовы множества (то есть, для $n=1$),
то существует константа $m$, такая, что {\it для любого} $n$ имеется универсальное диофантово уравнение с $u=1$ и $v=m$.

\task{C3} Придумайте способ кодировки уравнения и потенциального решения с помощью нескольких натуральных чисел, такой, что
функция проверки, является ли данный кортеж решением данного уравнения, была диофантовой.

\task{C4} Постройте универсальное диофантово уравнение.

\task{C5} Постройте диофантово множество с недиофантовым дополнением.

\task{C6} Докажите, что множество кодов диофантовых уравнений без параметров, имеющих решения, является множеством из $C5$.




\mysection{D. Машины Тьюринга}

\x[Объяснение устройства машины Тьюринга и принципов составления сложных машин из простых.]



Машина $wRITE(0)$ c инструкциями

q_1* \rightarrow *Sq_2

q_10 \rightarrow 0Sq_2

q_11 \rightarrow 0Sq_2 

q_12 \rightarrow 0Sq_2 

q_13 \rightarrow 0Sq_2 

q_1\lambda \rightarrow 0Sq_2
 
q_1\omega \rightarrow 0Sq_2 

вписывает в клетку, где находится головка, символ "0", если, конечно, это не самая левая клетка с маркером "*".
Ясно, что аналогично можно построить машины $WRITE(1)$, $WRITE(2)$, $WRITE(3)$ инструкции которых получаются заменой
всюду в правых частях символа $"0"$ на $"1"$, $"2"$ и $"3"$ соответственно.


Машина $READ(0)$ c инструкциями

q_1* \rightarrow *Sq_3

q_10 \rightarrow 0Sq_2

q_11 \rightarrow 1Sq_3

q_12 \rightarrow 2Sq_3

q_13 \rightarrow 3Sq_3

q_1\lambda \rightarrow \lambda Sq_3

q_1\omega \rightarrow \lambda Sq_3

распознает, записан ли в клетке, где находится головка, символ "0" или нет. В зависимости от этого она заканчивает 
работу в состоянии $q_2$ или $q_3$. Аналогично можно построить машины $READ(1)$, $READ(2)$, $READ(3)$, $READ(*)$.

\task{D0} a) Постройте машину Тьюринга STOP, которая не сдвигая головки сразу переходит в заключительное состояние.

\task{D0} b) Постройте машину Тьюринга READNOT(x), которая распознает отстутствие символа $"x"$ в клетке.

\medskip

{\bf Два способа композиции машин. }

Первый способ построения по двум машинам Тьюринга $M_1$  м $M_2$ новой машины $M$ состоит в следующем:

1. Во всех инструкциях машины $M_1$ заключительное состояние $q_2$ заменяется на $q_{v+1}$, где $v$ -- количество
состояний машины $M_1$. (Заключительные состояния могут стоять только в правых частях инструкций);

2. Во всех инструкциях машины $M_2$ каждое незаключительное состояние $q_j$ заменяется на $q_{v+i}$.
(В частности, $q_1$ заменяется на q_{v+1})

3. Модифицированные инструкции обеих машин объединяются и образуют систему инструкций новой машины $M$.

рисунок 1


Действие машины $M$, построенной описанным выше способом, состоит в последовательном выполнении
действий машин $M_1$ и $M_2$ при условии, что машина $M_1$ заканчивает работу в состоянии $q_2$. Для обозначения
машины $M$ мы будем испоьзовать одну из трех форм записи 
$M_1;M_2 \quad M_1 \bf{ and } M_2$ или $\bf{if }M_1 {\bf then } M_2$.

\medskip

Второй способ построения по двум машинам Тьюринга $M_1$  м $M_2$ новой машины $M$ состоит в следующем:

1. Во всех инструкциях машины $M_1$ заключительное состояние $q_2$ заменяется на $q_{v+1}$, где $v$ -- количество
состояний машины $M_1$, а заключительное состояние $q_3$ заменяется на $q_2$;

2. Во всех инструкциях машины $M_2$ каждое незаключительное состояние $q_j$ заменяется на $q_{v+i}$.
 а заключительное состояние $q_2$ заменяется на $q_1$;

3. Модифицированные инструкции обеих машин объединяются и образуют систему инструкций новой машины $M$.

рисунок 2


Действие машины $M$, построенной описанным выше способом, состоит в поочередном выполнении
действий машин $M_1$ и $M_2$ до тех пор, пока одна из машин не перейдет в состояние $q_3$. 
$M_1;M_2 \quad M_1 \bf{ and } M_2$ или $\bf{if }M_1 {\bf then } M_2$. Построенную таким образом
машину мы будем обозначать посредством $\bf{while } M_1 \bf{ do } M_2 {\bf od}$.

Введенные нами обозначения выглядят как некоторый примитивный язык программирования. Следует отметить,
однако, что каждая "программа" является на самом деле обозначением конкретной машины Тьюринга.

\medskip 


Машина 

$$ STAR =  \bf{while} READNOT(*) {\bf do} LEFT \bf{od}$$

устанавливает головку на левый конец ленты (помеченный символом $"*"$).

Машина 

$$ VACANT =  STAR; \bf{while} READNOT(\lambda) {\bf do} RIGHT \bf{od}$$

устанавливает головку на левый конец ленты (помеченный символом $"*"$).

\medskip

\task{D1} a) Постройте машину $JUMP$, передвигающую головку до ближайшей клетки с символом $0$.

b) Постройте серию машин Тьюринга $FIND(k)$, устанавливающих головку на $k$-ый от левого края символ $0$.

На ленте машины Тьюринга можно запоминать наборы (кортежи) чисел: для записи кортежа $(a_1, \dots, a_n)$ используются символы~$1$, разделенные
символами~$0$. Например, кортеж $(3,1,2,0,2)$ записывается как $*0111010110011\lambda \dots$. Таким образом, машина Тьюринга может получать
на входе какой-то кортеж и осуществлять его преобразование. 

\task{D2} Постройте машины Тьюринга, преобразующие кортеж $(a_1, \dots, a_n)$ в кортеж: 

a)  $(a_1, \dots, a_n,0)$;

b)  $(a_1, \dots, a_n+1)$;

\task{D3} a) Постройте машину Тьюринга, преобразующие кортеж $(a_1, \dots, a_n)$ в кортеж $(a_1, \dots, a_n-1})$,
или останавливающуюся в состоянии $q_3$, если $a_n=0$.

b) Постройте машину Тьюринга, усекающую кортеж $(a_1, \dots, a_n)$ до кортежа $(a_1, \dots, a_{n-1})$. 

\task{D4} Постройте машины Тьюринга, преобразующие кортеж $(a_1, \dots, a_n)$ в кортеж: 

a) $(a_1, \dots, a_n,a_k+a_l)$, для заданных $0\leq k, \, l\leq n$;

b) $(a_1, \dots, a_n,a_k\times a_l)$, для заданных $0\leq k, \, l\leq n$;

\task{D5} Постройте машину $NOTGREATER(k,l)$, сравнивающую элементы $a_k$ и $a_l$ кортежа 
$(a_1, \dots, a_n)$ и останавливающуюся в состоянии $q_2$ или $q_3$, в соответствии с тем, которое из
неравенств $a_k\leq a_l$ или $a_k>a_l$ имеет место. 

\task{D6} Постройте машины Тьюринга, преобразующие кортеж $(a_1, \dots, a_n)$ в кортеж: 

a) $(a_1, \dots, a_n,b,c)$, где $(b,c)$ пара чисел, следующая за парой $(a_{n-1},a_n)$ в канторовой нумерации;

b) $(a_1, \dots, a_n,b,c)$, где $(b,c)$ пара чисел, имеющая номер $a_n$ в канторовой нумерации;

\task{D7} Пусть имеется уравнение $D(a_1,\dots, a_n,x_1,\dots x_{m+1})=0$. Постройте машину Тьюринга, которая по 
кортежу $(a_1,\dots, a_n,y_0)$ проверяет, является ли $y_0$ канторовым номером кортежа $(x_1,\dots, x_{m+1})$, 
дающего решение уравнения.

\task{D8} Пусть имеется уравнение $D(a_1,\dots,a_n,x_1,\dots x_{m+1})=0$. Постройте машину тьюринга, получающую 
на входе кортеж $(a_1, \dots, a_n)$ и заканчивающую свою работу в том и только том случае, когда уравнение $D=0$
разрешимо относительно $x_1,\dots, x_{m+1}$.

Будем называть множество $\omega$, состоящее из упорядоченных наборов из $n$ натуральных чисел ($n$-ок) 
{\it полуразрешимым по Тьюрингу}, если существует машина Тьюринга $M$, которая начав работу над каноническим изображением
кортежа  $(a_1,\dots,a_n)$ в состоянии $q_1$  и головкой, установленной в левом конце ленты, окончит свою работу в том 
и только том случае, когда $(a_1,\dots,a_n)\in \omega$.

Итак, из результата задачи {D7} следует, что всякое диофантово множество является полуразрешимым по Тьюрингу. Целью следующих
задач будет доказательство обратного, то есть того что каждое полуразрешимое по Тьюрингу множество является диофантовым.

Пусть дана машина Тьюринга $M$, полуразрешающая некоторое множество $\omega$, состоящее из $n-ок$ натуральных чисел.
Пусть $\{ \alpha_1, \dots, \alpha_w \}$ -- алфавит этой машины. На каждом шаге работы машины $M$ заполнен только конечный отрезок
ленты, скажем, длины $l$. Мы можем представить его кортежем $(s_1,s_2,\dots, s_m,\dots, s_{l-1}, s_l)$, где $s_i$ -- номер 
символа записанного в ячейке $i$.

Текущее состояние $q_i$ машины и положение головки можно представлять кортежем такой же длины $(0,\dots, 0,i,0,\dots, 0)$, все
элементы которого, кроме одного, равны нулю, единственный ненулевой элемент указывает положение головки и равен номеру состояния
машины.

Тройку, состоящую из текущего содержимого ленты, состояния машины и положения головки, будем называть {\it конфигурацией}.
Конфигурация определяется двумя кортежами $(s_1,s_2,\dots, s_m,\dots, s_{l-1}, s_l)$ и  $(0,\dots, 0,i,0,\dots, 0)$. Для представления
кортежей мы будем использовать позиционную систему кодирования с каким либо фиксированным основанием $\beta>v,w$.
{\it Кодом конфигурации} будем называть пару $(p,t)$, где $p$ и $t$ -- шифры по основанию $\beta$ указанных кортежей.

Итак, необходимо построить диофантово уравнение $D(p,t,x_1,\dots,x_m)=0$, такое что, если $(p,t)$~--- код некоторой конфигурации,
то уравнение разрешимо относительно $x_1,\dots,x_m$ тогда и только тогда, когда машина $M$ начав работу в этой конфигурации,
остановится через конечное число шагов. Вопрос о разрешимости уравнения в случае, когда $(p,t)$ не является кодом никакой
конфигурации, нас не интересует.

\task{D9} Пусть из конфигурации с кодом $(p,t)$ машина $M$ непосредственно переходит в конфигурацию с кодом $[\NextP(p,t),\NextT(p,t)]$.
Докажите, что функции $\NextP$ и $\NextT$ диофантовы. 

\task{D10} Пусть из конфигурации с кодом $(p,t)$ машина $M$ за $k$ шагов переходит в конфигурацию с кодом $[\AfterP(p,t,k),\AfterT(p,t,k)]$.
Докажите, что функции $\AfterP$ и $\AfterT$ диофантовы.

\task{D11} Постройте диофантово уравнение с параметрами $a_1, \dots, a_n$, разрешимое в тех и только тех случаях, когда данная
машина Тьюринга $M$, начав работу на кортеже $a_1, \dots, a_n$, останавливается. 

\task{D12} Докажите, что нельзя построить машину Тьюринга, которая, начав работу над изображением числа $k$, останавливалась бы через
конечное число шагов в состоянии $q_2$ или $q_3$ в соответствии с тем, разрешимо или неразрешимо диофантово уравнение с кодом $k$.


\end{document}
