Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-29T06:24:34.273Z Has data issue: false hasContentIssue false
  • English
  • Français

Kolmogorov and mathematical logic

Published online by Cambridge University Press:  12 March 2014

Vladimir A. Uspensky
Vladimir A. Uspensky*
Affiliation:
Department of Mathematical Logic, Faculty of Mechanics and Mathematics, Moscow University, 119899 Moscow V-234, USSR
Get access Rights & Permissions [Opens in a new window]

Extract

There are human beings whose intellectual power exceeds that of ordinary men. In my life, in my personal experience, there were three such men, and one of them was Andrei Nikolaevich Kolmogorov. I was lucky enough to be his immediate pupil. He invited me to be his pupil at the third year of my being student at the Moscow University. This talk is my tribute, my homage to my great teacher.

Andrei Nikolaevich Kolmogorov was born on April 25, 1903. He graduated from Moscow University in 1925, finished his post-graduate education at the same University in 1929, and since then without any interruption worked at Moscow University till his death on October 20, 1987, at the age 84½.

Kolmogorov was not only one of the greatest mathematicians of the twentieth century. By the width of his scientific interests and results he reminds one of the titans of the Renaissance. Indeed, he made prominent contributions to various fields from the theory of shooting to the theory of versification, from hydrodynamics to set theory. In this talk I should like to expound his contributions to mathematical logic.

Here the term “mathematical logic” is understood in a broad sense. In this sense it, like Gallia in Caesarian times, is divided into three parts:

(1) mathematical logic in the strict sense, i.e. the theory of formalized languages including deduction theory,

(2) the foundations of mathematics, and

(3) the theory of algorithms.

