On free Turing algebras (Q1820803)

A configuration (simulating the tape of a Turing machine) is a pair (s,t) of words over \(\{\) 0,1\(\}\) such that s (assumed non-empty) begins and t (if non-empty) ends with a 1. A Turing algebra is an algebra of type (1,1,1,1,2) over the universe of all partial functions of the set of all configurations into itself. The paper presents an algorithmic solution to the word problem for the free algebra (over a standard alphabet) in the variety K generated by the class of all Turing algebras. It is also proved that the subalgebra of a Turing algebra, generated by the identity mapping in the set of all configurations, is also a free K-algebra, for which the same algorithm is valid.