Affiliations: [a] School of Mathematics and Statistics, Victoria University of Wellington, New Zealand. [email protected] | [b] Department of Computer Science, University of Auckland, New Zealand. [email protected] | [c] School of Mathematics and Statistics, Victoria University of Wellington, New Zealand. [email protected]
Abstract: In this paper we study various properties of algorithmically random infinite structures. Our results address the following questions. How would one define algorithmic randomness for infinite structures? Could algorithmically random structures be computable? What are the similarities and differences between algorithmically random structures and algorithmically random infinite strings? What are the possible Turing degrees of algorithmically random structures? Are there algorithmically random infinite groups? For instance, we prove the following in this paper: (1) there are classes which contain algorithmically random yet computable structures, (2) there exist algorithmically random universal algebras with co-computably enumerable as well as computably enumerable word problems, (3) there are natural classes of structures in which the Turing degrees of algorithmically random structures can only be either computable or equivalent to the halting set, and (4) there are examples of algorithmically random groups. The first result shows a dramatic difference between algorithmically random strings and algorithmically random structures. The second result significantly improves the known theorem that algorithmically random structures computable in the halting set exist; these examples of algebras are sharp in terms of arithmetical hierarchy of the word problem for random algebras. The third result is a dichotomy theorem that characterises all possible Turing degrees of algorithmically random structures. Finally, the fourth result answers a nontrivial open question about the existence of algorithmically random groups.
Keywords: Random structures, word problem, degree of a structure, random groups
DOI: 10.3233/COM-180101
Journal: Computability, vol. 8, no. 3-4, pp. 359-375, 2019
