Abstract
We present an axiomatic approach that introduces algorithmic randomness into various classes of structures. The central concept is the notion of a branching class. Through this technical yet simple notion we define measure, metric, and topology in many classes of graphs, trees, relational structures, and algebras. As a consequence we define algorithmically random structures. We prove the existence of algorithmically random structures with various computability-theoretic properties. We show that any nontrivial variety of algebras has an effective measure 0. We also prove a counter-intuitive result that there are algorithmically random yet computable structures. This establishes a connection between algorithmic randomness and computable model theory.
B. Khoussainov— The author also acknowledges support of Marsden Fund of Royal Society of New Zealand.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The next subsection provides many examples of classes with height function. For now, for the reader a good example of a class with a height function is the class of rooted finite binary trees.
References
Benjamini, I., Schramm, O.: Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6(23), 1–13 (2001)
Calude, C.S.: Information and Randomness - An Algorithmic Perspective, 2nd edn. Springer, Heidelberg (2002). Revised and Extended
Chaitin, G.J.: On the length of programs for computing finite binary sequences: statistical considerations. J. ACM 16, 145–159 (1969)
Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, New York (2010)
Grätzer, G.: Universal Algebra. Springer, New York (2008). Revised reprint of the second edition
Hodges, W.: Model Theory. Encyclopaedia of Mathematics and Its Applications, vol. 42. Cambridge University Press, Cambridge (1993)
Kolmogorov, A.: Three approaches to the quantitative definition of information. Probl. Inf. Transm. 1, 1–7 (1965)
Khoussainov, B.: A quest for algorithmically random infinite structures. In: Proceedings of LICS-CSL Conference Vienna, Austria (2014)
Khoussainov, B.: Randomness computability, and algebraic specifications. Anal. Pure Appl. Log. 91(1), 1–15 (1998)
Kozen, D.: Complexity of finitely presented algebras. In: Proceedings of the 9th ACM Symposium on Theory of Computing, p. 164–177 (1977)
Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and its Applications. Springer, Heidelberg, 3rd Edn., p. xx+792 (2008)
Mal’cev, A.I.: Constructive algebras. I. Uspehi Mat. Nauk, 16(3(99)), 3–60 (1961)
Martin-Löf, P.: The definition of random sequences. Inf. Control 9(6), 602–619 (1966)
Von Mises, R.: Grundlagen der Wahrscheinlichkeitsrechnung. Math. Z. 5(191), 52–99 (1919)
Nies, A.: Computability and Randomness. Oxford University Press, New York (2009)
Nies, A., Stephan, F.: Personal communication
Rabin, M.O.: Computable algebra, general theory and theory of computable fields. Trans. Amer. Math. Soc. 95, 341–360 (1960)
Schnorr, C.P.: A unified approach to the definition of random sequences. Math. Syst. Theory 5(3), 246–258 (1971)
Schnorr, C.P. : The process complexity and effective random tests. In: Proceedings of the Fourth ACM Symposium of Theory of Computing, Denver, Colorado, 13 May (1972)
Zvonkin, A.K., Levin, L.A.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algoritheorems. Russ. Math. Surv. 25(6), 83–124 (1970)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Khoussainov, B. (2016). A Quest for Algorithmically Random Infinite Structures, II. In: Artemov, S., Nerode, A. (eds) Logical Foundations of Computer Science. LFCS 2016. Lecture Notes in Computer Science(), vol 9537. Springer, Cham. https://doi.org/10.1007/978-3-319-27683-0_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-27683-0_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-27682-3
Online ISBN: 978-3-319-27683-0
eBook Packages: Computer ScienceComputer Science (R0)