{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:54Z","timestamp":1777516794951,"version":"3.51.4"},"reference-count":24,"publisher":"SAGE Publications","issue":"3-4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["COM"],"published-print":{"date-parts":[[2019,9,20]]},"DOI":"10.3233\/com-180101","type":"journal-article","created":{"date-parts":[[2018,9,29]],"date-time":"2018-09-29T07:20:06Z","timestamp":1538205606000},"page":"359-375","source":"Crossref","is-referenced-by-count":3,"title":["Effective aspects of algorithmically random structures"],"prefix":"10.1177","volume":"8","author":[{"given":"Matthew","family":"Harrison-Trainor","sequence":"first","affiliation":[{"name":"School of Mathematics and Statistics, Victoria University of Wellington, New Zealand. matthew.harrisontrainor@vuw.ac.nz"}]},{"given":"Bakh","family":"Khoussainov","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Auckland, New Zealand. bmk@cs.auckland.ac.nz"}]},{"given":"Daniel","family":"Turetsky","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Victoria University of Wellington, New Zealand. dan.turetsky@vuw.ac.nz"}]}],"member":"179","reference":[{"key":"10.3233\/COM-180101_ref1","unstructured":"C.S.\u00a0Calude, Information and Randomness\u00a0\u2013 an Algorithmic Perspective, 2nd edn, revised and extended, Springer-Verlag, Berlin, 2002."},{"key":"10.3233\/COM-180101_ref2","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1145\/321495.321506","article-title":"On the length of programs for computing finite binary sequences: Statistical considerations","volume":"16","author":"Chaitin","year":"1969","journal-title":"Journal of the ACM"},{"key":"10.3233\/COM-180101_ref3","unstructured":"R.\u00a0Downey and D.\u00a0Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York."},{"key":"10.3233\/COM-180101_ref4","unstructured":"P.\u00a0Erd\u00f6s and J.\u00a0Spencer, Probabilistic Methods in Combinatorics, Probability and Mathematical Statistics, Vol.\u00a017, Academic Press, New York\u2013London, 1974."},{"issue":"1","key":"10.3233\/COM-180101_ref5","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s000390300002","article-title":"Random walk in random groups","volume":"13","author":"Gromov","year":"2003","journal-title":"Geom. Funct. Anal."},{"key":"10.3233\/COM-180101_ref6","doi-asserted-by":"crossref","first-page":"4473","DOI":"10.1090\/proc\/14063","article-title":"On optimal Scott sentences of finitely generated structures","volume":"146","author":"Harrison-Trainor","year":"2018","journal-title":"Proceedings of the American Mathematical Society"},{"key":"10.3233\/COM-180101_ref7","unstructured":"W.\u00a0Hodges, Model Theory, Encyclopedia of Mathematics and its Applications, Vol.\u00a042, Cambridge University Press, 1993."},{"key":"10.3233\/COM-180101_ref8","doi-asserted-by":"crossref","unstructured":"B.\u00a0Khoussainov, A\u00a0quest for algorithmically random infinite structures,\u00a0II, in: Proceedings of LFCS, 2015.","DOI":"10.1007\/978-3-319-27683-0_12"},{"key":"10.3233\/COM-180101_ref9","doi-asserted-by":"crossref","unstructured":"B.\u00a0Khoussainov, A quest for algorithmically random infinite structures, in: Proceedings of LICS-CSL 2014 Conference, Vienna, Austria.","DOI":"10.1145\/2603088.2603114"},{"key":"10.3233\/COM-180101_ref10","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.2307\/2273915","article-title":"Degrees coded in jumps of orderings","volume":"51","author":"Knight","year":"1986","journal-title":"Journal of Symbolic Logic"},{"key":"10.3233\/COM-180101_ref11","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Problems of Information Transmission"},{"key":"10.3233\/COM-180101_ref12","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1137\/S0097539799357441","article-title":"Randomness and recursive enumerability","volume":"31","author":"Ku\u010dera","year":"2001","journal-title":"SIAM Journal on Computing"},{"key":"10.3233\/COM-180101_ref13","doi-asserted-by":"crossref","unstructured":"M.\u00a0Li and P.\u00a0Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn, Springer-Verlag, 2008, (xx\u00a0+ 792\u00a0pp.).","DOI":"10.1007\/978-0-387-49820-1"},{"key":"10.3233\/COM-180101_ref14","unstructured":"R.C.\u00a0Lyndon and P.E.\u00a0Schupp, Combinatorial Group Theory, Springer-Verlag, Berlin, 1977."},{"issue":"3(99)","key":"10.3233\/COM-180101_ref15","first-page":"3","article-title":"Constructive algebras.\u00a0I","volume":"16","author":"Mal\u2019cev","year":"1961","journal-title":"Uspehi Mat. Nauk"},{"issue":"6","key":"10.3233\/COM-180101_ref16","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","article-title":"The definition of random sequences","volume":"9","author":"Martin-L\u00f6f","year":"1966","journal-title":"Information and Control"},{"key":"10.3233\/COM-180101_ref17","doi-asserted-by":"crossref","unstructured":"A.\u00a0Nies, Computability and Randomness, Oxford University Press, 2009.","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001"},{"key":"10.3233\/COM-180101_ref18","first-page":"341","article-title":"Computable algebra, general theory and theory of computable fields","volume":"95","author":"Rabin","year":"1960","journal-title":"Trans. Amer. Math. Soc."},{"issue":"4","key":"10.3233\/COM-180101_ref19","doi-asserted-by":"publisher","first-page":"723","DOI":"10.2307\/2273222","article-title":"Degrees of structures","volume":"46","author":"Richter","year":"1981","journal-title":"J.\u00a0Symbolic Logic"},{"issue":"3","key":"10.3233\/COM-180101_ref20","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/BF01694181","article-title":"A\u00a0unified approach to the definition of random sequences","volume":"5","author":"Schnorr","year":"1971","journal-title":"Mathematical Systems Theory"},{"key":"10.3233\/COM-180101_ref21","doi-asserted-by":"crossref","unstructured":"C.P.\u00a0Schnorr, The process complexity and effective random tests, in: Proceedings of the Fourth ACM Symposium of Theory of Computing, Vols\u00a01\u20133, Denver, Colorado, 1972.","DOI":"10.1145\/800152.804910"},{"issue":"1","key":"10.3233\/COM-180101_ref22","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s000390300003","article-title":"Addendum to: \u201cRandom walk in random groups\u201d","volume":"13","author":"Silberman","year":"2003","journal-title":"Geom. Funct. Anal."},{"key":"10.3233\/COM-180101_ref23","doi-asserted-by":"publisher","first-page":"2117","DOI":"10.1090\/S0002-9939-98-04307-X","article-title":"Relative to any nonrecursive set","volume":"126","author":"Slaman","year":"1998","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"6","key":"10.3233\/COM-180101_ref24","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1070\/RM1970v025n06ABEH001269","article-title":"The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms","volume":"25","author":"Zvonkin","year":"1970","journal-title":"Russian Math. Surveys"}],"container-title":["Computability"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/COM-180101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T16:00:03Z","timestamp":1777392003000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-180101"}},"subtitle":[],"editor":[{"given":"Vasco","family":"Brattka","sequence":"additional","affiliation":[]},{"given":"Rod","family":"Downey","sequence":"additional","affiliation":[]},{"given":"Julia F.","family":"Knight","sequence":"additional","affiliation":[]},{"given":"Steffen","family":"Lempp","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2019,9,20]]},"references-count":24,"journal-issue":{"issue":"3-4"},"URL":"https:\/\/doi.org\/10.3233\/com-180101","relation":{},"ISSN":["2211-3576","2211-3568"],"issn-type":[{"value":"2211-3576","type":"electronic"},{"value":"2211-3568","type":"print"}],"subject":[],"published":{"date-parts":[[2019,9,20]]}}}