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
Deep learning in neural networks: an overview
Schmidhuber, J. (2015) · Neural Networks · doi:10.1016/j.neunet.2014.09.003 · Cited by 18,570
How to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. M. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,108
Computation at the edge of chaos: Phase transitions and emergent computation
Langton, C. G. (1990) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(90)90064-v · Cited by 1,527
Inferring statistical complexity
Crutchfield, J. P., & Young, K. (1989) · Physical Review Letters · doi:10.1103/physrevlett.63.105 · Cited by 987
A Theory of Program Size Formally Identical to Information Theory
Chaitin, G. J. (1975) · Journal of the ACM · doi:10.1145/321892.321894 · Cited by 831
Self-citationQuasi-Monte Carlo methods and pseudo-random numbers
Niederreiter, H. (1978) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1978-14532-7 · Cited by 803
The calculi of emergence: computation, dynamics and induction
Crutchfield, J. P. (1994) · Physica D Nonlinear Phenomena · doi:10.1016/0167-2789(94)90273-9 · Cited by 748
Consistent interpretations of quantum mechanics
Omnès, R. (1992) · Reviews of Modern Physics · doi:10.1103/revmodphys.64.339 · Cited by 648
Logical basis for information theory and probability theory
Kolmogorov, A. N. (1968) · IEEE Transactions on Information Theory · doi:10.1109/tit.1968.1054210 · Cited by 588
Mathematical discoveries from program search with large language models
Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., Ellenberg, J. S., Wang, P., Fawzi, O., et al. (2024) · Nature · doi:10.1038/s41586-023-06924-6 · Cited by 544
“In a loose sense, FunSearch attempts to find solutions that have low Kolmogorov complexity 48–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.”
BackgroundEstimation and Inference by Compact Coding
Wallace, C. S., & Freeman, P. R. (1987) · Journal of the Royal Statistical Society Series B (Statistical Methodology) · doi:10.1111/j.2517-6161.1987.tb01695.x · Cited by 521
Easily calculable measure for the complexity of spatiotemporal patterns
Kaspar, F., & Schuster, H. G. (1987) · Physical Review A · doi:10.1103/physreva.36.842 · Cited by 504
Minimum complexity density estimation
Barron, A. R., & Cover, T. M. (1991) · IEEE Transactions on Information Theory · doi:10.1109/18.86996 · Cited by 497
Random sequence generation by cellular automata
Wolfram, S. (1986) · Advances in Applied Mathematics · doi:10.1016/0196-8858(86)90028-x · Cited by 494
Minimization of Boolean complexity in human concept learning
Feldman, J. (2000) · Nature · doi:10.1038/35036586 · Cited by 475
Computational Mechanics: Pattern and Prediction, Structure and Simplicity
Shalizi, C. R., & Crutchfield, J. P. (2001) · Journal of Statistical Physics · doi:10.1023/a:1010388907793 · Cited by 471
Measures of statistical complexity: Why?
Feldman, D. P., & Crutchfield, J. P. (1998) · Physics Letters A · doi:10.1016/s0375-9601(97)00855-4 · Cited by 438
Crutchfield, J. P. (2011) · Nature Physics · doi:10.1038/nphys2190 · Cited by 452
Applying Occam’s razor in modeling cognition: A Bayesian approach
Myung, I. J., & Pitt, M. A. (1997) · Psychonomic Bulletin & Review · doi:10.3758/bf03210778 · Cited by 417
Introduction To Artificial Life
Adami, C. (1998) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.1998.738989 · Cited by 404
Generalized statistical complexity measures: Geometrical and analytical properties
Martín, M. T., Plastino, A. R., & Rosso, O. A. (2006) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2005.11.053 · Cited by 390
Algorithmic randomness and physical entropy
Zurek, W. H. (1989) · Physical Review A · doi:10.1103/physreva.40.4731 · Cited by 371
Benedetto, D., Caglioti, E., & Loreto, V. (2002) · Physical Review Letters · doi:10.1103/physrevlett.88.048702 · Cited by 359
The Search for Simplicity: A Fundamental Cognitive Principle?
Chater, N. (1999) · The Quarterly Journal of Experimental Psychology Section A · doi:10.1080/713755819 · Cited by 336
Verdú, S. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720531 · Cited by 320
Shiner, J. S., Davison, M., & Landsberg, P. T. (1999) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.59.1459 · Cited by 315
Entropy estimation of symbol sequences
Schürmann, T., & Grassberger, P. (1996) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.166191 · Cited by 313
The Induction of Dynamical Recognizers
Pollack, J. B. (1991) · Machine Learning · doi:10.1007/bf00114845 · Cited by 305
Thermodynamic cost of computation, algorithmic complexity and the information metric
Zurek, W. H. (1989) · Nature · doi:10.1038/341119a0 · Cited by 272
Features of the extension of a statistical measure of complexity to continuous systems
Catalán, R. G., de Pablo, J. G., & López‐Ruiz, R. (2002) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.66.011102 · Cited by 263
A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
Trakhtenbrot, B. A. (1984) · IEEE Annals of the History of Computing · doi:10.1109/mahc.1984.10036 · Cited by 260
Almost everywhere high nonuniform complexity
Lutz, J. H. (1992) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(92)90020-j · Cited by 251
Randomness conservation inequalities; information and independence in mathematical theories
Levin, L. A. (1984) · Information and Control · doi:10.1016/s0019-9958(84)80060-1 · Cited by 246
Causal Inference Using the Algorithmic Markov Condition
Janzing, D., & Schölkopf, B. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2060095 · Cited by 230
Lesne, A. (2014) · Mathematical Structures in Computer Science · doi:10.1017/s0960129512000783 · Cited by 241
Causal architecture, complexity and self-organization in time series and cellular automata
Shalizi, C. R., & Olsson, M. (2001) · Cited by 221
Not all (possibly) “random” sequences are created equal
Pincus, S. M., & Kalman, R. E. (1997) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.94.8.3513 · Cited by 194
Kolmogorov Complexity and its Applications
Li, M., & Vitanyi, P. M. B. (1990) · Elsevier eBooks · doi:10.1016/b978-0-444-88071-0.50009-6 · Cited by 188
Complexity of strings in the class of Markov sources
Rissanen, J. (1986) · IEEE Transactions on Information Theory · doi:10.1109/tit.1986.1057210 · Cited by 186
The dimensions of individual strings and sequences
Lutz, J. H. (2003) · Information and Computation · doi:10.1016/s0890-5401(03)00187-1 · Cited by 184
Tendency towards maximum complexity in a nonequilibrium isolated system
Calbet, X., & López‐Ruiz, R. (2001) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.63.066116 · Cited by 183
An overview of computational complexity
Cook, S. A. (1983) · Communications of the ACM · doi:10.1145/358141.358144 · Cited by 181
How To Construct Random Functions
Goldreich, O., Goldwasser, S., & Micali, S. M. (1984) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1984.715949 · Cited by 167
MML clustering of multi-state, Poisson, von Mises circular and Gaussian distributions
Wallace, C. S., & Dowe, D. L. (2000) · Statistics and Computing · doi:10.1023/a:1008992619036 · Cited by 167
Counting probability distributions: Differential geometry and model selection
Myung, I. J., Balasubramanian, V., & Pitt, M. A. (2000) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.170283897 · Cited by 163
Digital Image Reconstruction: Deblurring and Denoising
Puetter, R. C., Gosnell, T. R., & Yahil, A. (2005) · Annual Review of Astronomy and Astrophysics · doi:10.1146/annurev.astro.43.112904.104850 · Cited by 163
Physical complexity of symbolic sequences
Adami, C., & Cerf, N. J. (2000) · Physica D Nonlinear Phenomena · doi:10.1016/s0167-2789(99)00179-7 · Cited by 154
Generalized Kolmogorov complexity and the structure of feasible computations
Hartmanis, J. (1983) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1983.21 · Cited by 149
Thermodynamic depth of causal states: Objective complexity via minimal representations
Crutchfield, J. P., & Shalizi, C. R. (1999) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.59.275 · Cited by 144
Syntactic Measures of Complexity
Edmonds, B. (1999) · Cited by 138
Exact and approximate membership testers
Carter, L., Floyd, R. W., Gill, J. T., III, Markowsky, G., & Wegman, M. N. (1978) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800133.804332 · Cited by 138
Fisher–Shannon plane and statistical complexity of atoms
Angulo, J. C., Antolín, J., & Sen, K. D. (2007) · Physics Letters A · doi:10.1016/j.physleta.2007.07.077 · Cited by 138
Discovering Neural Nets with Low Kolmogorov Complexity and High Generalization Capability
Schmidhuber, J. (1997) · Neural Networks · doi:10.1016/s0893-6080(96)00127-x · Cited by 148
Blum, M. (1967) · Information and Control · doi:10.1016/s0019-9958(67)90546-3 · Cited by 138
Advancing catchment hydrology to deal with predictions under change
Ehret, U., Gupta, H. V., Sivapalan, M., Weijs, S. V., Schymanski, S. J., Blöschl, G., Gelfan, A. N., Harman, C. J., Kleidon, A., Bogaard, T. A., et al. (2014) · Hydrology and earth system sciences · doi:10.5194/hess-18-649-2014 · Cited by 139
Why hydrological predictions should be evaluated using information theory
Weijs, S., Schoups, G., & van de Giesen, N. C. (2010) · Hydrology and earth system sciences · doi:10.5194/hess-14-2545-2010 · Cited by 129
The generation of complexity in evolution: A thermodynamic and information-theoretical discussion
Wicken, J. S. (1979) · Journal of Theoretical Biology · doi:10.1016/0022-5193(79)90361-8 · Cited by 128
Lombardi, O., Holik, F., & Vanni, L. (2015) · Synthese · doi:10.1007/s11229-015-0824-z · Cited by 129
Zenil, H., Hernández-Orozco, S., Kiani, N. A., Toscano, F. S., Rueda-Toicen, A., & Tegner, J. N. (2018) · Entropy · doi:10.3390/e20080605 · Cited by 121
Artificial Intelligence and Advanced Materials
López, C. (2022) · Advanced Materials · doi:10.1002/adma.202208683 · Cited by 123
Origins of randomness in physical systems
Wolfram, S. (1985) · Physical Review Letters · doi:10.1103/physrevlett.55.449 · Cited by 125
A thermodynamic theory of evolution
Wicken, J. S. (1980) · Journal of Theoretical Biology · doi:10.1016/0022-5193(80)90216-7 · Cited by 115
Allender, E., & Rubinstein, R. S. (1988) · SIAM Journal on Computing · doi:10.1137/0217075 · Cited by 114
The Discovery of Algorithmic Probability
Solomonoff, R. J. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1500 · Cited by 110
Berthiaume, A., van Dam, W., & Laplante, S. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1765 · Cited by 107
Estimating the information content of symbol sequences and efficient codes
Grassberger, P. (1989) · IEEE Transactions on Information Theory · doi:10.1109/18.30993 · Cited by 107
Ribeiro, M., Henriques, T. S., Castro, L., Souto, A., Antunes, L. F., Santos, C., & Teixeira, A. (2021) · Entropy · doi:10.3390/e23020222 · Cited by 107
Corominas‐Murtra, B., & Solé, R. V. (2010) · Physical Review E · doi:10.1103/physreve.82.011102 · Cited by 102
On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
Chaitin, G. J. (1969) · Journal of the ACM · doi:10.1145/321526.321530 · Cited by 99
Self-citationA method for parameter calibration and relevance estimation in evolutionary algorithms
Nannen, V., & Eiben, A. E. (2006) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/1143997.1144029 · Cited by 99
Atomic complexity measures in position and momentum spaces
Angulo, J. C., & Antolín, J. (2008) · The Journal of Chemical Physics · doi:10.1063/1.2907743 · Cited by 96
On the Relationship between Complexity and Entropy for Markov Chains and Regular Languages.
Li, W. (1991) · Cited by 94
OPEN-ENDED ARTIFICIAL EVOLUTION
Standish, R. K. (2003) · International Journal of Computational Intelligence and Applications · doi:10.1142/s1469026803000914 · Cited by 93
Symbolic dynamics of one-dimensional maps: Entropies, finite precision, and noise
Crutchfield, J. P., & Packard, N. H. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650178 · Cited by 93
On grammars, complexity, and information measures of biological macromolecules
Ebeling, W., & Jiménez-Montaño, M. A. (1980) · Mathematical Biosciences · doi:10.1016/0025-5564(80)90004-8 · Cited by 95
Computational Aesthetic Evaluation: Past and Future
Galanter, P. (2012) · Springer eBooks · doi:10.1007/978-3-642-31727-9_10 · Cited by 92
The simplicity principle in perception and cognition
Feldman, J. (2016) · Wiley Interdisciplinary Reviews Cognitive Science · doi:10.1002/wcs.1406 · Cited by 102
On Evaluation Metrics in Optimality Theory
Rasin, E., & Katzir, R. (2016) · Linguistic Inquiry · doi:10.1162/ling_a_00210 · Cited by 89
Crutchfield, J. P., Ditto, W. L., & Sinha, S. (2010) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.3492712 · Cited by 89
Commentary on theOrganization ScienceSpecial Issue on Complexity
Cohen, M. (1999) · Organization Science · doi:10.1287/orsc.10.3.373 · Cited by 94
Algorithmic Information Theory
Chaitin, G. J. (2004) · Wiley eBooks · doi:10.1002/0471667196.ess0029 · Cited by 89
Self-citationInformation Complexity of Online Problems
Hromkovic̆, J., Kráľovič, R., & Královič, R. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15155-2_3 · Cited by 88
Approximate Entropy as an Irregularity Measure for Financial Data
Pincus, S. M. (2008) · Econometric Reviews · doi:10.1080/07474930801959750 · Cited by 88
An Asymptotically Random Tausworthe Sequence
Tootill, J. P. R., Robinson, W. D., & Eagle, D. J. (1973) · Journal of the ACM · doi:10.1145/321765.321778 · Cited by 88
To a mathematical definition of 'life'
Chaltin, G. J. (1970) · ACM SIGACT News · doi:10.1145/1247047.1247052 · Cited by 88
Quantifying Hidden Order out of Equilibrium
Martiniani, S., Chaikin, P. M., & Levine, D. (2019) · Physical Review X · doi:10.1103/physrevx.9.011031 · Cited by 87
Low-algorithmic-complexity entropy-deceiving graphs
Zenil, H., Kiani, N. A., & Tegner, J. N. (2017) · Physical review. E · doi:10.1103/physreve.96.012308 · Cited by 84
The emergence of protein complexes: quaternary structure, dynamics and allostery
Perica, T., Marsh, J. A., Sousa, F. L., Natan, E., Colwell, L. J., Ahnert, S. E., & Teichmann, S. A. (2012) · Biochemical Society Transactions · doi:10.1042/bst20120056 · Cited by 87
Universal Algorithmic Intelligence: A Mathematical Top→Down Approach
Hütter, M. (2007) · Cognitive technologies · doi:10.1007/978-3-540-68677-4_8 · Cited by 83
Causal deconvolution by algorithmic generative models
Zenil, H., Kiani, N. A., Zea, A. A., & Tegner, J. N. (2018) · Nature Machine Intelligence · doi:10.1038/s42256-018-0005-0 · Cited by 92
An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems
Zenil, H., Kiani, N. A., Marabita, F., Deng, Y., Éliás, S., Schmidt, A., Ball, G., & Tegner, J. N. (2018) · iScience · doi:10.1016/j.isci.2019.07.043 · Cited by 99
On the notion of infinite pseudorandom sequences
Ko, K. (1986) · Theoretical Computer Science · doi:10.1016/0304-3975(86)90081-2 · Cited by 81
Saunders, P. T., & Ho, M. W. (1981) · Journal of Theoretical Biology · doi:10.1016/0022-5193(81)90303-9 · Cited by 80
On the Advice Complexity of the k-Server Problem
Böckenhauer, H.-J., Komm, D., Kráľovič, R., & Královič, R. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22006-7_18 · Cited by 79
Interpreting neurodynamics: concepts and facts
Harald Atmanspacher, A., & Rotter, S. (2008) · Cognitive Neurodynamics · doi:10.1007/s11571-008-9067-8 · Cited by 79
On order and complexity. I. General considerations
Papentin, F. (1980) · Journal of Theoretical Biology · doi:10.1016/0022-5193(80)90230-1 · Cited by 79
Complexity measures and cellular automata
Lindgren, K. A., & Nordahl, M. G. (1988) · Chalmers Publication Library (Chalmers University of Technology) · doi:10.5555/56123.56125 · Cited by 78
An immunological approach to change detection: theoretical results
D’haeseleer, P. (2002) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csfw.1996.503687 · Cited by 78
Esquivel, R. O., Angulo, J. C., Antolín, J., Dehesa, J. S., López‐Rosa, S., & Flores-Gallegos, N. (2010) · Physical Chemistry Chemical Physics · doi:10.1039/b927055h · Cited by 76
A Review of Graph and Network Complexity from an Algorithmic Information Perspective
Zenil, H., Kiani, N. A., & Tegner, J. N. (2018) · Entropy · doi:10.3390/e20080551 · Cited by 84
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
