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
Flagged first, then by citations
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 101–200 of 907
Physical models as tests of randomness
Vattulainen, I., Ala-Nissilä, T., & Kankaala, K. (1995) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.52.3205 · Cited by 75
Entropy, information, and computation
Machta, J. L. (1999) · American Journal of Physics · doi:10.1119/1.19085 · Cited by 74
Recursively enumerable reals and Chaitin Ω numbers
Calude, C. S., Hertling, P. H., Khoussainov, B., & Wang, Y. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(99)00159-0 · Cited by 73
Relations Between Varieties of Kolmogorov Complexities
Uspensky, V., & Shen', A. K. (1996) · Theory of Computing Systems · doi:10.1007/bf01201280 · Cited by 72
Endliche Automaten und Zufallsfolgen
Schnorr, C. P., & Stimm, H. (1972) · Acta Informatica · doi:10.1007/bf00289514 · Cited by 71
An Information Theoretic Framework for Classifying Exoplanetary System Architectures
Gilbert, G. J., & Fabrycky, D. C. (2020) · The Astronomical Journal · doi:10.3847/1538-3881/ab8e3c · Cited by 82
Feldman, J. (2003) · Journal of Mathematical Psychology · doi:10.1016/s0022-2496(02)00025-1 · Cited by 75
Puetter, R. C. (1995) · International Journal of Imaging Systems and Technology · doi:10.1002/ima.1850060405 · Cited by 69
A generalized statistical complexity measure: Applications to quantum systems
López‐Ruiz, R., Nagy, Á., Romera, E., & Jaime Sañudo, A. (2009) · Journal of Mathematical Physics · doi:10.1063/1.3274387 · Cited by 70
Does the universe in fact contain almost no informationPreprint
Tegmark, M. (1996) · Cited by 68
Gales and the Constructive Dimension of Individual Sequences
Lutz, J. H. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45022-x_76 · Cited by 67
Wan, H., & Wootton, J. C. (2000) · Computers & Chemistry · doi:10.1016/s0097-8485(00)80008-x · Cited by 67
Complexity–entropy analysis of daily stream flow time series in the continental United States
Serinaldi, F., Zunino, L., & Rosso, O. A. (2013) · Stochastic Environmental Research and Risk Assessment · doi:10.1007/s00477-013-0825-8 · Cited by 66
Gershenfeld, N., & Weigand, A. S. (1993) · International Conference on Neural Information Processing · Cited by 66
Heat diffusion: Thermodynamic depth complexity of networks
Escolano, F., Hancock, E. R., & Lozano, M. Á. (2012) · Physical Review E · doi:10.1103/physreve.85.036206 · Cited by 66
Finite-state models in the alignment of macromolecules
Allison, L., Wallace, C. S., & Yee, C. N. (1992) · Journal of Molecular Evolution · doi:10.1007/bf00160262 · Cited by 65
A Theory of Universal Artificial Intelligence based on Algorithmic ComplexityPreprint
Hütter, M. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0004001 · Cited by 65
Complexity of Dirac–Fock atom increases with atomic number
Borgoo, A., Proft, F. D., Geerlings, P., & Sen, K. D. (2007) · Chemical Physics Letters · doi:10.1016/j.cplett.2007.07.003 · Cited by 63
Sets with small generalized Kolmogorov complexity
Balc�zar, J. L., & Book, R. V. (1986) · Acta Informatica · doi:10.1007/bf00264313 · Cited by 62
Self-assembly, modularity, and physical complexity
Ahnert, S. E., Johnston, I. G., Fink, T. M. A., Doye, J. P. K., & Louis, A. A. (2010) · Physical Review E · doi:10.1103/physreve.82.026117 · Cited by 62
Algorithmic complexity for psychology: a user-friendly implementation of the coding theorem method
Gauvrit, N., Singmann, H., Toscano, F. S., & Zenil, H. (2015) · Behavior Research Methods · doi:10.3758/s13428-015-0574-3 · Cited by 61
Algorithmic complexity for short binary strings applied to psychology: a primer
Gauvrit, N., Zenil, H., Delahaye, J.-P., & Toscano, F. S. (2013) · Behavior Research Methods · doi:10.3758/s13428-013-0416-0 · Cited by 64
THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS
Hütter, M. (2002) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054102001199 · Cited by 63
On the syntactic structure of protein sequences and the concept of grammar complexity
Jiménez-Montaño, M. A. (1984) · Bulletin of Mathematical Biology · doi:10.1007/bf02459508 · Cited by 60
A Survey of the Theory of Random Sequences
Schnorr, C. P. (1977) · Springer eBooks · doi:10.1007/978-94-017-0837-1_12 · Cited by 60
On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy
Morzy, M., Kajdanowicz, T. J., & Kazienko, P. (2017) · Complexity · doi:10.1155/2017/3250301 · Cited by 59
Dowe, D. L. (2008) · The Computer Journal · doi:10.1093/comjnl/bxm117 · Cited by 58
An Introduction to Design Arguments
Jantzen, B. C. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9780511793882 · Cited by 58
Hypercomputation: computing more than the Turing machine
Ord, T. (2002) · Oxford University Research Archive (ORA) (University of Oxford) · doi:10.48550/arxiv.math/0209332 · Cited by 58
MML, Hybrid Bayesian Network Graphical Models, Statistical Consistency, Invariance and Uniqueness
Dowe, D. L. (2011) · Elsevier eBooks · doi:10.1016/b978-0-444-51862-0.50030-7 · Cited by 57
Comparison of SDL and LMC measures of complexity: Atoms as a testbed
Panos, C. P., Chatzisavvas, K. C., Moustakidis, C. C., & Kyrkou, E. G. (2006) · Physics Letters A · doi:10.1016/j.physleta.2006.10.075 · Cited by 56
On hausdorff and topological dimensions of the kolmogorov complexity of the real line
Cai, J., & Hartmanis, J. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80073-x · Cited by 56
Holzinger, A., Hörtenhuber, M., Mayer, C. C., Bachler, M., Wassertheurer, S., Pinho, A. J., & Koslicki, D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-43968-5_12 · Cited by 58
Methods of information theory and algorithmic complexity for network biology
Zenil, H., Kiani, N. A., & Tegner, J. N. (2016) · Seminars in Cell and Developmental Biology · doi:10.1016/j.semcdb.2016.01.011 · Cited by 57
Image Similarity Using Sparse Representation and Compression Distance
Guha, T., & Ward, R. K. (2014) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2014.2306175 · Cited by 54
A geometric approach to complexity
Ay, N., Olbrich, E., Bertschinger, N., & Jost, J. (2011) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.3638446 · Cited by 55
Entropy Measures vs. Kolmogorov Complexity
Teixeira, A., Matos, A. B., Souto, A., & Antunes, L. F. (2011) · Entropy · doi:10.3390/e13030595 · Cited by 54
Computational depth and reducibility
Juedes, D. W., Lathrop, J. I., & Lutz, J. H. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)00014-x · Cited by 54
On the difficulty of computations
Chaitin, G. J. (1970) · IEEE Transactions on Information Theory · doi:10.1109/tit.1970.1054390 · Cited by 53
Self-citationA calculation of the probability of spontaneous biogenesis by information theory
Yockey, H. (1977) · Journal of Theoretical Biology · doi:10.1016/0022-5193(77)90044-3 · Cited by 53
Hierarchical approach to complexity with applications to dynamical systems
D’Alessandro, G., & Politi, A. (1990) · Physical Review Letters · doi:10.1103/physrevlett.64.1609 · Cited by 53
Biological Information as Set-Based Complexity
Galas, D. J., Nykter, M., Carter, G. W., Price, N. D., & Shmulevich, I. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2037046 · Cited by 52
López‐Rosa, S., Angulo, J. C., & Antolín, J. (2009) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2009.01.037 · Cited by 52
Power prediction in mobile communication systems using an optimal neural-network structure
Gao, X., Gao, X. Z., Tanskanen, J. M. A., & Ovaska, S. J. (1997) · IEEE Transactions on Neural Networks · doi:10.1109/72.641467 · Cited by 52
Two decades of applied Kolmogorov complexity: in memoriam Andrei Nikolaevich Kolmogorov 1903-87
Li, M., & Vitanyi, P. M. B. (1988) · Structure in Complexity Theory Annual Conference · doi:10.1109/sct.1988.5265 · Cited by 52
A Short Introduction to Model Selection, Kolmogorov Complexity and Minimum Description Length (MDL)Preprint
Nannen, V. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1005.2364 · Cited by 52
Order and information in the patterns of spinning magnetic micro-disks at the air-water interface
Wang, W., Gardi, G., Malgaretti, P., Kishore, V., Koens, L., Son, D., Gilbert, H. B., Wu, Z., Harwani, P., Lauga, E., et al. (2022) · Science Advances · doi:10.1126/sciadv.abk0685 · Cited by 51
Does the universe in fact contain almost no information?
Tegmark, M. (1996) · Foundations of Physics Letters · doi:10.1007/bf02186207 · Cited by 56
Cutting, J. E. (2021) · doi:10.1093/oso/9780197567777.001.0001 · Cited by 52
Barbieri, M. (2016) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2015.0060 · Cited by 50
A statistical complexity measure with nonextensive entropy and quasi-multiplicativity
Yamano, T. (2004) · Journal of Mathematical Physics · doi:10.1063/1.1695600 · Cited by 49
Computational Complexity and Probability Constructions
Willis, D. G. (1970) · Journal of the ACM · doi:10.1145/321574.321578 · Cited by 49
The Algorithmic Complexity of Landscapes
Papadimitriou, F. (2012) · Landscape Research · doi:10.1080/01426397.2011.650628 · Cited by 48
Finkelstein, D., & Finkelstein, S. R. (1983) · International Journal of Theoretical Physics · doi:10.1007/bf02085960 · Cited by 48
Simulating the spatial and temporal dynamics of landscapes using generic and complex models
Bolliger, J., Lischke, H., & Green, D. G. (2005) · Ecological Complexity · doi:10.1016/j.ecocom.2004.11.005 · Cited by 48
Complexity and Dynamical Depth
Deacon, T. W., & Koutroufinis, S. A. (2014) · Information · doi:10.3390/info5030404 · Cited by 48
Foundations of Support Constraint Machines
Gnecco, G., Gori, M., Melacci, S., & Sanguineti, M. (2014) · Neural Computation · doi:10.1162/neco_a_00686 · Cited by 47
Statistical complexity and Fisher–Shannon information measure of H+2
Montgomery, H. E., Jr., & Sen, K. D. (2007) · Physics Letters A · doi:10.1016/j.physleta.2007.11.041 · Cited by 47
Sequence complexity for biological sequence analysis
Allison, L., Stern, L., Edgoose, T., & Dix, T. I. (2000) · Computers & Chemistry · doi:10.1016/s0097-8485(00)80006-6 · Cited by 46
The Logical Underpinnings of Intelligent Design
Dembski, W. A. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511804823.018 · Cited by 45
Any code of which we cannot think is good
Coffey, J. T., & Goodman, R. M. (1990) · IEEE Transactions on Information Theory · doi:10.1109/18.59944 · Cited by 45
Complexity and Scientific Modelling
Edmonds, B. (2000) · Foundations of Science · doi:10.1023/a:1011383422394 · Cited by 45
Beyond crystals: the dialectic of materials and informationPreprint
Cartwright, J. H. E., & Mackay, A. L. (2016) · Cited by 45
A study of the Classical Differential Evolution control parameters
Peñuñuri, F., Cab, C., Carvente, O., Zambrano-Arjona, M. A., & Tapia, J. A. (2015) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2015.08.003 · Cited by 44
Beyond crystals: the dialectic of materials and information
Cartwright, J. H. E., & Mackay, A. L. (2012) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2012.0106 · Cited by 44
Compression of strings with approximate repeats.
Allison, L., Edgoose, T. C., & Dix, T. I. (1998) · PubMed · Cited by 44
A Simplicity Criterion for Physical Computation
Millhouse, T. (2017) · The British Journal for the Philosophy of Science · doi:10.1093/bjps/axx046 · Cited by 43
Complexity analysis of ionization processes and isoelectronic series
Antolín, J., & Angulo, J. C. (2008) · International Journal of Quantum Chemistry · doi:10.1002/qua.21832 · Cited by 43
QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS
Mora, C. E., Briegel, H. J., & Kraus, B. (2007) · International Journal of Quantum Information · doi:10.1142/s0219749907003171 · Cited by 43
Three subsets of sequence complexity and their relevance to biopolymeric information
Abel, D. L., & Trevors, J. T. (2005) · Theoretical Biology and Medical Modelling · doi:10.1186/1742-4682-2-29 · Cited by 43
Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
Lutz, J. H., & Lutz, N. (2018) · ACM Transactions on Computation Theory · doi:10.1145/3201783 · Cited by 43
A theory of information structure I. General principles
Leyton, M. (1986) · Journal of Mathematical Psychology · doi:10.1016/0022-2496(86)90011-8 · Cited by 43
Data compression and learning in time sequences analysis
Andrea Puglisi, B., Benedetto, D., Caglioti, E., Loreto, V., & Vulpiani, A. (2003) · Physica D Nonlinear Phenomena · doi:10.1016/s0167-2789(03)00047-2 · Cited by 45
Algorithmic complexity of points in dynamical systems
White, H. S. (1993) · Ergodic Theory and Dynamical Systems · doi:10.1017/s0143385700007653 · Cited by 43
Arithmetical representations of Brownian motion I
Fouché, W. L. (2000) · Journal of Symbolic Logic · doi:10.2307/2586546 · Cited by 42
Spike-time encoding as a data compression technique for pattern recognition of temporal data
Sengupta, N., & Kasabov, N. K. (2017) · Information Sciences · doi:10.1016/j.ins.2017.04.017 · Cited by 42
Exploring Statistical and Population Aspects of Network Complexity
Emmert‐Streib, F., & Dehmer, M. (2012) · PLoS ONE · doi:10.1371/journal.pone.0034523 · Cited by 44
Recursively enumerable reals and chaitin Ω numbers
Calude, C. S., Hertling, P. H., Khoussainov, B., & Wang, Y. (1998) · Lecture notes in computer science · doi:10.1007/bfb0028594 · Cited by 42
Sequences and Codes: Fundamentals of Biomolecular Cryptology
Konopka, A. K. (1994) · Elsevier eBooks · doi:10.1016/b978-0-08-092596-7.50008-3 · Cited by 42
Tape versus queue and stacks: The lower bounds
Li, M., & Vitanyi, P. M. B. (1988) · Information and Computation · doi:10.1016/0890-5401(88)90003-x · Cited by 42
Complexity analysis of the stock market
Park, J. B., Lee, J. W., Yang, J., Jo, H.-H., & Moon, H. (2007) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2006.12.042 · Cited by 41
Information Theory: a Multifaceted Model of Information
Burgin, M. (2003) · Entropy · doi:10.3390/e5020146 · Cited by 41
Stochastic Complexity in Learning
Rissanen, J. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1501 · Cited by 41
Luengo, E. A., & Villaizán, J. R. (2023) · Mathematics · doi:10.3390/math11234812 · Cited by 40
ALGORITHMIC INFORMATION THEORY
Grünwald, P., & Vitanyi, P. M. B. (2008) · Elsevier eBooks · doi:10.1016/b978-0-444-51726-5.50013-3 · Cited by 40
Algorithmic Information Content, Church — Turing Thesis, Physical Entropy, and Maxwell’s Demon
Zurek, W. H. (1991) · NATO ASI series. Series B : Physics · doi:10.1007/978-1-4899-2305-9_20 · Cited by 40
Classification of Random Binary Sequences Using Walsh-Fourier Analysis
Kak, S. C. (1971) · IEEE Transactions on Electromagnetic Compatibility · doi:10.1109/temc.1971.303131 · Cited by 39
INFORMATION IN COMPUTER SCIENCE
Dunn, J. M. (2008) · Elsevier eBooks · doi:10.1016/b978-0-444-51726-5.50019-4 · Cited by 39
A method to discern complexity in two-dimensional patterns generated by coupled map lattices
SANCHEZ, J. R., & López‐Ruiz, R. (2005) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2005.02.058 · Cited by 39
Effective normalization of complexity measurements for epoch length and sampling frequency
Rapp, P. E., Cellucci, C. J., Korslund, K. E., Watanabe, T., & Jiménez-Montaño, M. A. (2001) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.64.016209 · Cited by 39
The nomological argument for the existence of God
Hildebrand, T., & Metcalf, T. (2022) · Noûs · doi:10.1111/nous.12364 · Cited by 38
The Descriptive Complexity of Brownian Motion
Fouché, W. L. (2000) · Advances in Mathematics · doi:10.1006/aima.2000.1945 · Cited by 38
MDLChunker: A MDL‐Based Cognitive Model of Inductive Learning
Robinet, V., Lemaire, B., & Gordon, M. B. (2011) · Cognitive Science · doi:10.1111/j.1551-6709.2011.01188.x · Cited by 38
Antunes, L. F., & Fortnow, L. (2003) · Lecture notes in computer science · doi:10.1007/3-540-45061-0_23 · Cited by 38
Estimating Algorithmic Information Using Quantum Computing for Genomics Applications
Sarkar, A., Al-Ars, Z., & Bertels, K. (2021) · Applied Sciences · doi:10.3390/app11062696 · Cited by 38
Triple-aspect monism: A conceptual framework for the science of human consciousness
Pereira, A. (2013) · Cambridge University Press eBooks · doi:10.1017/cbo9781139207065.011 · Cited by 37
Conformation-dependent evolution of copolymer sequences
Khalatur, P. G., Novikov, V. V., & Khokhlov, A. R. (2003) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.67.051901 · Cited by 37
Quantitative limits on the ability of a Maxwell demon to extract work from heat
Caves, C. M. (1990) · Physical Review Letters · doi:10.1103/physrevlett.64.2111 · Cited by 37
Minimum Complexity Pursuit for Universal Compressed Sensing
Jalali, S., Maleki, A., & Baraniuk, R. G. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2014.2302005 · Cited by 36
Benchmark development for the evaluation of visualization for data mining
Laskowski, S. J., Grinstein, G., Hoffman, P., & Pickett, R. M. (1999) · doi:10.6028/nist.ir.6287 · Cited by 36
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
