Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Tarski’s finite basis problem via $\mathbf A(\mathcal T)$

Author: Ross Willard
Journal: Trans. Amer. Math. Soc. 349 (1997), 2755-2774
MSC (1991): Primary 03C05; Secondary 08B05
MathSciNet review: 1389791
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: R. McKenzie has recently associated to each Turing machine $\mathcal {T}$ a finite algebra $\mathbf {A} (\mathcal {T})$ having some remarkable properties. We add to the list of properties, by proving that the equational theory of $\mathbf {A}(\mathcal {T})$ is finitely axiomatizable if $\mathcal {T}$ halts on the empty input. This completes an alternate (and simpler) proof of McKenzie’s negative answer to A. Tarski’s finite basis problem. It also removes the possibility, raised by McKenzie, of using $\mathbf {A}(\mathcal {T})$ to answer an old question of B. Jónsson.

References [Enhancements On Off] (What's this?)

  • Kirby A. Baker, Finite equational bases for finite algebras in a congruence-distributive equational class, Advances in Math. 24 (1977), no. 3, 207–243. MR 447074, DOI
  • David Hobby and Ralph McKenzie, The structure of finite algebras, Contemporary Mathematics, vol. 76, American Mathematical Society, Providence, RI, 1988. MR 958685
  • K. Kearnes and Á. Szendrei, Self-rectangulating varieties of type 5, manuscript, 1995.
  • Emil W. Kiss and Péter Pröhle, Problems and results in tame congruence theory. A survey of the ’88 Budapest Workshop, Algebra Universalis 29 (1992), no. 2, 151–171. MR 1157431, DOI
  • Ralph McKenzie, Para primal varieties: A study of finite axiomatizability and definable principal congruences in locally finite varieties, Algebra Universalis 8 (1978), no. 3, 336–348. MR 469853, DOI
  • ---, The residual bounds of finite algebras, Int. J. Algebra and Computation 6 (1996), 1–28.
  • ---, The residual bound of a finite algebra is not computable, Int. J. Algebra and Computation 6 (1996), 29–48.
  • ---, Tarski’s finite basis problem is undecidable, Int. J. Algebra and Computation 6 (1996), 49–104.
  • Peter Perkins, Unsolvable problems for equational theories, Notre Dame J. Formal Logic 8 (1967), 175–185. MR 236012
  • A. Tarski, Equational logic and equational theories of algebras, Contributions to Math. Logic (Colloquium, Hannover, 1966) North-Holland, Amsterdam, 1968, pp. 275–288. MR 0237410
  • Walter Taylor, Equational logic, Houston J. Math. Survey (1979), iii+83. MR 546853
  • R. Willard, On McKenzie’s method, Periodica Math. Hungarica 32 (1996), 149–165.

Similar Articles

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

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

Additional Information

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

Keywords: Finite algebra, equational theory, finitely axiomatizable
Received by editor(s): October 18, 1995
Additional Notes: This research was supported by the NSERC of Canada
Article copyright: © Copyright 1997 American Mathematical Society