| Preface | |
| Introduction | p. 1 |
| Notation and Terminology | p. 3 |
| Fundamental Discoveries of the General Theory of Algorithms | p. 5 |
| Preliminary notions of the theory of algorithms: constructive objects and aggregates; local properties and local actions | p. 7 |
| The general notion of an algorithm as an independent (separate) concept | p. 17 |
| Representative computational models | p. 22 |
| Appendix 1.2: Schonhage machines | p. 28 |
| The general notion of a calculus as an independent (separate) concept | p. 31 |
| Appendix 1.3: Algebraic examples | p. 37 |
| Representative generating models | p. 45 |
| Interrelations between algorithms and calculuses | p. 46 |
| Time and Space as complexities of computation and generation | p. 48 |
| Appendix 1.6: Real-time simulation | p. 57 |
| Computable functions and generable sets; decidable sets; enumerable sets | p. 58 |
| The concept of a [mu]-recursive function | p. 66 |
| Possibility of an arithmetical and even Diophantine representation of any enumerable set of natural numbers | p. 68 |
| Construction of an undecidable generable set | p. 70 |
| Post's reducibility problem | p. 73 |
| The concept of a relative algorithm, or an oracle algorithm | p. 77 |
| The concept of a computable operation | p. 80 |
| The concept of a program; programs as objects of computation and generation | p. 84 |
| The concept of a numbering and the theory of numberings | p. 98 |
| First steps in the invariant, or machine-independent, theory of complexity of computations | p. 108 |
| The theory of complexity and entropy of constructive objects | p. 110 |
| Convenient computational models | p. 115 |
| Mathematical Applications of the Theory of Algorithms | p. 119 |
| Investigations of mass problems | p. 121 |
| Applications to the foundations of mathematics: constructive semantics | p. 137 |
| Applications to mathematical logic: formalized languages of logic and arithmetic | p. 141 |
| Computable analysis | p. 145 |
| Numbered structures | p. 154 |
| Applications to probability theory: definitions of a random sequence | p. 166 |
| Applications to information theory: the algorithmic approach to the concept of quantity of information | p. 179 |
| Complexity bounds for particular problems | p. 184 |
| Influence of the theory of algorithms on algorithmic practice | p. 188 |
| Appendix. Probabilistic Algorithms (How the Use of Randomness Makes Computations Shorter) | p. 195 |
| References | p. 209 |
| Subject Index | p. 253 |
| Author Index | p. 267 |
| Table of Contents provided by Blackwell. All Rights Reserved. |
