Available in electronic format
Available in print format
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
     

Tarski's finite basis problem via $ \mathbf {A}({\mathcal T})$

Author(s): Ross Willard
Journal: Trans. Amer. Math. Soc. 349 (1997), 2755-2774.
MSC (1991): Primary 03C05; Secondary 08B05
Retrieve article in: PDF
This article is available free of charge

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:

1.
K. Baker, Finite equational bases for finite algebras in a congruence-distributive equational class, Adv. in Math. 24 (1977), 207-243. MR 56:5389

2.
D. Hobby and R. McKenzie, The Structure of Finite Algebras, Amer. Math. Soc. (Providence, R.I.), 1988. MR 89m:08001

3.
K. Kearnes and Á. Szendrei, Self-rectangulating varieties of type 5, manuscript, 1995.

4.
E. Kiss and P. Prohle, Problems and results in tame congruence theory, Algebra Universalis 29 (1992), 151-171. MR 93g:08004

5.
R. McKenzie, Paraprimal varieties: a study of finite axiomatizability and definable principal congruences in locally finite varieties, Algebra Universalis 8 (1978), 336-348. MR 57:9634

6.
-, The residual bounds of finite algebras, Int. J. Algebra and Computation 6 (1996), 1-28. CMP 96:07
7.
-, The residual bound of a finite algebra is not computable, Int. J. Algebra and Computation 6 (1996), 29-48. CMP 96:07
8.
-, Tarski's finite basis problem is undecidable, Int. J. Algebra and Computation 6 (1996), 49-104. CMP 96:07
9.
P. Perkins, Unsolvable problems for equational theories, Notre Dame J. Formal Logic 8 (1967), 175-185. MR 38:4310

10.
A. Tarski, Equational logic and equational theories of algebras, pp. 275-288 in H. A. Schmidt et al., eds., Contributions to Mathematical Logic, North-Holland (Amsterdam), 1968. MR 38:5692

11.
W. Taylor, Equational Logic, Survey 1979, Houston J. Math., 1979. MR 80j:03042

12.
R. Willard, On McKenzie's method, Periodica Math. Hungarica 32 (1996), 149-165. CMP 97:01


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
Email: rdwillar@flynn.uwaterloo.ca

DOI: 10.1090/S0002-9947-97-01807-2
PII: S 0002-9947(97)01807-2
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
Copyright of article: Copyright 1997, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google