of the Department of Mathematical Logic and Theory of Algorithms

The Department of Mathematical Logic was founded in April 1959.

(22.09.1903 — 11.10.1979).**Andrei Andreevich Markov, Jr.**

Head of the Department from 1959 till October 1979 (simultaneously head of Laboratory of Mathematical Logic and Structure of Machines of Research Computer Center, Academy of Science). A.A.Markov was an outstanding Russian mathematician, corresponding member of the Academy of Sciences of the Soviet Union. He worked fruitfully in algebra, topology, mechanics, mathematical logic, and recursion theory. A.A.Markov is the founder of Russian constructive mathematics.-
(25.04.1903 — 20.10.1987).**Andrei Nikolaevich Kolmogorov**

Head of the Department from January 1980 till October 1987 (simultaneously head of Mathematics Department of the Faculty of Mechanics and Mathematics of Moscow State University). A.N.Kolmogorov, a great mathematician, a member of Academy of Sciences, is the author of the first Russian paper on mathematical logic published in 1925. A.N.Kolmogorov obtained a series of fundamental results in mathematical logic and its applications. Additional information can be found at http://www.kolmogorov.com/. -
(18.08.1928 — 07.05.1993).**Vladimir Andreevich Mel'nikov**

Head of the Department from 1988 until May 1993 (simultaneously the director of the Institute of Problems of Cybernetics, Academy of Science). V.A.Mel'nikov made research in computer architecture, programming, computer-aided design, and other computer-related areas. -
(27.11.1930 — 27.06.2018).**Vladimir Andreevich Uspensky**

Head of the Department January 1995 — June 2018. V.A.Uspensky began his activity as a student of Kolmogorov and now proceeds in study and in developing of Kolmogorov's heritage.

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 achievements of the Laboratory for Logical Problems of Computer Science is also available.

Last modified 08.08.2018.

Mati Pentus