{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:06Z","timestamp":1759638366613},"reference-count":15,"publisher":"Duke University Press","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Notre Dame J. Formal Logic"],"published-print":{"date-parts":[[2005,1,1]]},"DOI":"10.1305\/ndjfl\/1107220673","type":"journal-article","created":{"date-parts":[[2005,2,1]],"date-time":"2005-02-01T17:31:57Z","timestamp":1107279117000},"source":"Crossref","is-referenced-by-count":6,"title":["Program Size Complexity for Possibly Infinite Computations"],"prefix":"10.1215","volume":"46","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":"Andr\u00e9","family":"Nies","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Silvana","family":"Picchi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"73","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"Becher, V., S. Daicz, and G. Chaitin, \"A highly random number\", pp. 55\u201368 in <i>Combinatorics, C<\/i>omputability and Logic: Proceedings of the Third Discrete Mathematics and Theoretical Computer Science Conference (DMTCS'01), edited by C. S. Calude and M. J. Dineen and S. Sburlan, Springer-Verlag, London, 2001.","DOI":"10.1007\/978-1-4471-0717-0_6"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Chaitin, G. J., \"A theory of program size formally identical to information theory\", <i>Journal of the Association for Computing Machinery<\/i>, vol. 22 (1975), pp. 329\u201340.","DOI":"10.1145\/321892.321894"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Chaitin, G. J., \"Algorithmic entropy of sets\", <i>Computers &amp; Mathematics with Applications<\/i>, vol. 2 (1976), pp. 233\u201345.","DOI":"10.1016\/0898-1221(76)90016-X"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Chaitin, G. J., \"Information-theoretic characterizations of recursive infinite strings\", <i>Theoretical Computer Science<\/i>, vol. 2 (1976), pp. 45\u201348.","DOI":"10.1016\/0304-3975(76)90005-0"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Downey, R. G., D. R. Hirschfeldt, A. Nies, and F. Stephan, \"Trivial reals\", pp. 103\u201331 in <i>Proceedings of the 7th and 8th A<\/i>sian Logic Conferences, Singapore University Press, Singapore, 2003.","DOI":"10.1142\/5186"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Ferbus-Zanda, M., and S. Grigorieff, \"Church, cardinal and ordinal representations of integers and kolmogorov complexity\", in preparation, 2003.","DOI":"10.1002\/malq.200510040"},{"key":"7","unstructured":"Gacs, P., \"On the symmetry of algorithmic information\", <i>Soviet Mathematics, Doklady (Akademiia Nauk SSSR. Doklady)<\/i>, vol. 15 (1974), pp. 1477\u201380."},{"key":"8","unstructured":"Levin, L. A., \"The concept of a random sequence\", <i>Doklady Akademii Nauk SSSR<\/i>, vol. 212 (1973), pp. 548\u201350."},{"key":"9","unstructured":"Levin, L. A., \"Laws on the conservation (zero increase) of information, and questions on the foundations of probability theory\", <i>Problemy Pereda\u010di Informacii<\/i>, vol. 10 (1974), pp. 30\u201335."},{"key":"10","unstructured":"Li, M., and P. Vitanyi, <i>An I<\/i>ntroduction to Kolmogorov Complexity and Its Applications, 2d edition, Graduate Texts in Computer Science. Springer-Verlag, New York, 1997."},{"key":"11","doi-asserted-by":"publisher","unstructured":"Martin-L \u00f6f, P., \"The definition of random sequences\", <i>Information and Control<\/i>, vol. 9 (1966), pp. 602\u201319.","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Schnorr, C.-P., \"Process complexity and effective random tests\", <i>Journal of Computer and System Sciences<\/i>, vol. 7 (1973), pp. 376\u201388. Fourth Annual ACM Symposium on the Theory of Computing (Denver, Colo., 1972).","DOI":"10.1016\/S0022-0000(73)80030-3"},{"key":"13","unstructured":"Solovay, R. M., \"Draft of a paper (or series of papers) on C\"haitin's work done for the most part during the period Sept. to Dec. 1974, 1974."},{"key":"14","doi-asserted-by":"publisher","unstructured":"Uspensky, V. A., and A. Shen, \"Relations between varieties of K\"olmogorov complexities, <i>Mathematical Systems Theory<\/i>, vol. 29 (1996), pp. 271\u201392.","DOI":"10.1007\/BF01201280"},{"key":"15","doi-asserted-by":"crossref","unstructured":"Zvonkin, A. K., and L. A. Levin, \u201cThe complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms,\u201d <i>Uspekhi Matematicheskikh Nauk<\/i>, vol. 25 (1970), pp. 85\u2013127.","DOI":"10.1070\/RM1970v025n06ABEH001269"}],"container-title":["Notre Dame Journal of Formal Logic"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/journalArticle\/Download?urlid=10.1305\/ndjfl\/1107220673","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T20:56:13Z","timestamp":1706648173000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/notre-dame-journal-of-formal-logic\/volume-46\/issue-1\/Program-Size-Complexity-for-Possibly-Infinite-Computations\/10.1305\/ndjfl\/1107220673.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1,1]]},"references-count":15,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,1,1]]}},"URL":"https:\/\/doi.org\/10.1305\/ndjfl\/1107220673","relation":{},"ISSN":["0029-4527"],"issn-type":[{"value":"0029-4527","type":"print"}],"subject":[],"published":{"date-parts":[[2005,1,1]]}}}