The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
On the Length of Programs for Computing Finite Binary Sequences
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“In a loose sense, FunSearch attempts to find solutions that have low Kolmogorov complexity48–50 (which is the length of the shortest computer program that produces a given object as output), whereas traditional search procedures have a very different inductive bias.”
From Mathematical discoveries from program search with large language models (2024) · cites this paper as [48]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb01338.x · Cited by 88,486
On the concept of a random sequence
Church, A. (1940) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1940-07154-x · Cited by 395
Research works printed but not linked: 5
- SHANON C. E., 1956, Automata Sludiea, Shagreen aNd McCarthy, Edm
- DAVIS M., 1958, New York
- NOV MIUSES R, 1921, New York, 9
- POPERR K.R., 1959, Toronto
- VON NEUMANN J., 1963, John yon Neumann, Collected Works
Cited by
Sorted by citations
Items 501–600 of 907
Comparing Security Notions of Secret Sharing Schemes
Dai, S., & Guo, D. (2015) · Entropy · doi:10.3390/e17031135 · Cited by 6
Nonlinear analysis of saccade speed fluctuations during combined action and perception tasks
Stan, C., Aştefănoaei, C., Pretegiani, E., Optican, L. M., Creanga, D. E., Rufa, A., & Cristescu, C. (2014) · Journal of Neuroscience Methods · doi:10.1016/j.jneumeth.2014.05.010 · Cited by 6
Kolmogorov-Chaitin complexity of digital controller implementations
Whidborne, J. F., McKernan, J., & Gu, D. (2006) · Machine Intelligence Research · doi:10.1007/s11633-006-0314-3 · Cited by 6
Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces
Benatti, F., Oskouei, S. K., & Abad, A. S. D. (2014) · Journal of Mathematical Physics · doi:10.1063/1.4892516 · Cited by 6
The application of algorithmic information theory to noisy patterned strings
Devine, S. (2006) · Complexity · doi:10.1002/cplx.20152 · Cited by 6
An Information Measure for Comparing Top k Lists
Collier, J. H., & Konagurthu, A. S. (2014) · IEEE International Conference on eScience · doi:10.1109/escience.2014.39 · Cited by 6
Measuring meaningful information in images: algorithmic specified complexity
Ewert, W., Dembski, W. A., & Marks, R. J. (2015) · IET Computer Vision · doi:10.1049/iet-cvi.2014.0141 · Cited by 6
Topological Complexity Measures of Supply Chain Networks
Modrák, V., & Bednár, S. (2016) · Procedia CIRP · doi:10.1016/j.procir.2016.01.041 · Cited by 6
Algorithmic complexity of quantum capacity
Oskouei, S. K., & Mancini, S. (2018) · Quantum Information Processing · doi:10.1007/s11128-018-1859-0 · Cited by 6
Sophistication vs Logical Depth
Antunes, L. F., Bauwens, B., Souto, A., & Teixeira, A. (2016) · Theory of Computing Systems · doi:10.1007/s00224-016-9672-6 · Cited by 6
Enhancing MML Clustering Using Context Data with Climate Applications
Visser, G., Dowe, D. L., & Uotila, P. J. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10439-8_36 · Cited by 6
Connectionist functionality and the emergent network behavior
Hoffmann, A. G. (1991) · Neurocomputing · doi:10.1016/0925-2312(91)90046-e · Cited by 6
Statistical learning theory, model identification and system information content
Guergachi, A., & Patry, G. G. (2002) · International Journal of General Systems · doi:10.1080/03081070290018056 · Cited by 6
A complexity theory of design intentionality
Zamenopoulos, T. (2011) · Artificial intelligence for engineering design analysis and manufacturing · doi:10.1017/s0890060411000023 · Cited by 6
Measuring the Difficulty of Specific Learning Problems
Thornton, C. (1995) · Connection Science · doi:10.1080/09540099508915658 · Cited by 6
Degrees of monotone complexity
Calhoun, W. C. (2006) · Journal of Symbolic Logic · doi:10.2178/jsl/1164060458 · Cited by 6
Random languages for nonuniform complexity classes
Mundhenk, M., & Schuler, R. (1991) · Journal of Complexity · doi:10.1016/0885-064x(91)90038-y · Cited by 6
Chaitin, G. J. (1992) · Applied Mathematics and Computation · doi:10.1016/0096-3003(92)90057-8 · Cited by 6
Self-citationDynamical Complexity of Strange Sets
Auerbach, D. (1989) · NATO ASI series. Series B : Physics · doi:10.1007/978-1-4757-0623-9_26 · Cited by 6
Textual Substitution Techniques for Data Compression
Storer, J. A. (1985) · Springer eBooks · doi:10.1007/978-3-642-82456-2_8 · Cited by 6
Quantum Kolmogorov Complexity and the Quantum Turing Machine
Müller, M. P. (2007) · DepositOnce · doi:10.14279/depositonce-1687 · Cited by 6
A Simple Overview of Complex Systems and Complexity Measures
Monteiro, L. H. A. (2025) · Complexities · doi:10.3390/complexities1010002 · Cited by 5
Assembly in Directed Hypergraphs
Flamm, C., Merkle, D., & Stadler, P. F. (2025) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2025.0331 · Cited by 5
How Physical Information Underlies Causation and the Emergence of Systems at all Biological Levels
Farnsworth, K. D. (2025) · Acta Biotheoretica · doi:10.1007/s10441-025-09495-3 · Cited by 5
Process and truth-table characterisations of randomness
Day, A. R. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.05.028 · Cited by 5
A Critical Review of the Main Approaches on Financial Market Dynamics Modelling
Lucian, P. (2015) · Journal of Heterodox Economics · doi:10.1515/jheec-2015-0017 · Cited by 5
The value of compression for taxonomic identification
Silva, J. M., & Almeida, J. R. (2022) · Proceedings - IEEE Symposium on Computer-Based Medical Systems · doi:10.1109/cbms55023.2022.00055 · Cited by 5
AN ALGORITHMIC INFORMATION THEORY CHALLENGE TO INTELLIGENT DESIGN
Devine, S. (2014) · Zygon® · doi:10.1111/zygo.12059 · Cited by 5
Cryptography and Algorithmic Randomness
Tadaki, K., & Doi, N. (2014) · Theory of Computing Systems · doi:10.1007/s00224-014-9545-9 · Cited by 5
A Method to Detect Repeated Unknown Patterns in an Image
Ferreira, P. J. S. G., & Pinho, A. J. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11758-4_2 · Cited by 5
Stochastic approaches in phyllotaxis
Barabé, D. (2006) · Canadian Journal of Botany · doi:10.1139/b06-116 · Cited by 5
Very Simple Chaitin Machines for Concrete AIT
Stay, M. (2005) · Fundamenta Informaticae · doi:10.3233/fun-2005-68303 · Cited by 5
The tragicomedy of modern theoretical biology
Seel, M., & Ladik, J. J. (2019) · Advances in quantum chemistry · doi:10.1016/bs.aiq.2019.11.001 · Cited by 5
Classification of Complex Systems Based on Transients
Hudcová, B., & Mikolov, T. (2020) · Conference on Artificial Life (ALIFE) · doi:10.1162/isal_a_00260 · Cited by 5
Lutz, N., & Stull, D. M. (2021) · Computability · doi:10.3233/com-190292 · Cited by 5
Complex Systems and Self-Organization
Marinescu, D. C. (2013) · Elsevier eBooks · doi:10.1016/b978-0-12-404627-6.00010-5 · Cited by 5
Symmetry of information and one-way functions
Longpré, L., & Mocas, S. (1991) · Lecture notes in computer science · doi:10.1007/3-540-54945-5_75 · Cited by 5
Smith, E. (2013) · Cambridge University Press eBooks · doi:10.1017/cbo9781139225700.012 · Cited by 5
Measuring Complexity in Financial Data
Yadav, G. S., Guha, A., & Chakrabarti, A. S. (2020) · Frontiers in Physics · doi:10.3389/fphy.2020.00339 · Cited by 5
Entropy estimation in bidimensional sequences
Filho, F. N. M. D. S., de Sá, V. G. P., & Brigatti, E. (2022) · Physical review. E · doi:10.1103/physreve.105.054116 · Cited by 5
Day, A. R. (2011) · doi:10.26686/wgtn.16985293.v1 · Cited by 5
Rissanen, J. (1990) · Springer eBooks · doi:10.1007/978-1-4612-3352-7_25 · Cited by 5
A new spectral test for nonrandomness and the DES
Feldman, F. A. (1990) · IEEE Transactions on Software Engineering · doi:10.1109/32.48934 · Cited by 5
The Complexity of Sequences Generated by the Arc-Fractal System
Huynh, H. N., Pradana, A., & Chew, L. Y. (2015) · PLoS ONE · doi:10.1371/journal.pone.0117365 · Cited by 5
Graph Entropy from Closed Walk and Cycle Functionals
Aziz, F., Hancock, E. R., & Wilson, R. C. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-49055-7_16 · Cited by 5
On Measuring Cognition and Cognitive Augmentation
Fulbright, R. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-92046-7_41 · Cited by 6
The Combinatorial Foundations of Information Theory and the Probability Calculus
Shiryayev, A. N. (1993) · Mathematics and its applications. Soviet series · doi:10.1007/978-94-017-2973-4_13 · Cited by 5
On the entropy of a formal language
de Luca, A. (1975) · Lecture notes in computer science · doi:10.1007/3-540-07407-4_13 · Cited by 5
Inferring phylogenetic graphs of natural languages using minimum message length
Ooi, J. N., & Dowe, D. L. (2005) · Cited by 5
Ren, F., Tanaka, H., & Gojobori, T. (1995) · Computer Methods and Programs in Biomedicine · doi:10.1016/0169-2607(94)01609-j · Cited by 5
Daws, R. E., Scott, G., Soreq, E., Leech, R., Hellyer, P. J., & Hampshire, A. (2020) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2020.06.17.156570 · Cited by 5
Modularity in Reinforcement Learning via Algorithmic Independence in Credit AssignmentPreprint
Chang, M., Kaushik, S., Levine, S., & Griffiths, T. L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.14993 · Cited by 5
Jeffrey, R. C. (1977) · Springer eBooks · doi:10.1007/978-94-017-0837-1_13 · Cited by 5
State Complexity of Imprecise Causal Models
(1976) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1976.4309572 · Cited by 5
The Origins of Computational Mechanics: A Brief Intellectual History and Several ClarificationsPreprint
Crutchfield, J. P. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.06832 · Cited by 14
Phylogenetic minimum description length: an optimality criterion based on algorithmic complexity
Wheeler, W. C., & Varón, A. (2025) · Cladistics · doi:10.1111/cla.12603 · Cited by 4
On Jacob Ziv’s Individual-Sequence Approach to Information Theory
Merhav, N. (2024) · IEEE BITS the Information Theory Magazine · doi:10.1109/mbits.2025.3543321 · Cited by 4
Robust Estimation of Evolutionary Distances with Information Theory
Cao, M. D., Allison, L., Dix, T. I., & Mikael Bodén, A. (2016) · Molecular Biology and Evolution · doi:10.1093/molbev/msw019 · Cited by 4
Mega-Evolution of Information Processing Systems
Oeser, E. (1992) · Springer eBooks · doi:10.1007/978-3-642-77211-5_6 · Cited by 4
Let Us First Agree on what the Term "Semantics" Means: An Unorthodox Approach to an Age-Old Debate
Diamant, E. (2012) · InTech eBooks · doi:10.5772/36981 · Cited by 4
Nafría, J. M. D. (2011) · IGI Global eBooks · doi:10.4018/978-1-61350-201-3.ch003 · Cited by 4
On the Biological Origin of Design in Nature
Grandpierre, A. (2012) · Cellular origin, life in extreme habitats and astrobiology · doi:10.1007/978-94-007-4156-0_2 · Cited by 4
Complexity, Emergence and Molecular Diversity via Information Theory
Torrens, F., & Castellano, G. (2012) · IGI Global eBooks · doi:10.4018/978-1-4666-2077-3.ch009 · Cited by 4
Complexity of Legal Processes and Systems
Burgin, M., & Mestdagh, K. D. V. (2020) · International Society for the Study of Information Summit (IS4SI Summit) · doi:10.3390/proceedings2020047017 · Cited by 4
On the Detection of Unknown Locally Repeating Patterns in Images
Pratas, D., & Pinho, A. J. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31295-3_19 · Cited by 4
Information and complexity measures in the interface of a metal and a superconductor
Moustakidis, C. C., & Panos, C. P. (2018) · Physics Letters A · doi:10.1016/j.physleta.2018.04.022 · Cited by 4
Complexity of HCl and H2 molecules under q-deformed Morse potential
Nutku, F., Aydıner, E., & Sen, K. D. (2021) · Indian Journal of Physics · doi:10.1007/s12648-021-02028-x · Cited by 4
Quantum Statistical Complexity Measure as a Signaling of Correlation Transitions
Cesário, A. T., Ferreira, D. L. B., Debarba, T., Iemini, F., Maciel, T. O., & Vianna, R. O. (2022) · Entropy · doi:10.3390/e24081161 · Cited by 4
Panos, C. P., Chatzisavvas, K. C., Moustakidis, C. C., Nikolaidis, N., Massen, S. E., & Sen, K. D. (2011) · Springer eBooks · doi:10.1007/978-90-481-3890-6_3 · Cited by 4
Calude, C. S. (2000) · Cited by 4
On the algorithmic foundation of information theory
Heim, R. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1056080 · Cited by 4
Subrecursive programming languages II on program size
Constable, R. L. (1971) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(71)80039-9 · Cited by 4
Collins, R., & Thompson, R. (1997) · Elsevier eBooks · doi:10.1016/b978-008042835-2/50040-0 · Cited by 4
A Statistically Significant Test to Evaluate the Order or Disorder of a Binary String
Blackledge, J., & Mosola, N. (2020) · Irish Signals and Systems Conference · doi:10.1109/issc49989.2020.9180178 · Cited by 4
Computing and Complexity — Networks, Nature and Virtual Worlds
Green, D. G., & Leishman, T. G. (2011) · Elsevier eBooks · doi:10.1016/b978-0-444-52076-0.50004-3 · Cited by 4
To the Logical Foundations of the Theory of Information and Probability Theory
Shiryayev, A. N. (1993) · Mathematics and its applications. Soviet series · doi:10.1007/978-94-017-2973-4_12 · Cited by 4
Convergence rates for the minimum complexity estimator of counting process intensities
Gregoire, G., & Nembé, J. (2000) · Journal of nonparametric statistics · doi:10.1080/10485250008832825 · Cited by 4
Exploring, modelling and controlling discrete sequential environments
Witten, I. H. (1977) · International Journal of Man-Machine Studies · doi:10.1016/s0020-7373(77)80038-2 · Cited by 4
The complexity and entropy of Turing machines
Dufort, P. A., & Lumsden, C. J. (2002) · Workshop on Physics and Computation (PhysComp) · doi:10.1109/phycmp.1994.363677 · Cited by 4
Mathematical foundations of modern cryptography: computational complexity perspectivePreprint
Goldwasser, S. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0212055 · Cited by 4
Information, Language, and Pixon‐Based Image Reconstructiona
Puetter, R. C. (1997) · Annals of the New York Academy of Sciences · doi:10.1111/j.1749-6632.1997.tb51659.x · Cited by 4
Non-complex sequences: Characterizations and examples
Daley, R. (1974) · Annual Symposium on Switching & Automata Theory · doi:10.1109/swat.1974.15 · Cited by 4
Properties of bounds on computation
Meyer, A. R., & McCreight, E. M. (2018) · Figshare · doi:10.1184/r1/6608699 · Cited by 4
Korotkich, V. (2001) · Springer eBooks · doi:10.1007/0-306-48332-7_241 · Cited by 4
Computationally intelligent methods for qualitative data analysis
Lensu, A. (2002) · Jyväskylä University Digital Archive (University of Jyväskylä) · Cited by 4
An Algorithmic Approach to Emergence
Bédard, C. A., & Bergeron, G. (2022) · Entropy · doi:10.3390/e24070985 · Cited by 3
Conversational complexity for assessing risk in large language models
Burden, J., Cebrián, M., & Hernández‐Orallo, J. (2025) · EPJ Data Science · doi:10.1140/epjds/s13688-025-00592-4 · Cited by 8
Minimum complexity pursuit: Stability analysis
Jalali, S., Maleki, A., & Baraniuk, R. G. (2012) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2012.6283602 · Cited by 3
Haynes, K. E., Kulkarni, R., Stough, R. R., & Schintler, L. A. (2012) · Studies in Regional Science · doi:10.2457/srs.42.25 · Cited by 3
Weight Assignment using Entropy
Yurong, Q., & Jeon, G. (2016) · International Journal of Multimedia and Ubiquitous Engineering · doi:10.14257/ijmue.2016.11.1.34 · Cited by 3
Spohn, W. (2010) · Boston studies in the philosophy of science · doi:10.1007/978-90-481-3615-5_5 · Cited by 3
Lemus, M., Faleiro, R., Mateus, P., Paunković, N., & Souto, A. (2024) · Quantum · doi:10.22331/q-2024-01-18-1230 · Cited by 3
Complexity computations in code cracking problems
Simion, E., & Constantinescu, N. (2002) · International Spring Seminar on Electronics Technology · doi:10.1109/isse.2001.931065 · Cited by 3
The Bielefeld School of economics, Post Keynesian economics, and dynamic complexity
Rosser, J. B., & Rosser, M. V. (2023) · Journal of Economic Behavior & Organization · doi:10.1016/j.jebo.2023.05.023 · Cited by 3
Numerical Investigation of Graph Spectra and Information Interpretability of Eigenvalues
Zenil, H., Kiani, N. A., & Tegner, J. N. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-16480-9_39 · Cited by 3
Information-Theoretic Image Reconstruction and Segmentation from Noisy Projections
Visser, G., Dowe, D. L., & Svalbe, I. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10439-8_18 · Cited by 3
A Note on Blum Static Complexity Measures
Câmpeanu, C. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-27654-5_6 · Cited by 3
Multiobjective design of low complexity digital controllers
Whidborne, J. F., & Yang, J. (2003) · IEEE International Symposium on Computer-Aided Control System Design (CACSD) · doi:10.1109/cacsd.2002.1036924 · Cited by 3
Impugning Randomness, Convincingly
Gurevich, Y. G., & Passmore, G. O. (2012) · Studia Logica · doi:10.1007/s11225-012-9375-1 · Cited by 3
On the classification of learning machines
Giorgio Parisi, A. (1992) · Network Computation in Neural Systems · doi:10.1088/0954-898x/3/3/001 · Cited by 3
Metadata
- Authors
- Chaitin, G. J.
- Affiliations
- City College of New York (US)
- Corresponding author
- Chaitin, Gregory J.
- Venue
- Journal of the ACM
- Published
- 1966-10
- Volume
- 13
- Issue
- 4
- Pages
- 547-569
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W1969678783
- Cited by
- 913
- References
- 2
- Citations by year
- 2026: 13 · 2025: 28 · 2024: 16 · 2023: 17 · 2022: 22 · 2021: 40 · 2020: 22 · 2019: 17 · 2018: 32 · 2017: 26 · 2016: 22 · 2015: 32 · 2014: 30 · 2013: 32 · 2012: 40
- FWCI
- 3.65
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Journal of the ACM (publishedVersion)
- Funders
- National Science Foundation
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Keywords
- program duration, Turing machines, information theory, recursive functions, program size, Kolmogorov complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
