{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:57:36Z","timestamp":1757624256610,"version":"3.44.0"},"reference-count":33,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T00:00:00Z","timestamp":1662336000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2023,1,19]]},"abstract":"<jats:p> In this article, we study a notion of the extraction rate of Turing functionals that translate between notions of randomness with respect to different underlying probability measures. We analyze several classes of extraction procedures: (1) a class that generalizes von Neumann\u2019s trick for extracting unbiased randomness from the tosses of a biased coin, (2) a class based on work of by Knuth and Yao (which more properly can be characterized as extracting biased randomness from unbiased randomness), and (3) a class independently developed by Levin and Kautz that generalizes the data compression technique of arithmetic coding. For the first two classes of extraction procedures, we identify a level of algorithmic randomness for an input that guarantees that we attain the extraction rate along that input, while for the third class, we calculate the rate attained along sufficiently random input sequences. <\/jats:p>","DOI":"10.3233\/com-210343","type":"journal-article","created":{"date-parts":[[2022,9,6]],"date-time":"2022-09-06T11:42:46Z","timestamp":1662464566000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":2,"title":["Randomness extraction in computability theory"],"prefix":"10.1177","volume":"12","author":[{"given":"Douglas","family":"Cenzer","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Florida, FL, USA"}]},{"given":"Christopher P.","family":"Porter","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Drake University, IA, USA"}]}],"member":"179","published-online":{"date-parts":[[2022,9,5]]},"reference":[{"key":"ref001","doi-asserted-by":"crossref","unstructured":"S.\u00a0Arora and B.\u00a0Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.","DOI":"10.1017\/CBO9780511804090"},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-007-0060-4"},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2012.26"},{"key":"ref004","doi-asserted-by":"crossref","unstructured":"D.\u00a0Cenzer and C.P.\u00a0Porter, Algorithmically random functions and effective capacities, in: Theory and Methods of Computation (TAMC 2015), Lecture Notes in Computer Science, Vol.\u00a09076, Springer Verlag, 2015, pp.\u00a022\u201337.","DOI":"10.1007\/978-3-319-17142-5_4"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-94418-0_14"},{"key":"ref006","unstructured":"T.M.\u00a0Cover and J.A.\u00a0Thomas, Elements of Information Theory, John Wiley & Sons, 2012."},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9024-7"},{"key":"ref008","doi-asserted-by":"crossref","unstructured":"R.G.\u00a0Downey and D.R.\u00a0Hirschfeldt, Algorithmic Randomness and Complexity, Springer, 2010.","DOI":"10.1007\/978-0-387-68441-3"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177692552"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1017\/9781108781718"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.17323\/1609-4514-2014-14-4-711-744"},{"key":"ref012","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9263-x"},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1109\/18.556116"},{"key":"ref014","unstructured":"M.\u00a0Hoyrup, The dimension of ergodic random sequences, in: 29th International Symposium on Theoretical Aspects of Computer Science, LIPIcs, Leibniz Int. Proc. Inform., Vol.\u00a014, Schloss Dagstuhl. Leibniz-Zent. Inform, Wadern, 2012, pp.\u00a0567\u2013576."},{"key":"ref015","doi-asserted-by":"crossref","unstructured":"R.\u00a0Impagliazzo and A.\u00a0Wigderson, P = BPP if E requires exponential circuits: Derandomizing the XOR lemma, in: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, 1997, pp.\u00a0220\u2013229.","DOI":"10.1145\/258533.258590"},{"key":"ref016","unstructured":"S.M.\u00a0Kautz, Degrees of Random Sets, ProQuest LLC, Thesis (Ph.D.)\u2013Cornell University, Ann Arbor, MI, 1991, p.\u00a0129."},{"key":"ref017","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63248-4_17"},{"key":"ref018","unstructured":"D.E.\u00a0Knuth and A.C.\u00a0Yao, The complexity of nonuniform random number generation, in: Algorithms and Complexity, Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976, 1976, pp.\u00a0357\u2013428."},{"key":"ref019","first-page":"85","volume":"25","author":"Levin L.","year":"1970","journal-title":"Uspekhi Mat. Nauk"},{"key":"ref020","doi-asserted-by":"publisher","DOI":"10.3233\/com-13015"},{"key":"ref021","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001"},{"key":"ref022","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541834"},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176348543"},{"key":"ref024","doi-asserted-by":"crossref","unstructured":"J.\u00a0Rute, Algorithmic randomness and constructive\/computable measure theory, in: Algorithmic Randomness: Progress and Prospects, J.N.Y.\u00a0Franklin and C.P.\u00a0Porter, eds, Lecture Notes in Logic, Vol.\u00a050, Cambridge University Press, 2020.","DOI":"10.1017\/9781108781718.004"},{"key":"ref025","doi-asserted-by":"crossref","unstructured":"K.\u00a0Sayood, Introduction to Data Compression, Morgan Kaufmann, 2017.","DOI":"10.1016\/B978-0-12-809474-7.00019-7"},{"key":"ref026","doi-asserted-by":"publisher","DOI":"10.2307\/2272862"},{"key":"ref027","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22012-8_2"},{"key":"ref028","doi-asserted-by":"crossref","unstructured":"A.\u00a0Shen, V.A.\u00a0Uspensky and N.\u00a0Vereshchagin, Kolmogorov Complexity and Algorithmic Randomness, Vol.\u00a0220, American Mathematical Soc., 2017.","DOI":"10.1090\/surv\/220"},{"key":"ref029","doi-asserted-by":"crossref","unstructured":"C.E.\u00a0Silva, Invitation to Ergodic Theory, Vol.\u00a042, American Mathematical Soc., 2008.","DOI":"10.1090\/stml\/042"},{"key":"ref030","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-014-0378-7"},{"key":"ref031","doi-asserted-by":"crossref","unstructured":"T.\u00a0Uyematsu and F.\u00a0Kanaya, Almost sure convergence theorems of rate of coin tosses for random number generation by interval algorithm, in: 2000 IEEE International Symposium on Information Theory, IEEE, 2000, p.\u00a0457.","DOI":"10.1109\/ISIT.2000.866755"},{"key":"ref032","unstructured":"J.\u00a0von Neumann, Various techniques used in connection with random digits, Applied Math Series (1951), 36\u201338."},{"key":"ref033","doi-asserted-by":"crossref","unstructured":"S.\u00a0Watanabe and T.S.\u00a0Han, Interval algorithm for random number generation: Information spectrum approach, IEEE Transactions on Information Theory (2019).","DOI":"10.1109\/ITW44776.2019.8989339"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-210343","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-210343","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-210343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T12:22:15Z","timestamp":1757420535000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-210343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,5]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,19]]}},"alternative-id":["10.3233\/COM-210343"],"URL":"https:\/\/doi.org\/10.3233\/com-210343","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"type":"print","value":"2211-3568"},{"type":"electronic","value":"2211-3576"}],"subject":[],"published":{"date-parts":[[2022,9,5]]}}}