×

A variety with solvable, but not uniformly solvable, word problem. (English) Zbl 0796.08006

A variety has solvable word problem if every finitely presented algebra in the variety has solvable word problem. It has uniformly solvable word problem if there is an algorithm which, given a finite presentation, produces an algorithm for solving the word problem of the algebra so presented. The authors construct a finitely based variety of finite type which does not have uniformly solvable word problem but which has nevertheless solvable word problem. The proof uses the unsolvability of the halting problem for the universal Turing machine, and the laws defining the variety allow to model the action of the universal Turing machine in the variety. They also construct a recursively based variety of finite type, which is defined by laws involving no variables, with solvable but not uniformly solvable word problem. (The latter result is the best possible: there is no finitely based variety with this property.) The authors also present an easy example (essentially due to B. Wells) of a recursively based variety of infinite type with solvable but not uniformly solvable word problem.

MSC:

08A50 Word problems (aspects of algebraic structures)
03D40 Word problems, etc. in computability and recursion theory
08B99 Varieties
PDFBibTeX XMLCite
Full Text: DOI arXiv