A finitely axiomatizable undecidable

equational theory with recursively

solvable word problems

Author:
Dejan Delic

Journal:
Trans. Amer. Math. Soc. **352** (2000), 3065-3101

MSC (1991):
Primary 03B25; Secondary 08A50, 08B05

DOI:
https://doi.org/10.1090/S0002-9947-99-02339-9

Published electronically:
October 5, 1999

MathSciNet review:
1615947

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we construct a finitely based variety, whose equational theory is undecidable, yet whose word problems are recursively solvable, which solves a problem stated by G. McNulty (1992). The construction produces a discriminator variety with the aforementioned properties starting from a class of structures in some multisorted language (which may include relations), axiomatized by a finite set of universal sentences in the given multisorted signature. This result also presents a common generalization of the earlier results obtained by B. Wells (1982) and A. Mekler, E. Nelson, and S. Shelah (1993).

**1.**E. Börger,*Computability, Complexity, Logic*, North-Holland, Amsterdam, 1989. MR**90h:68041****2.**S. Burris,*Polynomial time uniform word problems*, Math. Logic Quart.,**41**(1995), 173-182. MR**96j:08004****3.**S. Burris and H. P. Sankappanavar,*A Course in Universal Algebra*, Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York, 1981. MR**83k:08001****4.**S. Crvenkovi\'{c} and D. Deli\'{c},*A variety with locally solvable but globally unsolvable word problem*, Algebra Universalis,**35**(1996), 420-424. MR**97d:03058****5.**O. Kharlampovich and M.V. Sapir,*Algorithmic problems in varieties*, Internat. J. Algebra Comput.,**5**(1995), 379-602. MR**96m:20045****6.**D. Kozen,*Complexity of finitely presented algebras*, Proc. of the 9th Symposium, STOC, pages 164-177, 1977. MR**58:8487****7.**G. Kreisel and J.L. Krivine,*Elements of Mathematical Logic*, North-Holland, Amsterdam, 1967. MR**36:2463****8.**A.I. Mal'cev,*On homomorphisms onto finite groups*(in Russian), U\v{c}en. Zap. Ivan. Ped. Inst.,**18**(1958), 49-60.**9.**E.W. Mayr and A.R. Meyer,*The complexity of the word problem for commutative semigroups and polynomial ideals*, Adv. in Math.,**46**(1982), 305-329. MR**84g:20099****10.**R. McKenzie,*On spectra, and the negative solution of the decision problem for identities having a nontrivial model*, J. Symbolic Logic,**40**(1975), 186-196. MR**51:12499****11.**R. McKenzie, G. McNulty, and W. Taylor,*Algebras, Lattices, Varieties*, Vol.I, Wadsworth & Brooks/Cole, Monterey, CA, 1987. MR**88e:08001****12.**R. McKenzie and M. Valeriote,*The Structure of Locally Finite Decidable Varieties*, Progress in Mathematics, vol. 79, Birkhäuser, Boston, 1989. MR**92j:08001****13.**G. McNulty,*A field guide to equational logic*, J. Symbolic Comp.,**14**(1992), 371-397. MR**94g:03065****14.**A. Mekler, E. Nelson, and S. Shelah,*A variety with solvable, but not uniformly solvable, word problem*, Proc. London Math. Soc.,**66**(1993), 225-256. MR**93m:03018****15.**A. Schmidt,*Über deduktive Theorien mit mehreren Sorten von Grunddingen*, Math. Ann.,**115**(1938), 485-506.**16.**W. Taylor,*Characterizing Mal'cev conditions*, Algebra Universalis,**3**(1973), 351-397. MR**50:2030****17.**B. Wells,*Pseudorecursive varieties of semigroups*. I, Internat. J. Algebra Comput. MR**97k:20099****18.**B. Wells,*Pseudorecursive Varieties and Their Implications for Word Problems*. PhD thesis, University of California, Berkeley, 1982.

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (1991):
03B25,
08A50,
08B05

Retrieve articles in all journals with MSC (1991): 03B25, 08A50, 08B05

Additional Information

**Dejan Delic**

Affiliation:
Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, N2L 3G1 Canada

Email:
ddelic@math.uwaterloo.ca

DOI:
https://doi.org/10.1090/S0002-9947-99-02339-9

Keywords:
Multisorted logic,
universal theory,
variety,
equational theory,
word problem

Received by editor(s):
June 21, 1996

Received by editor(s) in revised form:
January 8, 1998

Published electronically:
October 5, 1999

Article copyright:
© Copyright 2000
American Mathematical Society