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 401–500 of 907
Life sets off a cascade of machines
Tlusty, T., & Libchaber, A. J. (2025) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2418000122 · Cited by 11
Algorithmic Complexity and Reprogrammability of Chemical Structure Networks
Zenil, H., Kiani, N. A., Shang, M.-M., & Tegner, J. N. (2018) · Parallel Processing Letters · doi:10.1142/s0129626418500056 · Cited by 11
Real patterns and indispensability
Suñé, A., & Martínez, M. (2019) · Synthese · doi:10.1007/s11229-019-02343-1 · Cited by 11
Evolutionary tinkering enriches the hierarchical and nested structures in amino acid sequences
Zhang, Z., Liu, C., Zhu, Y., Lu, P., Qiu, W., Tang, Q.-Y., He, L., Zhang, K., Di, Z., & Liu, Y. (2024) · Physical Review Research · doi:10.1103/physrevresearch.6.023215 · Cited by 11
Assembly theory and its relationship with computational complexity
Kempes, C. P., Lachmann, M., Iannaccone, A., Fricke, G. M., Chowdhury, M. R., Walker, S. I., & Cronin, L. (2025) · npj Complexity · doi:10.1038/s44260-025-00049-9 · Cited by 11
Information Theory for Risk-based Water System Operation
Weijs, S. V. (2011) · Research Repository (Delft University of Technology) · doi:10.4233/uuid:8d7290d3-a903-4cfe-8c12-0387b94a192e · Cited by 11
On the improbability of algorithmic specified complexity
Ewert, W., Marks, R. J., & Dembski, W. A. (2013) · 45th Southeastern Symposium on System Theory · doi:10.1109/ssst.2013.6524962 · Cited by 11
Zenil, H., Kiani, N. A., & Tegner, J. N. (2019) · Entropy · doi:10.3390/e21060560 · Cited by 11
Complexity and Emergence in Engineering Systems
Chen, C., Nagl, S., & Clack, C. D. (2008) · Studies in computational intelligence · doi:10.1007/978-3-540-88075-2_5 · Cited by 11
Algorithmic complexity of real financial markets
Mansilla, R. (2001) · Physica A Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(01)00434-4 · Cited by 11
An Operational Characterization of Mutual Information in Algorithmic Information Theory
Romashchenko, A., & Zimand, M. (2019) · Journal of the ACM · doi:10.1145/3356867 · Cited by 11
MML Clustering of Continuous-Valued Data Using Gaussian and t Distributions
Agusta, Y., & Dowe, D. L. (2002) · Lecture notes in computer science · doi:10.1007/3-540-36187-1_13 · Cited by 11
A decision graph explanation of protein secondary structure prediction
Dowe, D. L., Oliver, J., Dix, T. I., Allison, L., & Wallace, C. S. (2002) · Hawaii International Conference on System Sciences (HICSS) · doi:10.1109/hicss.1993.270674 · Cited by 11
Dynamical properties and energy landscape of simple globular proteins
Krupyanskiǐ, Y. F., & Гольданский, В. И. (2002) · Uspekhi Fizicheskih Nauk · doi:10.3367/ufnr.0172.200211b.1247 · Cited by 11
Minimum message length clustering: an explication and some applications to vegetation data
Dale, M. B., Salmina, L., & Mucina, L. (2001) · Community Ecology · doi:10.1556/comec.2.2001.2.11 · Cited by 11
Succinct representation random strings, and complexity classes
Peterson, G. L. (1980) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1980.42 · Cited by 11
On sets with easy certificates and the existence of one-way permutations
Hemaspaandra, L. A., Rothe, J., & Wechsung, G. (1997) · Lecture notes in computer science · doi:10.1007/3-540-62592-5_78 · Cited by 11
Noncomplex sequences: characterizations and examples
Daley, R. (1976) · Journal of Symbolic Logic · doi:10.1017/s0022481200051197 · Cited by 11
Distinguishing Cause and Effect via Second Order Exponential ModelsPreprint
Janzing, D., Sun, X., & Schölkopf, B. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0910.5561 · Cited by 11
Algorithmic Complexity in Real Financial MarketsPreprint
Mansilla, R. (n.d.) · RePEc: Research Papers in Economics · Cited by 11
Enhancing metagenomic classification with compression-based features
Silva, J. M., & Almeida, J. R. (2024) · Artificial Intelligence in Medicine · doi:10.1016/j.artmed.2024.102948 · Cited by 10
Development of Metrics and a Complexity Scale for the Topology of Assembly Supply Chains
Modrák, V., & Márton, D. (2013) · Entropy · doi:10.3390/e15104285 · Cited by 10
The representation and manipulation of the algorithmic probability measure for problem solving
Gammerman, A. (1991) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/bf01531061 · Cited by 10
The dynamics of exchange rate time series and the chaos game
Cristescu, C., Stan, C., & Scarlat, E. I. (2009) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2009.08.005 · Cited by 10
Effective entropies and data compression
Huyn, D. T. (1991) · Information and Computation · doi:10.1016/0890-5401(91)90060-f · Cited by 10
Measuring complexity by measuring structure and organization
Hornby, G. S. (2007) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2007.4424721 · Cited by 10
Stochastic complexity in learning
Rissanen, J. (1995) · Lecture notes in computer science · doi:10.1007/3-540-59119-2_178 · Cited by 10
A Network of Autoregressive Processing Units for Time Series Modeling
Lehtokangas, M. I., Saarinen, J. P. P., Kaski, K. K., & Huuhtanen, P. (1996) · Applied Mathematics and Computation · doi:10.1016/0096-3003(95)00122-0 · Cited by 10
Quantitative characterization of complexity and predictability
Badii, R. (1991) · Physics Letters A · doi:10.1016/0375-9601(91)90668-x · Cited by 10
Almost everywhere high nonuniform complexity
Lutz, J. H. (2003) · Structure in Complexity Theory Annual Conference · doi:10.1109/sct.1989.41813 · Cited by 10
Complexity in Science: Syntaxis Versus Semantics
Arecchi, F. T. (1998) · CNS Spectrums · doi:10.1017/s1092852900005368 · Cited by 10
A note on the instance complexity of pseudorandom sets
Ko, K.-I. (2003) · Structure in Complexity Theory Annual Conference · doi:10.1109/sct.1992.215407 · Cited by 10
Werner, E. J. (1995) · Lecture notes in computer science · doi:10.1007/3-540-61157-6_19 · Cited by 10
Unfolding Complexity in Nonlinear Dynamical Systems
Badii, R. (1989) · NATO ASI series. Series B : Physics · doi:10.1007/978-1-4757-0623-9_46 · Cited by 10
Fiorini, R. A. (2017) · Advances in knowledge acquisition, transfer, and management book series/Advances in knowledge acquisition, transfer and management book series · doi:10.4018/978-1-5225-2443-4.ch011 · Cited by 9
Exploratory analysis of spatiotemporal patterns of cellular automata by clustering compressibility
Emmert‐Streib, F. (2010) · Physical Review E · doi:10.1103/physreve.81.026103 · Cited by 9
Information: Concept Clarification and Theoretical Representation
Burgin, M. (2011) · tripleC Communication Capitalism & Critique Open Access Journal for a Global Sustainable Information Society · doi:10.31269/triplec.v9i2.284 · Cited by 9
Devine, S. D. (2015) · Biosystems · doi:10.1016/j.biosystems.2015.11.008 · Cited by 9
Lee, J., & Dewhurst, J. (2021) · European Journal for Philosophy of Science · doi:10.1007/s13194-020-00341-6 · Cited by 9
A Kolmogorov complexity-based Genetic Programming tool for string compression
Falco, I. D., Iazzetta, A., Tarantino, E., Cioppa, A. D., & Trautteur, G. (2000) · Cited by 9
Shiner–Davison–Landsberg complexity revisited
Stoop, R., Stoop, N., Kern, A., & Steeb, W. ‐. (2005) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2005/11/p11009 · Cited by 9
Cryptographic Security of Individual Instances
Antunes, L. F., Laplante, S., Pinto, A., & Salvador, L. C. M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10230-1_17 · Cited by 9
Incompleteness, Complexity, Randomness and Beyond
Calude, C. S. (2002) · Minds and Machines · doi:10.1023/a:1021132605507 · Cited by 9
Complexity and forecasting in dynamical systems
Grassberger, P. (2008) · Springer eBooks · doi:10.1007/3-540-50316-1_1 · Cited by 9
Several results in program size complexity
Katseff, H. P., & Sipser, M. (1981) · Theoretical Computer Science · doi:10.1016/0304-3975(81)90083-9 · Cited by 9
Binary Sequences and Redundancy
Kak, S. C. (1974) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1974.5408465 · Cited by 9
Toward an abstract theory of data compression
Storer, J. A. (1983) · Theoretical Computer Science · doi:10.1016/0304-3975(83)90001-4 · Cited by 9
Machine Learning: When and Where the Horses Went Astray?
Diamant, E. (2010) · InTech eBooks · doi:10.5772/9156 · Cited by 8
Quantifying complexity in the minority game
Rajković, M., & Mihailović, Z. (2003) · Physica A Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(03)00181-x · Cited by 8
Complexity Analysis of Escher’s Art
Lopes, A. M., & Machado, J. A. T. (2019) · Entropy · doi:10.3390/e21060553 · Cited by 8
What Is Artificial General Intelligence?
Bennett, M. T. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-00686-8_4 · Cited by 9
Delahaye, J.-P. (1993) · Springer eBooks · doi:10.1007/978-94-015-8208-7_8 · Cited by 8
Natural Versus "universal" Probability, Complexity, And Entropy
Denker, J. S., & LeCun, Y. (2005) · Workshop on Physics and Computation (PhysComp) · doi:10.1109/phycmp.1992.615508 · Cited by 8
Finding Unknown Repeated Patterns In Images
Ferreira, P. J. S. G., & Pinho, A. J. (2011) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.42555 · Cited by 8
Invariance as a Tool for Ontology of Information
Schroeder, M. J. (2016) · Information · doi:10.3390/info7010011 · Cited by 8
Tate, S. R. (2003) · Elsevier eBooks · doi:10.1016/b978-012620861-0/50003-6 · Cited by 8
Improving the Scalability of Generative Representations for Openended Design
Hornby, G. S. (2007) · Springer eBooks · doi:10.1007/978-0-387-76308-8_8 · Cited by 8
Modeling Complexity for Interactive Art Works on the Internet
Sommerer, C., & Mignonneau, L. (2003) · Elsevier eBooks · doi:10.1016/b978-044450944-4/50010-4 · Cited by 8
Green, D. G., Liu, J., & Abbass, H. A. (2013) · Springer eBooks · doi:10.1007/978-1-4419-8423-4 · Cited by 8
Entropy and algorithmic complexity in quantum information theory
Benatti, F. (2006) · Natural Computing · doi:10.1007/s11047-006-9017-5 · Cited by 8
Algorithmic Specified Complexity in the Game of Life
Ewert, W., Dembski, W. A., & Marks, R. J. (2014) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2014.2331917 · Cited by 8
Infotropism as the underlying principle of perceptual organization
Thornton, C. (2014) · Journal of Mathematical Psychology · doi:10.1016/j.jmp.2014.08.002 · Cited by 8
Linear Complexity versus Pseudorandomness: On Beth and Dai’s Result
Wang, Y. (1999) · Lecture notes in computer science · doi:10.1007/978-3-540-48000-6_23 · Cited by 8
Algorithmic complexity in the minority game
Mansilla, R. (2000) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.62.4553 · Cited by 8
Scaling behaviour of entropy estimates
Schürmann, T. (2002) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/35/7/308 · Cited by 8
Nannen, V. (2003) · Cited by 8
Some Basic Problems with Complex Systems
Harald Atmanspacher, A., & Wiedenmann, G. (1998) · IFAC Proceedings Volumes · doi:10.1016/s1474-6670(17)41939-2 · Cited by 8
Kolmogorov Complexity, Complexity Cores, and the Distribution of Hardness
Juedes, D. W., & Lutz, J. H. (1992) · Springer eBooks · doi:10.1007/978-3-642-77735-6_4 · Cited by 8
Descriptive Complexity and Reflective Properties of Combinatorial Configurations
Fouché, W. L. (1996) · Journal of the London Mathematical Society · doi:10.1112/jlms/54.1.199 · Cited by 8
Topics in Statistical Pattern Recognition
Cover, T. M., & Wagner, T. J. (1976) · Communication and cybernetics · doi:10.1007/978-3-642-96303-2_2 · Cited by 8
Complexity and Information Theory
de Luca, A. (1975) · Springer eBooks · doi:10.1007/978-3-7091-3008-7_7 · Cited by 8
Taufemback, C. G., Giglio, R., & Silva, S. D. (2011) · RePEc: Research Papers in Economics · Cited by 7
Analysing Music with Point-Set Compression Algorithms
Meredith, D. (2015) · Springer eBooks · doi:10.1007/978-3-319-25931-4_13 · Cited by 7
Quantifying Dirac hydrogenic effects via complexity measures
Bouvrie, P. A., López‐Rosa, S., & Dehesa, J. S. (2012) · Physical Review A · doi:10.1103/physreva.86.012507 · Cited by 7
Analysis of Data Complexity in Human DNA for Gene-Containing Zone Prediction
Monge, R. E., & Crespo, J. (2015) · Entropy · doi:10.3390/e17041673 · Cited by 7
Shallow Reductionism and the Problem of Complexity in Psychology
Brattico, P. (2008) · Theory & Psychology · doi:10.1177/0959354308091840 · Cited by 7
Luckiness and Regret in Minimum Description Length Inference
de Rooij, S., & Grünwald, P. (2011) · Elsevier eBooks · doi:10.1016/b978-0-444-51862-0.50029-0 · Cited by 7
Comparison of complexity measures for DNA sequence analysis
Monge, R. E., & Crespo-Mariño, J. L. (2014) · IEEE International Work Conference on Bioinspired Intelligence (IWOBI) · doi:10.1109/iwobi.2014.6913941 · Cited by 7
Complexity versus Complex Systems: A New Approach to Scientific Discovery
Arecchi, F. T. (1999) · Springer eBooks · doi:10.1007/978-1-4615-4813-3_12 · Cited by 7
Calculating Cognitive Augmentation – A Case Study
Fulbright, R. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-22419-6_38 · Cited by 7
Complexity study of q -deformed quantum harmonic oscillator
Nutku, F., Sen, K. D., & Aydıner, E. (2019) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2019.122041 · Cited by 7
Toward a Simulation Model Complexity Measure
Thompson, J. S., Hodson, D. D., Grimaila, M. R., Hanlon, N., & Dill, R. (2023) · Information · doi:10.3390/info14040202 · Cited by 7
Quantum Kolmogorov complexity and quantum key distribution
Miyadera, T., & Imai, H. (2009) · Physical Review A · doi:10.1103/physreva.79.012324 · Cited by 7
Zenil, H., Kiani, N. A., & Tegner, J. N. (2018) · Entropy · doi:10.3390/e20070534 · Cited by 7
Uncomputability and Physical Law
Lloyd, S. (2017) · Theory and applications of computability · doi:10.1007/978-3-319-43669-2_6 · Cited by 7
Calude, C. S. (1996) · Springer eBooks · doi:10.1007/978-3-642-80350-5_5 · Cited by 7
On computational limitations of neural network architectures
Hoffmann, A. G. (2002) · IEEE Symposium on Parallel and Distributed Processing (SPDP) · doi:10.1109/spdp.1990.143652 · Cited by 7
Pseudorandom Generators: A Primer
Goldreich, O. (2008) · Cited by 7
Low-Depth Witnesses are Easy to Find
Antunes, L. F., Fortnow, L., Pinto, A., & Souto, A. (2007) · Computational Complexity · doi:10.1007/s00037-011-0025-1 · Cited by 7
Solow, D. (2000) · Complexity · doi:10.1002/1099-0526(200009/10)6:1 · Cited by 7
Papentin, F. (1980) · Die Naturwissenschaften · doi:10.1007/bf01086295 · Cited by 7
Inductive Inference by Using Information Compression
Choi, B. (2003) · Computational Intelligence · doi:10.1111/1467-8640.00218 · Cited by 7
Savage, J. E. (1975) · Springer eBooks · doi:10.1007/978-3-7091-3008-7_6 · Cited by 7
Signal Recovery in Compressed Sensing via Universal PriorsPreprint
Baron, D., & Duarte, M. F. (2012) · arXiv (Cornell University) · Cited by 7
LISP program-size complexity III
Chaitin, C. J. (1992) · Applied Mathematics and Computation · doi:10.1016/0096-3003(92)90101-6 · Cited by 7
Floridi, L. (2025) · Philosophy & Technology · doi:10.1007/s13347-025-00968-4 · Cited by 7
One-Way Functions Using Algorithmic and Classical Information Theories
Antunes, L. F., Matos, A. B., Pinto, A., Souto, A., & Teixeira, A. (2012) · Theory of Computing Systems · doi:10.1007/s00224-012-9418-z · Cited by 6
A comparison of two approaches to pseudorandomness
Wang, Y. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00311-5 · Cited by 6
Quantum Chaos and Quantum Randomness—Paradigms of Entropy Production on the Smallest Scales
Dittrich, T. (2019) · Entropy · doi:10.3390/e21030286 · Cited by 7
Computational Creativity and Aesthetics with Algorithmic Information Theory
Mondol, T., & Brown, D. G. (2021) · Entropy · doi:10.3390/e23121654 · Cited by 6
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
