Chapter 5 from the book


written by Yuri MATIYASEVICH

Formats of files

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 Cantorn are defined in Section 3.3 in the following way:

Cantor(a,b)=( (a+b)2+ 3a+b)/2,
Cantorn+1(a1, ..., an+1)= Cantorn(a1, ..., an-1, Cantor(an, an+1))
and that function Cantorn maps one-to-one Nn onto N, where N is the set of non-negative 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
It has a mirror at
All comments can be e-mailed to the author of the book.