zbMATH — the first resource for mathematics

The theory of algorithms. Transl. from the Russian by M. Greendlinger. (English. Russian original) Zbl 0663.03023
Due to the recent spectacular development of computer science, the theory of algorithms has become a central domain of modern mathematics. There are a good number of excellent monographs and textbooks in this area. However, most of them are written with a strong bias toward computer science. The book of Markov and Nagorny is based on another motivation, namely the fact that the concept of an algorithm occupies one of the most central places in investigations on the foundations of mathematics. This is why the authors proceed with great care when choosing the basic objects of their approach. The decision with the most dramatic consequences on the style of the book consists in the complete avoidance of what is usually called set theoretical notions (for example the set of natural numbers or the set of words over some alphabet). The authors’ conception is clearly expressed in the preface of the book: it is pointless to tackle a foundational investigation based on a theory (i.e. set theory) with severe internal difficulties. The book is built on the basis of a manuscript left by the great and profound mathematician A. A. Markov (1903-1979). It has been completed in a remarkable unitary style by his disciple N. M. Nagorny in 1984 when the original version appeared in Russian (see Zbl 0599.03040).
The monograph is organized into nine chapters. Chapter 1 introduces constructive objects. It is claimed that constructive objects of the most general kind can be expressed as words in a given fixed alphabet and that all constructive processes can be obtained from the composition of a few primitive operations on words. The chapter also contains a presentation of the principles of constructive logic which is used throughout the book. This logic differs in many respects from the classical one and each such aspect is clearly delimited and motivated.
Chapter 2 contains a detailed investigation of finite words over an alphabet. Chapter 3 and Chapter 4 present the notion of the Markov normal algorithm. This is the precise formulation of the concept of an algorithm which is taken as the basis of the presentation in the book. Clearly, Markov’s algorithms are equivalent with Turing machines or with the class of recursive functions which appear much more frequently in the literature. However, in the context of this monograph their use is natural since Markov’s algorithms deal only with words and simple operations on them. Various general techniques for constructing such algorithms as well as concrete examples with complete verification proofs are presented.
Chapter 5 is devoted to the proof of the existence of a universal algorithm. The following two chapters contain standard material for this theory. Thus in Chapter 6 various undecidable problems concerning Markov’s normal algorithms are proved and Chapter 7 contains well known theorems like Kleene’s recursion theorem or the Rice theorem (in the book it is called the Uspenski-Rice theorem).
Chapter 8 presents Markov’s proof of the unsolvability of Thue’s problem - the identity problem for semigroups. This question was settled in 1947 by Markov and Post independently. Historically, it has been the first example of an unsolvable algorithmic problem of a mathematical and not mathematical logical nature.
Chapter 9 appears as an application of the theory developed so far. It deals with a number of questions in constructive analysis such as Specker’s example of a bounded, monotonic sequence of constructive reals with no constructive limit or the problem of recognizing equality for real numbers. This chapter also includes a discussion of Markov’s principle, which is still a controversial subject among constructivists (it asserts the possibility of performing an algorithm on a given input, if the assumption that this process will continue endlessly has been refuted).
This monograph appears to be an updating of the classical Markov’s book from 1954 with the same title (Zbl 0058.005). It is remarkable in its striving to do everything in a complete constructive manner. Unfortunately, this approach is space consuming with the effect that only the basis of the theory of algorithms found place in the text. Readers with a good knowledge of the domain will find the book interesting for its distinct foundational flavour.
Reviewer: M.Zimand

03D03 Thue and Post systems, etc.
68W99 Algorithms in computer science
03F60 Constructive and recursive analysis
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations
03D05 Automata and formal grammars in connection with logical questions
03F50 Metamathematics of constructive systems
03D35 Undecidability and degrees of sets of sentences
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
03-03 History of mathematical logic and foundations
68-03 History of computer science