{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T09:41:31Z","timestamp":1772444491888,"version":"3.50.1"},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2841,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A recursive enumerator for a function <jats:italic>h<\/jats:italic> is an algorithm <jats:italic>f<\/jats:italic> which enumerates for an input <jats:italic>x<\/jats:italic> finitely many elements including <jats:italic>h(x)<\/jats:italic>. <jats:italic>f<\/jats:italic> is a <jats:italic>k(n)<\/jats:italic>-enumerator if for every input <jats:italic>x<\/jats:italic> of length <jats:italic>n. h(x)<\/jats:italic> is among the first <jats:italic>k(n)<\/jats:italic> elements enumerated by <jats:italic>f<\/jats:italic>. If there is a <jats:italic>k(n)<\/jats:italic>-enumerator for <jats:italic>h<\/jats:italic> then <jats:italic>h<\/jats:italic> is called <jats:italic>k(n)<\/jats:italic>-enumerable. We also consider enumerators which are only <jats:italic>A<\/jats:italic>-recursive for some oracle <jats:italic>A<\/jats:italic>.<\/jats:p>","DOI":"10.2178\/jsl\/1146620156","type":"journal-article","created":{"date-parts":[[2007,12,19]],"date-time":"2007-12-19T16:22:51Z","timestamp":1198081371000},"page":"501-528","source":"Crossref","is-referenced-by-count":15,"title":["Enumerations of the Kolmogorov function"],"prefix":"10.1017","volume":"71","author":[{"given":"Richard","family":"Beigel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harry","family":"Buhrman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Fejer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Grabowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Longpr\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrej","family":"Muchnik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leen","family":"Torenvliet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200006186_ref019","first-page":"1","article-title":"Three approaches for defining the concept of information quantity","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Problems of Information Transmission"},{"key":"S0022481200006186_ref020","first-page":"1396","author":"Ku\u010dera","year":"1999","journal-title":"Lowness for the class of random sets"},{"key":"S0022481200006186_ref029","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90131-7"},{"key":"S0022481200006186_ref031","first-page":"1199","volume":"66","author":"Terwijn","year":"2001","journal-title":"Algorithmic randomness and lowness"},{"key":"S0022481200006186_ref011","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321363"},{"key":"S0022481200006186_ref007","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360148"},{"key":"S0022481200006186_ref018","first-page":"33","article-title":"\u03a001 classes and degrees of theories","volume":"173","author":"Jockusch","year":"1972","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200006186_ref033","doi-asserted-by":"publisher","DOI":"10.1070\/RM1970v025n06ABEH001269"},{"key":"S0022481200006186_ref023","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"S0022481200006186_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90005-0"},{"key":"S0022481200006186_ref002","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1990.113971"},{"key":"S0022481200006186_ref005","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","author":"Beigel","year":"2004"},{"key":"S0022481200006186_ref001","first-page":"44","volume-title":"Proceedings 15th IEEE Conference on Computational Complexity","author":"Ambainis","year":"2000"},{"key":"S0022481200006186_ref003","first-page":"1251","article-title":"Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set","volume":"9","author":"B\u0101rzdi\u1e47\u0161","year":"1968","journal-title":"Soviet Mathematics Doklady"},{"key":"S0022481200006186_ref006","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1014"},{"key":"S0022481200006186_ref026","volume-title":"Computational complexity","author":"Papadimitriou","year":"1994"},{"key":"S0022481200006186_ref004","unstructured":"Beigel Richard , Query-limited redueihilities, Ph.D. thesis, Department of Computer Science, Stanford University, 1987."},{"key":"S0022481200006186_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90063-1"},{"key":"S0022481200006186_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90103-O"},{"key":"S0022481200006186_ref010","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00016-6"},{"key":"S0022481200006186_ref013","doi-asserted-by":"publisher","DOI":"10.1142\/9789812705815_0005"},{"key":"S0022481200006186_ref014","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19590050703"},{"key":"S0022481200006186_ref016","first-page":"439","volume-title":"Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science","author":"Hartmanis","year":"1983"},{"key":"S0022481200006186_ref015","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511565670.006"},{"key":"S0022481200006186_ref017","first-page":"599","article-title":"Pseudo-jump operators I:the r. e. case.","volume":"275","author":"Jockusch","year":"1983","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200006186_ref021","first-page":"25","volume-title":"Proceedings of the 13th Symposium on Theoretical Aspects of Computer Science","volume":"1046","author":"Kummer","year":"1996"},{"key":"S0022481200006186_ref022","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19940400209"},{"key":"S0022481200006186_ref024","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"S0022481200006186_ref025","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2004.10.006"},{"key":"S0022481200006186_ref027","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050007"},{"key":"S0022481200006186_ref028","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"S0022481200006186_ref032","volume-title":"Technical Report ILLC Technical Report ML 1990-05","author":"Zambella","year":"1990"},{"key":"S0022481200006186_ref030","first-page":"215","volume-title":"Draft of a paper on Chaitin's work","author":"Solovay","year":"1975"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200006186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T20:16:14Z","timestamp":1556828174000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200006186\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,6]]}},"alternative-id":["S0022481200006186"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1146620156","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}