The Department of Mathematical Logic was founded in April 1959.
The first Head of Department was A.A.Markov, Jr., followed by A.N.Kolmogorov, V.A.Mel'nikov, and V.A.Uspensky.
In 1992 the Department of Mathematical Logic got a new name the Department of Mathematical Logic and Theory of Algorithms.
In 1995 the Laboratory for Logical Problems of Computer Science was organized at the Department of Mathematical Logic and Theory of Algorithms.
In 1947 A.A.Markov, Jr. proved (independently of E. Post, 1947) algorithmic undecidability of the word identity problem in semigroup theory. He also established undecidability of several other famous algorithmic problems (in particular, undecidability of the problem of homeomorphism of polyhedra, 1958) and introduced the notion of normal algorithm.
A.N.Kolmogorov introduced the interpretation of intuitionistic logic as logic of problems (Brouwer — Heyting — Kolmogorov interpretation, 1925). He founded the numeration theory and the theory of complexity of constructive objects (Kolmogorov complexity, 1965). A.N.Kolmogorov suggested a very general notion of algorithm (Kolmogorov — Uspensky machine).
V.A.Uspensky is involved in systematization of fundamental ideas related to algorithms — beginning from his earlier publication (1958, jointly with Kolmogorov) on the so called Kolmogorov — Uspensky machine, through exposition of the basic notions of the numeration theory, to his recent papers on algorithmic approach to Goedel's incompleteness theorem and on Kolmogorov complexity.
S.I.Adian established in 1955 algorithmic undecidability of recognition problems for almost all invariant properties of groups and semigroups. In 1968 S.I.Adian and P.S.Novikov proved that in the case of odd periods n>664 the free periodic group with two generators is infinite (the soluton of the famous Burnside problem). In 1971 S.I.Adian constucted an example of a non-Abelian torsion free group in which the intersection of any two subgroups is infinite.
Information about scientific accomplishments of the Laboratory for Logical Problems of Computer Science is also available.
Last modified 06.12.2010.