Type
A Survey/expository paper
Information
The Journal of Symbolic Logic , Volume 57 , Issue 2 , June 1992 , pp. 385 - 412
Copyright
Copyright © Association for Symbolic Logic 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[ANK 25]Kolmogorov, A. N., On the principle “tertium non datur”, Mathematicheskiĭ Sbornik, vol. 32 (1924/1925), pp. 646–667; English translation, On the principle of excluded middle, in [Hei 67], pp. 416–437.Google Scholar
[ANK 32]Kolmogorov, A. N., Zur Deutung der intuitionistischen Logik, Mathematische Zeitschrift, vol. 35 (1932), pp. 58–65.CrossRefGoogle Scholar
[ANK 50]Kolmogorov, A. N., Algorithm, Greater Soviet encyclopedia, 2nd ed., Vol. 2, Gosudarstvennoe Nauchnoe Izdatel'stvo “Bol'shaya Sovetskaya Entsiklopediya”, Moscow, 1950, p. 65. (Russian)Google Scholar
[ANK 53]Kolmogorov, A. N., On the notion of algorithm, Uspekhi Matematicheskikh Nauk, vol. 8 (1953), no. 4 (56), pp. 175–176 (Russian); reprinted in [ANK 87], Russian, p. 24.Google Scholar
[ANK 54]Kolmogorov, A. N., Translation editor's preface, in the Russian translation of [Pé 51], IL, Moscow, 1954, pp. 3–10. (Russian)Google Scholar
[ANK 63]Kolmogorov, A. N., On tables of random numbers, Sankhyā: The Indian Journal of Statistics, Series A, vol. 25 (1963), pp. 369–376.Google Scholar
[ANK 65]Kolmogorov, A. N., Three approaches to the definition of the concept of the “amount of information”, Problemy Peredachi Informatsii, vol. 1 (1965), no. 1, pp. 3–11; English translations: (a) Problems of information Transmission, vol. 1 (1965), no. 1, pp. 1–7; (b) International Journal of Computer Mathematics, vol. 2 (1968), pp. 157–168; (c) Selected Translations in Mathematical Statistics and Probability, vol. 7, American Mathematical Society, Providence, Rhode Island, 1968, pp. 293–302.Google Scholar
[ANK 68]Kolmogorov, A. N., Logical basis for information theory and probability theory, IEEE Transactions on Information Theory, vol. IT-14 (1968), pp. 662–664; Russian version, Problemy Peredachi Informatsii, vol. 5 (1969), no. 3, pp. 3–7.CrossRefGoogle Scholar
[ANK 68a]Kolmogorov, A. N., Some theorems on algorithmic entropy and the algorithmic quantity of information, Uspekhi Matematicheskikh Nauk, vol. 23 (1968), no. 2 (140), p. 201. (Russian)Google Scholar
[ANK 70]Kolmogorov, A. N., Combinatorial foundations of information theory and the calculus of probabilities, Uspekhi Matematicheskikh Nauk, vol. 38 (1983), no. 4 (232), pp. 27–36; English translation, Russian Mathematical Surveys, vol. 38 (1983), no. 4, pp. 29–40. [This paper was written in 1970.]Google Scholar
[ANK 82]Kolmogorov, A. N., On logical foundations of probability theory, Probability theory and mathematical statistics (proceedings of the fourth USSR-Japan symposium held at Tbilisi, 1982), Lecture Notes in Mathematics, vol. 1021, Springer-Verlag, Berlin, 1983, pp. 1–5.Google Scholar
[ANK 85]Kolmogorov, A. N., Selected works. Vol. I: Mathematics and mechanics, “Nauka”, Moscow, 1985; English translation, Kluwer, Dordrecht, 1991.Google Scholar
[ANK 85a]Kolmogorov, A. N., About my papers on intuitionistic logic, in [ANK 85], p. 393 (Russian), 451–452 (English).Google Scholar
[ANK 87]Kolmogorov, A. N., Selected works. Vol. III: Theory of information and theory of algorithms, “Nauka”, Moscow, 1987; English translation, Kluwer, Dordrecht (to appear).Google Scholar
[ANK 87a]Kolmogorov, A. N., About my papers on information theory and some of its applications, in [ANK 87], Russian, pp. 251–253.Google Scholar
[ANK 88]Kolmogorov, A. N., Letters of A. N. Kolmogorov to A. Heyting, Uspekhi Matematicheskikh Nauk, vol. 43 (1988), no. 6 (264), pp. 75–77; English translation, Russian Mathematical Surveys, vol. 43 (1988), no. 6, pp. 89–93.Google Scholar
[ANK & D 82]Kolmogorov, A. N. and Dragalin, A. G., Introduction to mathematical logic, Moskovskiĭ Gosudarstvennyĭ Universitet, Moscow, 1982. (Russian)Google Scholar
[ANK & D 84]Kolmogorov, A. N. and Dragalin, A. G., Mathematical logic: supplementary chapters, Moskovskiĭ Gosudarstvennyĭ Universitet, Moscow, 1984. (Russian)Google Scholar
[ANK & U 58]Kolmogorov, A. N. and Uspensky, V. A., On the definition of an algorithm, Uspekhi Matematicheskikh Nauk, vol. 13 (1958), no. 4 (82), pp. 3–28; English translation, American Mathematical Society Translations, ser. 2, vol. 29 (1963), pp. 217–245.Google Scholar
[ANK & U 86]Kolmogorov, A. N. and Uspensky, V. A., Algorithms and randomness, Proceedings of the first world congress of the Bernoulli Society (Tashkent, 1986). Vol. 1: Probability theory and applications, VNU Science Press, Utrecht, 1987, pp. 3–53.Google Scholar
[ANK & U 87]Kolmogorov, A. N. and Uspensky, V. A., Algorithms and randomness, Teoriya Veroyatnosteĭ i eë Primeneniya, vol. 32 (1987), pp. 425–455; English translation, Theory of Probability and Its Applications, vol. 32 (1987), pp. 389–412.Google Scholar
[BA 77]Barzdin, Ya. M.′, Algorithmic information theory, Mathematical encyclopedia. Vol. 1, Izdatel'stvo “Sovetskaya Entsiklopediya”, Moscow, 1977, cols. 219-222; English translation, Kluwer, Dordrecht, 1988, vol. 1, pp. 140–142.Google Scholar
[Ch 40]Church, A., On the concept of a random sequence, Bulletin of the American Mathematical Society, vol. 46 (1940), pp. 130–135.CrossRefGoogle Scholar
[Ch 56]Church, A., Introduction to mathematical logic. Vol. 1, Princeton University Press, Princeton, New Jersey, 1960.Google Scholar
[Er 77]Ershov, Yu. L., The theory of numberings, “Nauka”, Moscow, 1977; German translation of an earlier version, Parts I, II, III, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 19 (1973), pp. 289–388; vol. 21 (1975), pp. 473–584; vol. 23 (1977), pp. 289–371.Google Scholar
[Gö 33]Gödel, K., Zur intuitionistischen Arithmetik und Zahlentheorie, Ergebnisse eines Mathematischen Kolloquiums, vol. 4 (1931/1932), pp. 34–38 (1933).Google Scholar
[Gu 88]Gurevich, Yu., The logic and computer science column, Bulletin of the European Association for Theoretical Computer Science, No. 35 (06 1988), pp. 71–82.Google Scholar
[Hei 67]van Heijenoort, J. (editor), From Frege to Gödel: a source-book in mathematical logic, 1879–1931, Harvard University Press, Cambridge, Massachusetts, 1967.Google Scholar
[Hey 30]Heyting, A., Die formalen Regeln der intuitionistischen Logik, Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-Mathematische Klasse, 1930, pp. 42–56.Google Scholar
[Hey 31]Heyting, A., Die intuitionische Grundlegung der Mathematik, Erkenntnis, vol. 2 (1931/1932), pp. 106–115.CrossRefGoogle Scholar
[Hey 34]Heyting, A., Mathematische Grundlagenforschung. Intuitionismus. Beweistheorie, Springer-Verlag, Berlin, 1934.Google Scholar
[Hi 22]Hilbert, D., Die logischen Grundlagen der Mathematik, Mathematische Annalen, vol. 88 (1923), pp. 151–165.CrossRefGoogle Scholar
[HW 67]Wang, Hao, Preface to the English translation of [ANK 25], in [Hei 67], pp. 414–416.Google Scholar
[Ja 70]Jacobs, K., Turing-Maschinen und zufällige 0-1-Folgen, Selecta mathematica (Jacobs, K., editor), Vol. II, Springer-Verlag, Berlin, 1970, pp. 141–167.CrossRefGoogle Scholar
[Jo 37]Johansson, I., Der Minimalkalkül, ein reduzierter intuitionistischer Formalismus, Compositio Mathematica, vol. 4 (1937), pp. 119–136.Google Scholar
[Kl 52]Kleene, S. C., Introduction to metamathematics, Van Nostrand, Princeton, New Jersey, 1952.Google Scholar
[Kn 69]Knuth, D. E., The art of computer programming. Vol 2: Seminumerical algorithms, Addison-Wesley, Reading, Massachusetts, 1969.Google Scholar
[La 87]van Lambalgen, M., Von Mises definition of random sequences reconsidered, this Journal, vol. 52 (1987), pp. 725–755.Google Scholar
[Le 73]Levin, L. A., On the notion of a random sequence, Doklady Akademii Nauk SSSR, vol. 212 (1973), pp. 548–550; English translation, Soviet Mathematics Doklady, vol. 14 (1973), pp. 1413–1416.Google Scholar
[Le 76]Levin, L. A., Various measures of complexity for finite objects (axiomatic description), Doklady Akademii Nauk SSSR, vol. 227 (1976), pp. 804–807; English translation, Soviet Mathematics Doklady, vol. 17 (1976), pp. 522–526.Google Scholar
[Li Vi 88]Li, M. and Vitányi, P. M. B., Kolmogorov complexity and its applications, Handbook of theoretical computer science. Vol. A: Algorithms and complexity, (van Leeuwen, J., editor), Elsevier, Amsterdam, and MIT Press, Cambridge, Massachusetts, 1990, pp. 187–254.Google Scholar
[Lo 66]Loveland, D., A new interpretation of the von Mises' concept of random sequence, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 279–294.CrossRefGoogle Scholar
[Ma 77]Manin, Yu. I., Kolmogorov complexity, Chapter VI, §9 in Manin, Yu. I., A course in mathematical logic, Springer-Verlag, Berlin, 1977, pp. 225–230.CrossRefGoogle Scholar
[Mi 28]von Mises, R., Wahrscheinlichkeit, Statistik und Wahrheit, J. Springer, Wien, 1928.CrossRefGoogle Scholar
[ML 66]Martin-Löf, P., On the concept of a random sequence, Teoriya Veroyatnosteĭ i eë Primeneniya, vol. 11 (1966), pp. 198–200; English translation, Theory of Probability audits Applications, vol. 11 (1966), pp. 177–179.Google Scholar
[ML 66a]Martin-Löf, P., The definition of random sequences, Information and Control, vol. 9 (1966), pp. 602–619.CrossRefGoogle Scholar
[Pé 51]Peter, R., Rekursive Funktionen, Akademischer Verlag, Budapest, 1951.Google Scholar
[Pl 88]Plisko, V. E., The Kolmogorov calculus as a fragment of minimal calculus, Uspekhi Matematicheskikh Nauk, vol. 43 (1988), no. 6(264), pp. 79–91; English translation, Russian Mathematical Surveys, vol. 43 (1988), no. 6, pp. 95–110.Google Scholar
[Ro 67]Rogers, H. Jr., Theory of recursive functions and effective computahility, McGraw-Hill, New York, 1967; 2nd ed., MIT Press, Cambridge, Massachusetts, 1987.Google Scholar
[Sehn 73]Schnorr, C. P., Process complexity and effective random tests. Journal of Computer and System Sciences, vol. 7 (1973), pp. 376–388.CrossRefGoogle Scholar
[Sehn 77]Schnorr, C. P., A survey of the theory of random sequences, Basic problems in methodology and linguistics: proceedings of the fifth international congress of logic, methodology and philosophy of science, part III (Butts, R. E. and Hintikka, J., editors), Reidel, Dordrecht, 1977, pp. 193–211.CrossRefGoogle Scholar
[Schö 70]schönhage, A., Universelle Turing Speicherung, Automatentheorie und formale Sprachen (Tagung, Oberwolfach, 1969; Dörr, J. and Hotz, G., editors), Bibliographisches Institut, Mannheim, 1970, pp. 369–383.Google Scholar
[Schö 80]Schnorr, C. P., Storage modification machines, SIAM Journal on Computing, vol. 9 (1980), pp. 490–508.Google Scholar
[Shen' 82]Shen, A. Kh.′, Frequency approach to defining the concept of a random sequence, Semiotika i Informatika, vol. 18, VINITI, Moscow, 1982, pp. 14–42. (Russian)Google Scholar
[Shen' 83]Shen, A. Kh.′, The concept of Kolmogorov (α, β)-slochasticity and its properties, Doklady Akademii Nauk SSSR, vol. 271 (1983), pp. 1337–1340; English translation, Soviet Mathematics Doklady, vol. 28 (1983), pp. 295–299.Google Scholar
[Shen' 87]Shen, A. Kh.′, Tables of random numbers, in [ANK 87], Russian, pp. 270–274.Google Scholar
[Shen' 87a]Shen, A. Kh.′, Algorithmic theory of information, in [ANK 87], Russian pp. 257–261.Google Scholar
[Shen' 88]Shen, A. Kh.′, On relations between different algorithmic definitions of randomness, Doklady Akademii Nauk SSSR, vol. 302 (1988), pp. 548–552; English translation, Soviet Mathematics Doklady, vol. 38 (1989), pp. 316–319.Google Scholar
[Sli 81]Slisenko, A. O., Complexity problems in computational theory, Uspekhi Matematicheskikh Nauk, vol. 36 (1981), no. 6 (222), pp. 21–103; English translation, Russian Mathematical Surveys, vol. 36 (1981), no. 6, pp. 23–125.Google Scholar
[So 64]Solomonoff, R., A formal theory of inductive inference. Part I, Information and Control, vol. 7 (1964), pp. 1–22.CrossRefGoogle Scholar
[Us 53]Uspensky, V. A., Gödel's theorem and the theory of algorithms, Uspekhi Matematicheskikh Nauk, vol. 8 (1953), no. 4 (56), pp. 176–178. (Russian)Google Scholar
[Us 53a]Uspensky, V. A., Gödel's theorem and the theory of algorithms, Doklady Akademii Nauk SSSR, vol. 91 (1953), pp. 737–740; English Iranslation, American Mathematical Society Translations, ser. 2, vol. 23 (1963), pp. 103–107.Google Scholar
[Us 55]Uspensky, V. A., Systems of enumerable sets and their numberings, Doklady Akademii Nauk SSSR, vol. 105 (1955), pp. 1155–1158. (Russian)Google Scholar
[Us 56]Uspensky, V. A., Computable operations and the notion of a program, Uspekhi Matematicheskikh Nauk, vol. 11 (1956), no. 4 (70), pp. 172–176. (Russian)Google Scholar
[Us 56a]Uspensky, V. A., The notion of a program and computable operators, Proceedings of the third all-union mathematical congress, Vol. 1: Sectional reports, Izdatel'stvo Akademii Nauk SSSR, Moscow, 1956, p. 186. (Russian)Google Scholar
[Us 57]Uspensky, V. A., Some notes on recursively enumerable sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 3 (1957), pp. 157–170; English translation, American Mathematical Society Translations, ser. 2, vol. 23 (1963), pp. 89–101.Google Scholar
[Us Pl 85]Uspensky, V. A. and Plisko, V. E., Intuitionistic logic, in [ANK 85], pp. 394–404 (Russian), 452–466 (English).Google Scholar
[Us P; 91]Uspensky, V. A. and Plisko, V. E., Diagnostic propositional formulas, Vestnik Moskovskogo Universiteta, Seriya 1: Matematika, Mekhanika, vol. 1991, no. 3, pp. 7–12; English translation, Moscow University Mathematics Bulletin, vol. 46 (1991), no. 3 (to appear).Google Scholar
[Us Se 81]Uspensky, V. A. and Semenov, A. L., What are the gains of the theory of algorithms: basic developments connected with the concept of algorithm and with its application in mathematics, Algorithms in modern mathematics and computer science ( Urgench, 1979), Lecture Notes in Computer Science, vol. 122, Springer-Verlag, Berlin, 1981, pp. 100–234.CrossRefGoogle Scholar
[UsSe87]Uspensky, V. A. and Semenov, A. L., Theory of algorithms: main discoveries and applications, “Niiuka”, Moscow, 1987. (Russian)Google Scholar
[Us Se 87a]Uspensky, V. A. and Semenov, A. L., Algorithms, or machine, of Kolmogorov, in [ANK 87], Russian pp. 279–289.Google Scholar
[V'yu 81]V'yugin, V. V., Algorithmic entropy (complexity) of finite objects and its application to defining randomness and amount of information, Semiotika i Informatika, vol. 16, VINITI, Moscow, 1981, pp. 14–43. (Russian)Google Scholar
[Zv Le 70]Zvonkin, A. K. and Levin, L. A., Complexity of finite objects and the algorithm-theoretic foundations of the notions of information and randomness, Uspekhi Matematicheskikh Nauk, vol. 25 (1970), no. 6(156), pp. 85–127; English translation, Russian Mathematical Surveys, vol. 25 (1970), no. 6, pp. 83–124.Google Scholar