{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T04:11:41Z","timestamp":1750824701464,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T00:00:00Z","timestamp":1501459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002367","name":"Chinese Academy of Sciences","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002367","id-type":"DOI","asserted-by":"crossref"}]},{"name":"1000 Young Talents Plan from the Chinese Government","award":["D1101130"],"award-info":[{"award-number":["D1101130"]}]},{"name":"Institute of Software of the CAS"},{"name":"National Security Agency Mathematical Sciences Program","award":["H98230-I6-I-D310"],"award-info":[{"award-number":["H98230-I6-I-D310"]}]},{"name":"U.S. National Science Foundation SEALS","award":["NSF DMS-1362273"],"award-info":[{"award-number":["NSF DMS-1362273"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>Consider a universal oracle Turing machine that prints a finite or an infinite binary sequence, based on the answers to the binary queries that it makes during the computation. We study the probability that this output is infinite and computable when the machine is given a random (in the probabilistic sense) stream of bits as the answers to its queries during an infinitary computation. Surprisingly, we find that these probabilities are the entire class of real numbers in (0,1) that can be written as the difference of two halting probabilities relative to the halting problem. In particular, there are universal Turing machines that produce a computable infinite output with probability exactly 1\/2. Our results contrast a large array of facts (the most well-known being the randomness of Chaitin\u2019s halting probability) that witness maximal initial segment complexity of probabilities associated with universal machines. Our proof uses recent advances in algorithmic randomness.<\/jats:p>","DOI":"10.1145\/3091527","type":"journal-article","created":{"date-parts":[[2017,8,2]],"date-time":"2017-08-02T19:36:12Z","timestamp":1501702572000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Probability of a Computable Output from a Random Oracle"],"prefix":"10.1145","volume":"18","author":[{"given":"George","family":"Barmpalias","sequence":"first","affiliation":[{"name":"State Key Lab of Computer Science, Institute of Software, Chinese Academy of Sciences, Zhong guan cun, Beijing, China"}]},{"given":"Douglas","family":"Cenzer","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL"}]},{"given":"Christopher P.","family":"Porter","sequence":"additional","affiliation":[{"name":"Drake University, University Ave, Des Moines, IA"}]}],"member":"320","published-online":{"date-parts":[[2017,8,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.2000.0561"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.02.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2011.0319"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.06.002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"325","DOI":"10.3233\/FUN-2002-51401","article-title":"Another example of higher order randomness","volume":"51","author":"Becher Ver\u00f3nica","year":"2002","unstructured":"Ver\u00f3nica Becher and Gregory J. Chaitin . 2002 . Another example of higher order randomness . Fundam. Inform. 51 , 4 (2002), 325 -- 338 . Ver\u00f3nica Becher and Gregory J. Chaitin. 2002. Another example of higher order randomness. Fundam. Inform. 51, 4 (2002), 325--338.","journal-title":"Fundam. Inform."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0717-0_6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1164060463"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1122038919"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1231082305"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00159-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04978-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/321892.321894"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(92)90099-M"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471667196.ess0029"},{"volume-title":"Computability by probabilistic machines","author":"de Leeuw Karel","key":"e_1_2_1_15_1","unstructured":"Karel de Leeuw , Edward F. Moore , Claude E. Shannon , and Norman Shapiro . 1955. Computability by probabilistic machines . In Automata Studies, C. E. Shannon and J. McCarthy (Eds.). Princeton University Press , Princeton, NJ , 183--212. Karel de Leeuw, Edward F. Moore, Claude E. Shannon, and Norman Shapiro. 1955. Computability by probabilistic machines. In Automata Studies, C. E. Shannon and J. McCarthy (Eds.). Princeton University Press, Princeton, NJ, 183--212."},{"key":"e_1_2_1_16_1","first-page":"315","article-title":"On constructive pseudonumbers","volume":"16","author":"Demuth Oswald","year":"1975","unstructured":"Oswald Demuth . 1975 . On constructive pseudonumbers . Comment. Math. Univers. Carolin. 16 (1975), 315 -- 331 . In Russian. Oswald Demuth. 1975. On constructive pseudonumbers. Comment. Math. Univers. Carolin. 16 (1975), 315--331. In Russian.","journal-title":"Comment. Math. Univers. Carolin."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1154698590"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdm041"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90194-E"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90209-V"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799357441"},{"volume-title":"Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory. Dissertation in Mathematics","author":"Levin Leonid A.","key":"e_1_2_1_23_1","unstructured":"Leonid A. Levin . 1971. Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory. Dissertation in Mathematics . Moscow University . In Russian. Leonid A. Levin. 1971. Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory. Dissertation in Mathematics. Moscow University. In Russian."},{"key":"e_1_2_1_24_1","first-page":"548","article-title":"The concept of a random sequence","volume":"212","author":"Levin Leonid A.","year":"1973","unstructured":"Leonid A. Levin . 1973 . The concept of a random sequence . Dokl. Akad. Nauk SSSR. 212 (1973), 548 -- 550 . Leonid A. Levin. 1973. The concept of a random sequence. Dokl. Akad. Nauk SSSR. 212 (1973), 548--550.","journal-title":"Dokl. Akad. Nauk SSSR."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46406-9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1154698740"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001"},{"volume-title":"Classical Recursion Theory","author":"Odifreddi Piergiorgio G.","key":"e_1_2_1_31_1","unstructured":"Piergiorgio G. Odifreddi . 1989. Classical Recursion Theory . Vol. I . North-Holland Publishing Co. , Amsterdam . Piergiorgio G. Odifreddi. 1989. Classical Recursion Theory. Vol. I. North-Holland Publishing Co., Amsterdam."},{"volume-title":"Classical Recursion Theory","author":"Odifreddi Piergiorgio G.","key":"e_1_2_1_32_1","unstructured":"Piergiorgio G. Odifreddi . 1999. Classical Recursion Theory . Vol. II . North-Holland Publishing Co. , Amsterdam . Piergiorgio G. Odifreddi. 1999. Classical Recursion Theory. Vol. II. North-Holland Publishing Co., Amsterdam."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1107298522"},{"key":"e_1_2_1_34_1","volume-title":"Computing and Combinatorics: 11th Annual International Conference, COCOON 2005 Kunming, China, August 16--19, 2005 Proceedings. Springer Berlin 359--368","author":"Rettinger Robert","year":"2005","unstructured":"Robert Rettinger and Xizhong Zheng . 2005 . Computing and Combinatorics: 11th Annual International Conference, COCOON 2005 Kunming, China, August 16--19, 2005 Proceedings. Springer Berlin 359--368 . https:\/\/doi.org\/10.1007\/11533719_37 10.1007\/11533719_37 Robert Rettinger and Xizhong Zheng. 2005. Computing and Combinatorics: 11th Annual International Conference, COCOON 2005 Kunming, China, August 16--19, 2005 Proceedings. Springer Berlin 359--368. https:\/\/doi.org\/10.1007\/11533719_37"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90223-2"},{"volume-title":"Handwritten manuscript related to Chaitin\u2019s work","author":"Solovay Robert","key":"e_1_2_1_36_1","unstructured":"Robert Solovay . 1975. Handwritten manuscript related to Chaitin\u2019s work . IBM Thomas J. Watson Research Center , Yorktown Heights, NY . Robert Solovay. 1975. Handwritten manuscript related to Chaitin\u2019s work. IBM Thomas J. Watson Research Center, Yorktown Heights, NY."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3091527","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3091527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T20:10:27Z","timestamp":1750795827000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3091527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,31]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3091527"],"URL":"https:\/\/doi.org\/10.1145\/3091527","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2017,7,31]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}