
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.
Applications of computability and recursion theory, Logic, Equational classes, universal algebra in model theory, Kolmogorov complexity, randomness, finitely generated algebras, Theory of numerations, effectively presented structures, Algorithmic information theory (Kolmogorov complexity, etc.), Abstract data types; algebraic specification, abstract data types
Applications of computability and recursion theory, Logic, Equational classes, universal algebra in model theory, Kolmogorov complexity, randomness, finitely generated algebras, Theory of numerations, effectively presented structures, Algorithmic information theory (Kolmogorov complexity, etc.), Abstract data types; algebraic specification, abstract data types
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 14 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
