In the mathematical subject of group theory, the Adyan–Rabin theorem is a result that states that most "reasonable" properties of finitely presentable groups are algorithmically undecidable.
The theorem is due to Sergei Adyan (1955)[1][2] and, independently, Michael O. Rabin (1958).
[3] A Markov property P of finitely presentable groups is one for which: For example, being a finite group is a Markov property: We can take
In modern sources, the Adyan–Rabin theorem is usually stated as follows:[4][5][6] Let P be a Markov property of finitely presentable groups.
Then there does not exist an algorithm that, given a finite presentation
defined by this presentation has property P. The word 'algorithm' here is used in the sense of recursion theory.
More formally, the conclusion of the Adyan–Rabin theorem means that set of all finite presentations (where
is a fixed countably infinite alphabet, and
is a finite set of relations in these generators and their inverses) defining groups with property P, is not a recursive set.
The statement of the Adyan–Rabin theorem generalizes a similar earlier result for semigroups by Andrey Markov, Jr.,[7][8] proved by analogous methods.
It was also in the semigroup context that Markov introduced the above notion that that group theorists came to call the Markov property of finitely presented groups.
This Markov, a prominent Soviet logician, is not to be confused with his father, the famous Russian probabilist Andrey Markov after whom Markov chains and Markov processes are named.
According to Don Collins,[9] the notion Markov property, as defined above, was introduced by William Boone in his Mathematical Reviews review of Rabin's 1958 paper containing Rabin's proof of the Adyan–Rabin theorem.
In modern sources,[4][5] the proof of the Adyan–Rabin theorem proceeds by a reduction to the Novikov–Boone theorem via a clever use of amalgamated products and HNN extensions.
be a finitely presented group with undecidable word problem, whose existence is provided by the Novikov–Boone theorem.
The proof then produces a recursive procedure that, given a word
, outputs a finitely presented group
, it follows that it is undecidable whether a finitely presented group has property
The following properties of finitely presented groups are Markov and therefore are algorithmically undecidable by the Adyan–Rabin theorem: Note that the Adyan–Rabin theorem also implies that the complement of a Markov property in the class of finitely presentable groups is algorithmically undecidable.
For example, the properties of being nontrivial, infinite, nonabelian, etc., for finitely presentable groups are undecidable.
However, there do exist examples of interesting undecidable properties such that neither these properties nor their complements are Markov.
Thus Collins (1969) [9] proved that the property of being Hopfian is undecidable for finitely presentable groups, while neither being Hopfian nor being non-Hopfian are Markov.