Tarski’s finite basis problem via 𝐀(𝒯)

Willard, Ross

doi:10.1090/S0002-9947-97-01807-2

Tarski’s finite basis problem via $\mathbf A(\mathcal T)$
HTML articles powered by AMS MathViewer

by Ross Willard PDF

Trans. Amer. Math. Soc. 349 (1997), 2755-2774 Request permission

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

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 10.1016/0001-8708(77)90056-1
David Hobby and Ralph McKenzie, The structure of finite algebras, Contemporary Mathematics, vol. 76, American Mathematical Society, Providence, RI, 1988. MR 958685, DOI 10.1090/conm/076
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 10.1007/BF01190604
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 10.1007/BF02485404
—, 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.