Chapter 5
from the book
written by
Yuri MATIYASEVICH
Sections 5.1 and 5.2 can be read without reading previous chapters in advance.
For reading Sections 5.3 and 5.4, it is sufficient to
know that functions Cantor and Cantor_{n}
are defined in Section 3.3 in the following way:
 Cantor(a,b)=(
(a+b)^{2}+
3a+b)/2,

Cantor_{1}(a_{1})=a_{1},

Cantor_{n+1}(a_{1},
..., a_{n+1})=
Cantor_{n}(a_{1},
..., a_{n1},
Cantor(a_{n},
a_{n+1}))
and that function
Cantor_{n} maps onetoone N^{n} onto N,
where N is the set of nonnegative integers.
The English translation of Chapter 5
is placed on WWW with kind permition of
The MIT Press.
URL of the original Home page of the book is
http://logic.pdmi.ras.ru/~yumat/H10Pbook.
It has a mirror at
http://www.informatik.unistuttgart.de/ifi/ti/personen/Matiyasevich/H10Pbook.
All comments can be
emailed
to the
author of the book.