Randnomness, computability, and algebraic specifications (Q1382180)

The author describes an interesting relation between Kolmogorov complexity and abstract algebra. Traditionally, Kolmogorov complexity is defined and analyzed for integers or for words in an alphabet; however, it can also be described for an arbitrary algebra (crudely speaking, for an arbitrary abstract data type). Namely, if we fix a finite set of constants and a finite set of function symbols of different arity, we can define terms in a standard manner. Each term \(t\) is a word, so we can define its Kolmogorov complexity \(K(t)\). If an integer-valued function \(f(t)\) is defined on the set of all terms, then we can say that a term is \(f\)-random if \(K(t)\geq f(t)\). In particular, if we take the height \(h(t)\) of a term \(t\) as \(f(t)\), we can talk about random terms. We can define the algebra of random terms if we factorize the set of all terms over the equivalence relation in which all non-random terms are equivalent to each other. It turns out that every original function operation is consistent with this equivalence and therefore, this factor-set is indeed an algebra. This algebra is finitely generated (constants serve as generators), and its equality relation is recursively enumerable (although, of course, not decidable). The author proves that this algebra cannot be algebraically specified (i.e., specified by equalities); thus, this algebra is a first natural example of a finitely generated recursively enumerable algebra which cannot be algebraically specified.