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 "algorithm" includes a transformed toponym Khorezm. Algorithms were named after a great sci entist of medieval East, is al-Khwarizmi (where al-Khwarizmi means "from Khorezm"). He lived between c. 783 and 850 B. C. and the year 1983 was chosen to celebrate his 1200th birthday. A short biography of al-Khwarizmi compiled in the tenth century starts as follows: "al-Khwarizmi. His name is Muhammad ibn Musa, he is from Khoresm" (cited according to [Bul Rozen Ah 83, p. 8]).
Inhaltsverzeichnis
Notation and Terminology. - 1. 0 Preliminary notions of the theory of algorithms: constructive objects and aggregates; local properties and local actions. - 1. 1 The general notion of an algorithm as an independent (separate) concept. - 1. 2 Representative computational models. - 1. 3 The general notion of a calculus as an independent (separate) concept. - 1. 4 Representative generating models. - 1. 5 Interrelations between algorithms and calculuses. - 1. 6 Time and Space as complexities of computation and generation. - 1. 7 Computable functions and generable sets; decidable sets; enumerable sets. - 1. 8 The concept of a ? -recursive function. - 1. 9 Possibility of an arithmetical and even Diophantine representation of any enumerable set of natural numbers. - 1. 10 Construction of an undecidable generable set. - 1. 11 Post s reducibility problem. - 1. 12 The concept of a relative algorithm, or an oracle algorithm. - 1. 13 The concept of a computable operation. - 1. 14 The concept of a program; programs as objects of computation and generation. - 1. 15 The concept of a numbering and the theory of numberings. - 1. 16 First steps in the invariant, or machine-independent, theory of complexity of computations. - 1. 17 The theory of complexity and entropy of constructive objects. - 1. 18 Convenient computational models. - 2. 1 Investigations of mass problems. - 2. 2 Applications to the foundations of mathematics: constructive semantics. - 2. 3 Applications to mathematical logic: formalized languages of logic and arithmetic. - 2. 4 Computable analysis. - 2. 5 Numbered structures. - 2. 6 Applications to probability theory: definitions of a random sequence. - 2. 7 Applications to information theory: the algorithmic approach to the concept of quantity of information. - 2. 8 Complexity bounds for particular problems. - 2. 9 Influenceof the theory of algorithms on algorithmic practice. - Appendix. Probabilistic Algorithms (How the Use of Randomness Makes Computations Shorter). - A. 1 Preliminary remarks. - A. 2 Main results. - A. 3 Formal definitions. - References. - Author Index.
