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 301–400 of 907
Esquivel, R. O., Molina‐Espíritu, M., Dehesa, J. S., Angulo, J. C., & Antolín, J. (2012) · International Journal of Quantum Chemistry · doi:10.1002/qua.24219 · Cited by 19
Constraints vs Controls~!2009-07-15~!2010-01-20~!2010-06-23~!
Abel, D. L. (2010) · The Open Cybernetics & Systemics Journal · doi:10.2174/1874110x01004010014 · Cited by 19
Statistical Complexity and Fisher-Shannon Information: Applications
López‐Ruiz, R., Jaime Sañudo, A., Romera, E., & Calbet, X. (2011) · Springer eBooks · doi:10.1007/978-90-481-3890-6_4 · Cited by 19
Analysis of Negotiation Processes
Koeszegi, S. T., & Vetschera, R. (2010) · Advances in group decision and negotiation/Advances in group decision and negotation · doi:10.1007/978-90-481-9097-3_8 · Cited by 19
Berthiaume, A., van Dam, W., & Laplante, S. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2000.856755 · Cited by 19
Primas, H., & Müller‐Herold, U. (1978) · Advances in chemical physics · doi:10.1002/9780470142578.ch1 · Cited by 19
Esquivel, R. O., Molina‐Espíritu, M., López‐Rosa, S., Soriano‐Correa, C., Barrientos‐Salcedo, C., Kohout, M., & Dehesa, J. S. (2015) · ChemPhysChem · doi:10.1002/cphc.201500282 · Cited by 18
How well do practical information measures estimate the Shannon entropy
Speidel, U., Titchener, M. R., & Jia, Y. (2006) · Cited by 18
Disentangling Complexity from Randomness and Chaos
Zuchowski, L. C. (2012) · Entropy · doi:10.3390/e14020177 · Cited by 19
Kolmogorov complexity of sequences of random numbers generated in Bell's experiments
Kovalsky, M. G., Hnilo, A. A., & Agüero, M. (2018) · Physical Review A · doi:10.1103/physreva.98.042131 · Cited by 20
On graph entropy measures based on the number of independent sets and matchings
Wan, P., Chen, X., Tu, J., Dehmer, M., Zhang, S., & Emmert‐Streib, F. (2019) · Information Sciences · doi:10.1016/j.ins.2019.11.020 · Cited by 18
Pinho, A. J., Garcia, S. P., Pratas, D., & Ferreira, P. J. S. G. (2013) · PLoS ONE · doi:10.1371/journal.pone.0079922 · Cited by 18
Solomonoff, R. J. (1975) · Cited by 18
Zauner, K. (2005) · Lecture notes in computer science · doi:10.1007/11527800_4 · Cited by 18
On the inference of optimal descriptions
Daley, R. (1977) · Theoretical Computer Science · doi:10.1016/0304-3975(77)90015-9 · Cited by 18
A Conjecture on a Fundamental Trade-Off Between Certainty and Scope in Symbolic and Generative AI
Floridi, L. (2025) · Philosophy & Technology · doi:10.1007/s13347-025-00927-z · Cited by 18
On the Existence and Uniqueness of the Scientific Method
Wagensberg, J. (2014) · Biological Theory · doi:10.1007/s13752-014-0166-y · Cited by 17
Recovery From Linear Measurements With Complexity-Matching Universal Signal Estimation
Zhu, J., Baron, D., & Duarte, M. F. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2393845 · Cited by 17
Information density, structure and entropy in equilibrium and non-equilibrium systems
Zu, M., Bupathy, A., Frenkel, D., & Sastry, S. (2020) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ab684b · Cited by 17
Küppers, B. (2013) · Springer eBooks · doi:10.1007/978-3-642-34997-3_4 · Cited by 17
On The Logical Foundations of Probability Theory
Shiryayev, A. N. (1992) · Springer eBooks · doi:10.1007/978-94-011-2260-3_53 · Cited by 17
A Subjective Measure of Complexity
Fioretti, G. (1999) · Advances in Complex Systems · doi:10.1142/s0219525999000187 · Cited by 17
Formal definitions of information and knowledge and their role in growth through structural change
Hilbert, M. (2016) · Structural Change and Economic Dynamics · doi:10.1016/j.strueco.2016.03.004 · Cited by 18
A Cognitive Approach to Organizational Complexity
Fioretti, G., & Visser, B. (2006) · Springer eBooks · doi:10.1007/0-387-28898-8_35 · Cited by 17
Easily adaptable complexity measure for finite time series
Ke, D., & Qin-ye, T. (2008) · Physical Review E · doi:10.1103/physreve.77.066215 · Cited by 17
The Insights of Algorithmic Entropy
Devine, S. (2009) · Entropy · doi:10.3390/e11010085 · Cited by 17
Sommerer, C., & Mignonneau, L. (2002) · Leonardo · doi:10.1162/00240940252940531 · Cited by 17
The Kolmogorov complexity of infinite words
Ludwig Staiger, B. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2007.04.013 · Cited by 17
Sequence Complexity and Composition
Konopka, A. K. (2005) · Wiley eBooks · doi:10.1038/npg.els.0005260 · Cited by 17
Task-based differences in brain state dynamics and their relation to cognitive ability
Kurtin, D. L., Scott, G., Hebron, H., Skeldon, A. C., & Violante, I. R. (2023) · NeuroImage · doi:10.1016/j.neuroimage.2023.119945 · Cited by 16
Perceptual Information Integration: Hypothetical Role of Astrocytes
Pereira, A. (2011) · Cognitive Computation · doi:10.1007/s12559-011-9120-5 · Cited by 16
On Potential Cognitive Abilities in the Machine Kingdom
Hernández‐Orallo, J., & Dowe, D. L. (2013) · Minds and Machines · doi:10.1007/s11023-012-9299-6 · Cited by 16
Azmi, E., Ehret, U., Weijs, S. V., Ruddell, B. L., & Perdigão, R. A. P. (2021) · Hydrology and earth system sciences · doi:10.5194/hess-25-1103-2021 · Cited by 16
Automatic analysis of artistic paintings using information-based measures
Silva, J. M., Pratas, D., Antunes, R., Matos, S., & Pinho, A. J. (2021) · Pattern Recognition · doi:10.1016/j.patcog.2021.107864 · Cited by 16
Statistic Complexity: Combining Kolmogorov Complexity with an Ensemble Approach
Emmert‐Streib, F. (2010) · PLoS ONE · doi:10.1371/journal.pone.0012256 · Cited by 16
Mechanisms of directed evolution of morphological structures and the problems of morphogenesis
Melkikh, A. V., & Khrennikov, A. Y. (2018) · Biosystems · doi:10.1016/j.biosystems.2018.04.004 · Cited by 16
Probing complexity: thermodynamics and computational mechanics approaches to origins studies
Bartlett, S., & Beckett, P. (2019) · Interface Focus · doi:10.1098/rsfs.2019.0058 · Cited by 16
Symbolic representation of probabilistic worlds
Feldman, J. (2012) · Cognition · doi:10.1016/j.cognition.2011.12.008 · Cited by 16
Lectures on Statistical Modeling Theory
Rissanen, J. (2005) · Cited by 16
Measuring complexity with zippersPreprint
Baronchelli, A., Caglioti, E., & Loreto, V. (2006) · Cited by 16
Information-theoretical complexity for the hydrogenic identity S N 2 exchange reaction
Molina‐Espíritu, M., Esquivel, R. O., Angulo, J. C., Antolín, J., & Dehesa, J. S. (2012) · Journal of Mathematical Chemistry · doi:10.1007/s10910-012-0009-7 · Cited by 15
Atomic and Molecular Complexities: Their Physical and Chemical Interpretations
Angulo, J. C., Antolín, J., & Esquivel, R. O. (2011) · Springer eBooks · doi:10.1007/978-90-481-3890-6_6 · Cited by 15
Ladderpath Approach: How Tinkering and Reuse Increase Complexity and Information
Liu, Y., Di, Z., & Gerlee, P. (2022) · Entropy · doi:10.3390/e24081082 · Cited by 15
The Information-Theoretic and Algorithmic Approach to Human, Animal, and Artificial Cognition
Gauvrit, N., Zenil, H., & Tegner, J. N. (2017) · Studies in applied philosophy, epistemology and rational ethics · doi:10.1007/978-3-319-43784-2_7 · Cited by 15
Signatures of infinity: Nonergodicity and resource scaling in prediction, complexity, and learning
Crutchfield, J. P., & Marzen, S. (2015) · Physical Review E · doi:10.1103/physreve.91.050106 · Cited by 15
Simplicity and likelihood: An axiomatic approach
Gilboa, I., & Schmeidler, D. (2010) · Journal of Economic Theory · doi:10.1016/j.jet.2010.03.010 · Cited by 15
ON SYSTEM PROPERTIES AND SYSTEMHOOD
Shenhar, A. J. (1990) · International Journal of General Systems · doi:10.1080/03081079008935136 · Cited by 15
Probabilistic automata as a model for epigenesis of cellular networks
Milgram, M., & Atlan, H. (1983) · Journal of Theoretical Biology · doi:10.1016/0022-5193(83)90281-3 · Cited by 15
APPROXIMATE, NON-DETERMINISTIC MODELLING OF BEHAVIOUR SEQUENCES
Witten, I. H. (1979) · International Journal of General Systems · doi:10.1080/03081077908960883 · Cited by 15
Laing, R. (1976) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(76)80028-1 · Cited by 15
Programmable active matter across scales
Yu, H., Fu, Y., Zhang, X.-L., Chen, L. X., Qi, D., Shi, J., & Wang, W. (2023) · Programmable Materials · doi:10.1017/pma.2023.6 · Cited by 14
Algorithmic complexity of motifs clusters superfamilies of networks
Zenil, H., Kiani, N. A., & Tegner, J. N. (2013) · IEEE International Conference on Bioinformatics and Biomedicine (BIBM) · doi:10.1109/bibm.2013.6732768 · Cited by 14
Text Classification Using Compression-Based Dissimilarity Measures
Coutinho, D., & Figueiredo, M. A. T. (2015) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001415530043 · Cited by 14
Afsar, O., Bagci, G. B., & Tirnakli, U. (2013) · The European Physical Journal B · doi:10.1140/epjb/e2013-40184-2 · Cited by 14
Complexity as a contrast between dynamics and phenomenology
Zuchowski, L. C. (2018) · Studies in History and Philosophy of Science Part B Studies in History and Philosophy of Modern Physics · doi:10.1016/j.shpsb.2017.12.003 · Cited by 14
Drinić, M., Kirovski, D., & Vo, H. (2007) · ACM Transactions on Programming Languages and Systems · doi:10.1145/1180475.1180478 · Cited by 14
Complexity and Chaos - State-of-the-Art; Formulations and Measures of Complexity
Couture, M. (2007) · Defense Technical Information Center (DTIC) · Cited by 14
Measuring complexity with zippers
Baronchelli, A., Caglioti, E., & Loreto, V. (2005) · European Journal of Physics · doi:10.1088/0143-0807/26/5/s08 · Cited by 14
Eine Bemerkung zum Begriff der zuf�lligen Folge
Schnorr, C.-P. (1969) · Probability Theory and Related Fields · doi:10.1007/bf00534115 · Cited by 14
Gene splicing: Spatial separation of overlapping messages
Trifonov, E. N. (1993) · Computers & Chemistry · doi:10.1016/0097-8485(93)80026-a · Cited by 14
Berwick and Weinberg on linguistics and computational psychology
Stabler, E. P. (1984) · Cognition · doi:10.1016/0010-0277(84)90017-9 · Cited by 13
Comparison of Compression-Based Measures with Application to the Evolution of Primate Genomes
Pratas, D., Silva, R. M., & Pinho, A. J. (2018) · Entropy · doi:10.3390/e20060393 · Cited by 13
Correlation Lengths in the Language of Computable Information
Martiniani, S., Lemberg, Y., Chaikin, P. M., & Levine, D. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.170601 · Cited by 13
Deflating the deflationary view of information
Lombardi, O., Fortín, S., & López, C. (2015) · European Journal for Philosophy of Science · doi:10.1007/s13194-015-0128-7 · Cited by 13
An unpredictability approach to finite-state randomness
O'Connor, M. G. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90011-6 · Cited by 13
Algorithmic treatment of the spin-echo effect
Lloyd, S., & Zurek, W. H. (1991) · Journal of Statistical Physics · doi:10.1007/bf01017985 · Cited by 13
Online Makespan Scheduling with Sublinear Advice
Dohrau, J. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46078-8_15 · Cited by 13
Fast Spectral Tests for Measuring Nonrandomness and the DES
Feldman, F. A. (1988) · Lecture notes in computer science · doi:10.1007/3-540-48184-2_22 · Cited by 13
Algorithmic complexity as a criterion of unsolvability
Burgin, M. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2007.04.011 · Cited by 13
The Lempel–Ziv Complexity of Fixed Points of Morphisms
Constantinescu, S., & Ilie, L. (2007) · SIAM Journal on Discrete Mathematics · doi:10.1137/050646846 · Cited by 13
Thermodynamics of random number generation
Aghamohammadi, C., & Crutchfield, J. P. (2017) · Physical review. E · doi:10.1103/physreve.95.062139 · Cited by 13
On generalized kolmogorov complexity
Balcázar, J. L., & Book, R. V. (1986) · Lecture notes in computer science · doi:10.1007/3-540-16078-7_87 · Cited by 13
The discovery of algorithmic probability: A guide for the programming of true creativity
Solomonoff, R. J. (1995) · Lecture notes in computer science · doi:10.1007/3-540-59119-2_165 · Cited by 13
On the structural complexity of simple biosystems
Yagil, G. (1985) · Journal of Theoretical Biology · doi:10.1016/s0022-5193(85)80114-4 · Cited by 13
Introductory Statistics and Random Phenomena
Lin, Y., Denker, M., & Woyczyński, W. A. (1999) · Technometrics · doi:10.1080/00401706.1999.10485688 · Cited by 13
Topics in Statistical Pattern Recognition
Cover, T. M., & Wagner, T. J. (1980) · Communication and cybernetics · doi:10.1007/978-3-642-67740-3_2 · Cited by 13
Undecidability in physics: A review
Perales, Á., Cubitt, T. S., Gu, M., Pérez-García, D., & Wolf, M. M. (2025) · Physics Reports · doi:10.1016/j.physrep.2025.06.004 · Cited by 22
Measuring structural similarity of semistructured data based on information-theoretic approaches
Helmer, S., Augsten, N., & Böhlen, M. H. (2012) · The VLDB Journal · doi:10.1007/s00778-012-0263-0 · Cited by 12
Minimum Description Length Recurrent Neural Networks
Lan, N., Geyer, M., Chemla, E., & Katzir, R. (2022) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00489 · Cited by 15
Introduction to Ray Solomonoff 85th Memorial Conference
Dowe, D. L. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-44958-1_1 · Cited by 12
Structural Complexity of Assembly Supply Chains: A Theoretical Framework
Modrák, V., & Márton, D. (2013) · Procedia CIRP · doi:10.1016/j.procir.2013.05.008 · Cited by 12
$LT^2C^2$ : A language of thought with Turing-computable Kolmogorov complexity
Romano, S., Sigman, M., & Figueira, S. D. (2013) · Papers in Physics · doi:10.4279/pip.050001 · Cited by 12
Permutation approach, high frequency trading and variety of micro patterns in financial time series
Aghamohammadi, C., Ebrahimian, M., & Tahmooresi, H. (2014) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2014.06.027 · Cited by 12
Cognitive Augmentation Metrics Using Representational Information Theory
Fulbright, R. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-58625-0_3 · Cited by 13
Noise and Synthetic Biology: How to Deal with Stochasticity?
Casanova, M. P. (2020) · NanoEthics · doi:10.1007/s11569-020-00366-4 · Cited by 12
Štambuk, N., & Konjevoda, P. (2003) · International Journal of Quantum Chemistry · doi:10.1002/qua.10499 · Cited by 12
Minimum Message Length Clustering of Spatially-Correlated Data with Varying Inter-Class Penalties
Visser, G., & Dowe, D. L. (2007) · IEEE/ACIS International Conference on Computer and Information Science (ICIS) · doi:10.1109/icis.2007.134 · Cited by 12
No communication without manipulation: A causal-deflationary view of information
López, C., & Lombardi, O. (2018) · Studies in History and Philosophy of Science Part A · doi:10.1016/j.shpsa.2018.06.003 · Cited by 14
Hertling, P. H., & Weihrauch, K. (1998) · Lecture notes in computer science · doi:10.1007/bfb0055103 · Cited by 12
Dowe, D. L. (2008) · Social Epistemology · doi:10.1080/02691720802576291 · Cited by 12
Informational parameters and randomness of mitochondrial DNA
Granero-Porati, M. I., & Porati, A. (1988) · Journal of Molecular Evolution · doi:10.1007/bf02138369 · Cited by 12
An Example of Information and Computation Resource Trade-Off
Daley, R. (1973) · Journal of the ACM · doi:10.1145/321784.321794 · Cited by 12
Physical complexity and Zipf's law
G�nther, R., Schapiro, B., & Wagner, P. (1992) · International Journal of Theoretical Physics · doi:10.1007/bf00740003 · Cited by 12
Random Sets in Subrecursive Hierarchies
Paola, R. A. D. (1969) · Journal of the ACM · doi:10.1145/321541.321551 · Cited by 12
Complexity Invariance by Replication in the Quantum Square Well
López‐Ruiz, R., & Jaime Sañudo, A. (2009) · Open Systems & Information Dynamics · doi:10.1142/s1230161209000311 · Cited by 12
Complexity and Unpredictable Scaling of Hierarchical Structures
Badii, R. (1992) · NATO ASI series. Series B : Physics · doi:10.1007/978-1-4615-3464-8_1 · Cited by 12
Regression Estimation from an Individual Stable Sequence
Morvai, G., Kulkarni, S. R., & Nobel, A. B. (1999) · Statistics · doi:10.1080/02331889908802686 · Cited by 12
An upward measure separation theorem
Lutz, J. H. (1991) · Theoretical Computer Science · doi:10.1016/0304-3975(91)90320-2 · Cited by 12
On solving hard problems by polynomial-size circuits
Huynh, D. T. (1987) · Information Processing Letters · doi:10.1016/0020-0190(87)90181-5 · Cited by 12
Alan Turing and the Foundation of Computer Science
Hromkovic̆, J. (2015) · Springer eBooks · doi:10.1007/978-3-319-22156-4_10 · Cited by 11
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
