{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T06:08:58Z","timestamp":1772604538954,"version":"3.50.1"},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2658,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the question of randomness of the probability \u03a9<jats:italic><jats:sub>U<\/jats:sub><\/jats:italic>[<jats:italic>X<\/jats:italic>] that an optimal Turing machine <jats:italic><jats:sub>U<\/jats:sub><\/jats:italic> halts and outputs a string in a fixed set <jats:italic>X<\/jats:italic>. The main results are as follows:<\/jats:p><jats:p>\u2022 \u03a9<jats:italic><jats:sub>U<\/jats:sub><\/jats:italic>[<jats:italic>X<\/jats:italic>] is random whenever <jats:italic>X<\/jats:italic> is \u03a3<jats:sub arrange=\"stack\">n<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup>-complete or \u03a0<jats:sub arrange=\"stack\">n<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup>-complete for some <jats:italic>n<\/jats:italic> \u2265 2.<\/jats:p><jats:p>\u2022 However, for <jats:italic>n<\/jats:italic> \u2265 2, \u03a9<jats:italic><jats:sub>U<\/jats:sub><\/jats:italic>[<jats:italic>X<\/jats:italic>] is not <jats:italic>n<\/jats:italic>-random when <jats:italic>X<\/jats:italic> is \u03a3<jats:sub arrange=\"stack\">n<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup> or \u03a0<jats:sub arrange=\"stack\">n<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup>. Nevertheless, there exists \u0394<jats:sub arrange=\"stack\">n+1<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup> sets such that \u03a9<jats:italic><jats:sub>U<\/jats:sub><\/jats:italic>[<jats:italic>X<\/jats:italic>] is <jats:italic>n<\/jats:italic>-random.<\/jats:p><jats:p>\u2022 There are \u0394<jats:sub arrange=\"stack\">2<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup> sets <jats:italic>X<\/jats:italic> such that \u03a9<jats:italic><jats:sub>U<\/jats:sub><\/jats:italic>[<jats:italic>X<\/jats:italic>] is rational. Also, for every <jats:italic>n<\/jats:italic> \u2265 1, there exists a set <jats:italic>X<\/jats:italic> which is \u0394<jats:sub arrange=\"stack\">n+1<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup> and \u03a3<jats:sub arrange=\"stack\">n<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup>-hard such that \u03a9<jats:italic><jats:sub>U<\/jats:sub><\/jats:italic>[<jats:italic>X<\/jats:italic>] is not random.<\/jats:p><jats:p>We also look at the range of \u03a9<jats:italic>U<\/jats:italic> as an operator. We prove that the set {\u03a9<jats:italic><jats:sub>U<\/jats:sub><\/jats:italic>[<jats:italic>X<\/jats:italic>]: <jats:italic>X<\/jats:italic> \u2286 2<jats:sup>\u2264<jats:sup>\u03c9<\/jats:sup><\/jats:sup>} is a finite union of closed intervals. It follows that for any optimal machine <jats:italic>U<\/jats:italic> and any sufficiently small real r, there is a set <jats:italic>X<\/jats:italic> \u2286 2<jats:sup>\u2264<jats:sup>\u03c9<\/jats:sup><\/jats:sup> recursive in \u2205\u2032 \u2295 <jats:italic>r<\/jats:italic>, such that \u03a9<jats:italic><jats:sub>U<\/jats:sub><\/jats:italic>[<jats:italic>X<\/jats:italic>] = <jats:italic>r<\/jats:italic>.<\/jats:p><jats:p>The same questions are also considered in the context of infinite computations, and lead to similar results.<\/jats:p>","DOI":"10.2178\/jsl\/1164060463","type":"journal-article","created":{"date-parts":[[2007,12,19]],"date-time":"2007-12-19T11:24:03Z","timestamp":1198063443000},"page":"1411-1430","source":"Crossref","is-referenced-by-count":13,"title":["Randomness and halting probabilities"],"prefix":"10.1017","volume":"71","author":[{"given":"Ver\u00f3Nica","family":"Becher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Santiago","family":"Figueira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Serge","family":"Grigorieff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph S.","family":"Miller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200005843_ref010","volume-title":"Classical recursion theory","author":"Odifreddi","year":"1990"},{"key":"S0022481200005843_ref006","unstructured":"Downey R. and Hirschfeldt D. , Algorithmic randomness and complexity, to appear."},{"key":"S0022481200005843_ref005","volume-title":"Algorithmic information theory","author":"Chaitin","year":"1988"},{"key":"S0022481200005843_ref011","volume-title":"Theory of recursive functions and effective computability","author":"Junior","year":"1968"},{"key":"S0022481200005843_ref001","first-page":"891","article-title":"Random reals and possibly infinite computations","volume":"70","author":"Becher","year":"2005","journal-title":"Part I: randomness in \u2205\u2032"},{"key":"S0022481200005843_ref008","first-page":"103","article-title":"Randomness and universal machines","volume":"326","author":"Figueira","year":"2005","journal-title":"CCA 2005, Second International Conference on Computability and Complexity in Analysis, Kyoto, Fernuniversit\u00e4t Hagen, Informatik Berlchte"},{"key":"S0022481200005843_ref009","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799357441"},{"key":"S0022481200005843_ref012","first-page":"215","volume-title":"Draft of paper (or series of papers) on Chaitin's work, done for the most part during the period of Sept.\u2013Dec","author":"Solovay","year":"1974"},{"key":"S0022481200005843_ref007","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376937"},{"key":"S0022481200005843_ref002","unstructured":"Becher V. and Grigorieff S. , Random reals and possibly infinite computations. Part II: From index sets to higher order randomness, In preparation."},{"key":"S0022481200005843_ref004","doi-asserted-by":"publisher","DOI":"10.1145\/321892.321894"},{"key":"S0022481200005843_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00159-0"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200005843","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T15:29:41Z","timestamp":1556810981000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200005843\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["S0022481200005843"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1164060463","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]}}}