{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T02:10:00Z","timestamp":1652839800880},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1966,10]]},"abstract":"The use of Turing machines for calculating finite binary sequences is studied from the point of view of information theory and the theory of recursive functions. Various results are obtained concerning the number of instructions in programs. A modified form of Turing machine is studied from the same point of view. An application to the problem of defining a patternless sequence is proposed in terms of the concepts here developed.<\/jats:p>","DOI":"10.1145\/321356.321363","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:10Z","timestamp":1027769170000},"page":"547-569","source":"Crossref","is-referenced-by-count":640,"title":["On the Length of Programs for Computing Finite Binary Sequences"],"prefix":"10.1145","volume":"13","author":[{"given":"Gregory J.","family":"Chaitin","sequence":"first","affiliation":[{"name":"The City College of the City University of New York, New York, N. Y."}]}],"member":"320","reference":[{"key":"e_1_2_1_1_2","volume-title":"Automata Sludiea, Shagreen aNd McCarthy, Edm","author":"SHANON C. E.","year":"1956"},{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"SHANON C. E.","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"e_1_2_1_3_2","unstructured":"TURNING A. M. O computable mlmbers with an application to the Entscheidungsproblare. Prec. London Math. See. {2}2 (19337) 230=265; Correction ibid 43 (1937) 544- TURNING A. M. O computable mlmbers with an application to the Entscheidungsproblare. Prec. London Math. See. {2}2 (19337) 230=265; Correction ibid 43 (1937) 544-"},{"key":"e_1_2_1_4_2","volume-title":"New York","author":"DAVIS M.","year":"1958"},{"key":"e_1_2_1_5_2","first-page":"9","author":"NOV MIUSES R","year":"1921","journal-title":"New York"},{"key":"e_1_2_1_6_2","unstructured":"WALD A. Die Widempmmhsfreiheit des Koltektivbeg:riffes der Wahrscheialichkeitsrech mmg. Ergcbnisse eines mathe:matischen Kolloquiums 8 (1937) 38-72. WALD A. Die Widempmmhsfreiheit des Koltektivbeg:riffes der Wahrscheialichkeitsrech mmg. Ergcbnisse eines mathe:matischen Kolloquiums 8 (1937) 38-72."},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1090\/S0002-9904-1940-07154-X","article-title":"Or the concep of a random sequence. Bull","volume":"6","author":"CHURCH A","year":"1940","journal-title":"Amer. Math. Soc."},{"key":"e_1_2_1_8_2","volume-title":"Toronto","author":"POPERR K.R.","year":"1959"},{"key":"e_1_2_1_9_2","volume-title":"John yon Neumann, Collected Works","author":"VON NEUMANN J.","year":"1963"},{"key":"e_1_2_1_10_2","unstructured":"CHAITAN G. J. On the length of programs for computing finite binary sequences by bounded-transfer Taring machines. Abstract 66T-26 Notic. Amer. Math. Soc. 13 (I966) 133. CHAITAN G. J. On the length of programs for computing finite binary sequences by bounded-transfer Taring machines. Abstract 66T-26 Notic. Amer. Math. Soc. 13 (I966) 133."},{"key":"e_1_2_1_11_2","unstructured":"CHAITAN G. J. \n On the length of programs for eompating finite binary sequenees by bounded.trans_ far Turing machines II. Atmtract 631-6 Notic. Amer. Math. Soc. i8 (1966) 228-22(3. (Erratum p. 229 line 5: replace \"P\" by \"L.\") ---. On the length of programs for eompating finite binary sequenees by bounded.trans_ far Turing machines II. Atmtract 631-6 Notic. Amer. Math. Soc. i8 (1966) 228-22(3. (Erratum p. 229 line 5: replace \"P\" by \"L.\")"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/321356.321363","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T21:51:20Z","timestamp":1614721880000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/321356.321363"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1966,10]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1966,10]]}},"alternative-id":["10.1145\/321356.321363"],"URL":"http:\/\/dx.doi.org\/10.1145\/321356.321363","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1966,10]]}}}