{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T12:17:38Z","timestamp":1764937058379,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T00:00:00Z","timestamp":1556064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2019,4,24]]},"abstract":"<jats:p>Tracing some of the latest advancements in algorithmic randomness.<\/jats:p>","DOI":"10.1145\/3319408","type":"journal-article","created":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T16:17:28Z","timestamp":1556122648000},"page":"70-80","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Algorithmic randomness"],"prefix":"10.1145","volume":"62","author":[{"given":"Rod","family":"Downey","sequence":"first","affiliation":[{"name":"Victoria University Wellington, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis R.","family":"Hirschfeldt","sequence":"additional","affiliation":[{"name":"University of Chicago, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628994"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.09.008"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-015-1209-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.022"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.681318"},{"key":"e_1_2_1_6_1","first-page":"1","article-title":"Computing K-trivial sets by incomplete random sets","volume":"20","author":"Bienvenu L.","year":"2014","unstructured":"Bienvenu , L. , Day , A.R. , Greenberg , N. , Ku\u010dera , A. , Miller , J.S. , Nies , A. , Turetsky , D . Computing K-trivial sets by incomplete random sets . B. Symb. Log. 20 , 1 ( 2014 ), 80--90. Bienvenu, L., Day, A.R., Greenberg, N., Ku\u010dera, A., Miller, J.S., Nies, A., Turetsky, D. Computing K-trivial sets by incomplete random sets. B. Symb. Log. 20, 1 (2014), 80--90.","journal-title":"B. Symb. Log."},{"key":"e_1_2_1_7_1","volume-title":"35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) (Leibniz International Proceedings in Informatics (LIPIcs) )","volume":"96","author":"Bienvenu L.","year":"2018","unstructured":"Bienvenu , L. , Downey , R. On low for speed oracles . In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) (Leibniz International Proceedings in Informatics (LIPIcs) ) ( 2018 ), R. Niedermeier and B. Vall\u00e9e, eds. Volume 96 , Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Germany, 15: 1--15:13. Bienvenu, L., Downey, R. On low for speed oracles. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) (Leibniz International Proceedings in Informatics (LIPIcs) ) (2018), R. Niedermeier and B. Vall\u00e9e, eds. Volume 96, Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Germany, 15:1--15:13."},{"key":"e_1_2_1_8_1","volume-title":"25th International Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics (LIPIcs) )","volume":"1","author":"Bienvenu L.","year":"2008","unstructured":"Bienvenu , L. , Muchnik , An. A. , Shen , A. , Vereshchagin , N. Limit complexities revisited . In 25th International Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics (LIPIcs) ) ( 2008 ), S. Albers and P. Weil, eds. Volume 1 , Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Wadern, 73--84 (electronic). Bienvenu, L., Muchnik, An. A., Shen, A., Vereshchagin, N. Limit complexities revisited. In 25th International Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics (LIPIcs) ) (2008), S. Albers and P. Weil, eds. Volume 1, Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Wadern, 73--84 (electronic)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2014.04.009"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"Randomness and differentiability","volume":"368","author":"Brattka V.","year":"2016","unstructured":"Brattka , V. , Miller , J.S. , Nies , A . Randomness and differentiability . Trans. Amer. Math. Soc. 368 , 1 ( 2016 ), 581--605. Brattka, V., Miller, J.S., Nies, A. Randomness and differentiability. Trans. Amer. Math. Soc. 368, 1 (2016), 581--605.","journal-title":"Trans. Amer. Math. Soc."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1205766"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1142\/9789812705815_0005"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1208359062"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.11.001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_30"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/aima.2000.1945"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2010-10513-0"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/34\/35\/312"},{"key":"e_1_2_1_19_1","first-page":"4","article-title":"Diagonally non-recursive functions and effective Hausdorff dimension","volume":"43","author":"Greenberg N.","year":"2011","unstructured":"Greenberg , N. , Miller , J.S . Diagonally non-recursive functions and effective Hausdorff dimension . B. Lond. Math. Soc. 43 , 4 ( 2011 ), 636--654. Greenberg, N., Miller, J.S. Diagonally non-recursive functions and effective Hausdorff dimension. B. Lond. Math. Soc. 43, 4 (2011), 636--654.","journal-title":"B. Lond. Math. Soc."},{"key":"e_1_2_1_20_1","volume-title":"Dimension 1 sequences are close to randoms. Theor. Comput. Sci. 705","author":"Greenberg N.","year":"2018","unstructured":"Greenberg , N. , Miller , J.S. , Shen , A. , Westrick , L.B. Dimension 1 sequences are close to randoms. Theor. Comput. Sci. 705 ( 2018 ), 99--112. Greenberg, N., Miller, J.S., Shen, A., Westrick, L.B. Dimension 1 sequences are close to randoms. Theor. Comput. Sci. 705 (2018), 99--112."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdm041"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1122-1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603114"},{"key":"e_1_2_1_25_1","first-page":"11","article-title":"The surprise examination paradox and the second incompleteness theorem","volume":"57","author":"Kritchman S.","year":"2010","unstructured":"Kritchman , S. , Raz , R . The surprise examination paradox and the second incompleteness theorem . Notices Am. Math. Soc. 57 , 11 ( 2010 ), 1454--1458. Kritchman, S., Raz, R. The surprise examination paradox and the second incompleteness theorem. Notices Am. Math. Soc. 57, 11 (2010), 1454--1458.","journal-title":"Notices Am. Math. Soc."},{"key":"e_1_2_1_26_1","first-page":"3","article-title":"path to randomness","volume":"21","author":"Ku\u010dera A.","year":"2015","unstructured":"Ku\u010dera , A. , Nies , A. , Porter , C.P. Demuth's path to randomness . B. Symb. Log. 21 , 3 ( 2015 ), 270--305. Ku\u010dera, A., Nies, A., Porter, C.P. Demuth's path to randomness. B. Symb. Log. 21, 3 (2015), 270--305.","journal-title":"B. Symb. Log."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/161259"},{"key":"e_1_2_1_28_1","volume-title":"34th Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics (LIPIcs) )","volume":"66","author":"Lutz J.H.","year":"2017","unstructured":"Lutz , J.H. , Lutz , N. Algorithmic information, plane Kakeya sets, and conditional dimension . In 34th Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics (LIPIcs) ) ( 2017 ). Volume 66 , Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Wadern, Article No. 53, 13. Lutz, J.H., Lutz, N. Algorithmic information, plane Kakeya sets, and conditional dimension. In 34th Symposium on Theoretical Aspects of Computer Science (Leibniz International Proceedings in Informatics (LIPIcs) ) (2017). Volume 66, Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Wadern, Article No. 53, 13."},{"key":"e_1_2_1_29_1","volume-title":"Theory and Applications of Models of Computation (Lecture Notes in Computer Science).","author":"Lutz N.","year":"2017","unstructured":"Lutz , N. , Stull , D.M. Bounding the dimension of points on a line . In Theory and Applications of Models of Computation (Lecture Notes in Computer Science). Volume 10185 , Springer , Cham , 2017 , 425--439. Lutz, N., Stull, D.M. Bounding the dimension of points on a line. In Theory and Applications of Models of Computation (Lecture Notes in Computer Science). Volume 10185, Springer, Cham, 2017, 425--439."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1096901774"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1215\/00294527-2009-017"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2010.06.024"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-08-04395-X"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2004.10.006"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1572527"},{"key":"e_1_2_1_36_1","volume-title":"relativization, and Turing degrees. J Symbolic Logic 70","author":"Nies A.","year":"2005","unstructured":"Nies , A. , Stephan , F. , Terwijn , S.A. Randomness , relativization, and Turing degrees. J Symbolic Logic 70 ( 2005 ), 515--535. Nies, A., Stephan, F., Terwijn, S.A. Randomness, relativization, and Turing degrees. J Symbolic Logic 70 (2005), 515--535."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206006"},{"key":"e_1_2_1_38_1","volume-title":"Logic Colloquium'02 (Lecture Notes in Logic)","author":"Stephan F.","year":"2006","unstructured":"Stephan , F. Martin-L\u00f6f random sets and PA-complete sets . In Logic Colloquium'02 (Lecture Notes in Logic) , Z. Chatzidakis, P. Koepke, W. Pohlers, eds. Volume 27, Association for Symbolic Logic and A K Peters, Ltd ., La Jolla, CA and Wellesley, MA, 2006 , 342--348. Stephan, F. Martin-L\u00f6f random sets and PA-complete sets. In Logic Colloquium'02 (Lecture Notes in Logic), Z. Chatzidakis, P. Koepke, W. Pohlers, eds. Volume 27, Association for Symbolic Logic and A K Peters, Ltd., La Jolla, CA and Wellesley, MA, 2006, 342--348."},{"key":"e_1_2_1_39_1","volume-title":"Pure Mathematics","author":"Turing A.M.","year":"1992","unstructured":"Turing , A.M. Pure Mathematics . J.L. Britton, ed. North-Holland Publishing Co., Amsterdam , 1992 Turing, A.M. Pure Mathematics. J.L. Britton, ed. North-Holland Publishing Co., Amsterdam, 1992"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9214-6"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319408","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3319408","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:21Z","timestamp":1750199901000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319408"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,24]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,4,24]]}},"alternative-id":["10.1145\/3319408"],"URL":"https:\/\/doi.org\/10.1145\/3319408","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2019,4,24]]},"assertion":[{"value":"2019-04-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}