Recent Developments and Resources
Decidability Questions in Universal Algebra
Which questions about varieties and algebras admit algorithms, and the dividing lines that later work established.
Learning objectives
- Distinguish the main decision problems
- Report the status of each
- Identify the structural features driving decidability
Material on this page extends past the 1981 text and its Millennium re-typesetting. Statements here are attributed to later literature, not to Burris and Sankappanavar. Where the status of a question is unsettled, this page says so rather than resolving it.
The problems
| Problem | Input | Question |
|---|---|---|
| Word problem | A finite presentation, two terms | Are the terms equal? |
| Equational theory | A finite algebra, an identity | Does the identity hold in the generated variety? |
| First-order theory | A variety, a sentence | Is the sentence true in every member? |
| Finite basis problem | A finite algebra | Does the generated variety have a finite basis? |
| Residual smallness | A finite algebra | Is the generated variety residually small? |
Status
| Problem | Status | Attribution |
|---|---|---|
| Word problem for semigroups | Undecidable | Markov, Post (1947) |
| Word problem for groups | Undecidable | Novikov, Boone (1950s) |
| Equational theory of a finite algebra | Decidable | Check all assignments — finite |
| First-order theory of a finitely generated variety | Decidable or not, depending on the variety | Various |
| Tarski's finite basis problem | Undecidable | McKenzie (1996) |
| Residual smallness for finite algebras | Undecidable | McKenzie (1996) |
| Decidability of a locally finite variety's first-order theory | Characterised | McKenzie and Valeriote (1989) |
The equational theory of a single finite algebra is trivially decidable — evaluate the identity on all assignments. But whether that variety has a finite basis is undecidable. Deciding individual identities and deciding properties of the whole theory are problems of entirely different character.
What drives decidability
The decidable cases share a structural feature: every member is transparently built from a bounded family of pieces, so no computation can be simulated.
| Decidable side | Undecidable side |
|---|---|
| Discriminator varieties, finitely generated | Semigroups |
| Boolean algebras | Groups |
| Abelian groups | Rings |
| K-vector spaces | Lattices |
| Varieties omitting the right types | Varieties admitting all types |
The characterisation of decidable locally finite varieties says, roughly, that such a variety decomposes into a discriminator part, an affine part and a unary part, with strong restrictions on how they interact. Anything richer allows the simulation of computation.
Attribution
The source's Recent Developments chapter identifies decidability as an active area and reports the state as of around 1981. The McKenzie undecidability results (1996) and the McKenzie–Valeriote characterisation (1989) are later and are reported here as subsequent developments. The word problem results of Markov, Post, Novikov and Boone predate the source and are classical.
Frequently asked questions
Is the word problem always undecidable for infinite varieties?
No. The word problem for abelian groups and for Boolean algebras is decidable. Undecidability requires enough non-commutativity or combinatorial freedom to encode computation.
Does undecidability of the finite basis problem contradict Baker's theorem?
No. Baker gives a sufficient condition that is itself decidable to check — one can test whether a finite algebra generates a congruence-distributive variety. What is undecidable is the general question with no such hypothesis.
Source. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, The Millennium Edition — a corrected re-typesetting of Springer-Verlag Graduate Texts in Mathematics 78 (1981). Section RD.3, book pages 285-287.
This page is an original exposition prepared for the KEVOS® knowledge library. It restates and reorganises mathematical results; it is not a reproduction of the source text.