Today the notion of the algorithm is familiar not only to mathematicians. It forms a conceptual base for information processing; the existence of a corresponding algorithm makes automatic information processing possible. The theory of algorithms (together with mathematical logic ) forms the the oretical basis for modern computer science (see Sem Us 86]; this article is called "Mathematical Logic in Computer Science and Computing Practice" and in its title mathematical logic is understood in a broad sense including the theory of algorithms). However, not everyone realizes that the word...

The theory of algorithms not only answers philosophical questions but also is eminently applicable to practical computing, as well as to software and hardware design. This book presents exact mathematical formulations of major concepts and facts of the theory of algorithms in a unified and elegant way. Precise mathematical statements are given, together with their underlying motivations, philosophical interpretations and historical developments, starting with Frege, Hilbert and Borel through Godel and Turing up to Kolmogorov's results of 1950-1980. The book is divided into two parts. The...