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 201–300 of 907
Albrecht, J. (2020) · Geographic Information Science & Technology Body of Knowledge · doi:10.22224/gistbok/2020.2.1 · Cited by 35
System Complexity and Its Measures: How Complex Is Complex
Kinsner, W. (2010) · Studies in computational intelligence · doi:10.1007/978-3-642-16083-7_14 · Cited by 35
On Quantum Effects in a Theory of Biological Evolution
Martin-Delgado, M. A. (2012) · Scientific Reports · doi:10.1038/srep00302 · Cited by 35
Thermodynamic costs of Turing machines
Kolchinsky, A., & Wolpert, D. H. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.033312 · Cited by 35
A cognitive interpretation of organizational complexity
Fioretti, G., & Visser, B. (2004) · EUR Research Repository (Erasmus University Rotterdam) · Cited by 35
Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno’s Theorem
Benatti, F., Krüger, T., Müller, M. P., Siegmund‐Schultze, R., & Szkoła, A. (2006) · Communications in Mathematical Physics · doi:10.1007/s00220-006-0027-z · Cited by 35
Allen, E. B., Gottipati, S., & Govindarajan, R. (2007) · Software Quality Journal · doi:10.1007/s11219-006-9010-3 · Cited by 35
A Fractal Approach to Industry Dynamism
Farjoun, M., & Levin, M. (2011) · Organization Studies · doi:10.1177/0170840611410817 · Cited by 34
Natural halting probabilities, partial randomness, and zeta functions
Calude, C. S., & Stay, M. (2006) · Information and Computation · doi:10.1016/j.ic.2006.07.003 · Cited by 34
Hernández-Orozco, S., Kiani, N. A., & Zenil, H. (2018) · Royal Society Open Science · doi:10.1098/rsos.180399 · Cited by 38
What is Information? A multidimensional concern
Nafría, J. M. D. (2010) · tripleC Communication Capitalism & Critique Open Access Journal for a Global Sustainable Information Society · doi:10.31269/triplec.v8i1.76 · Cited by 34
Some consequences of the existence of pseudorandom generators
Allender, E. (1989) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(89)90021-4 · Cited by 34
Zenil, H., Badillo, L., Hernández-Orozco, S., & Hernández-Quiroz, F. (2018) · International Journal of Parallel Emergent and Distributed Systems · doi:10.1080/17445760.2018.1448932 · Cited by 33
Lombardi, O., Holik, F., & Vanni, L. (2016) · Studies in History and Philosophy of Science Part B Studies in History and Philosophy of Modern Physics · doi:10.1016/j.shpsb.2016.10.001 · Cited by 33
Quantifying loss of information in network-based dimensionality reduction techniques
Zenil, H., Kiani, N. A., & Tegner, J. N. (2015) · Journal of Complex Networks · doi:10.1093/comnet/cnv025 · Cited by 33
Leveraging Environmental Correlations: The Thermodynamics of Requisite Variety
Boyd, A. B., Mandal, D., & Crutchfield, J. P. (2017) · Journal of Statistical Physics · doi:10.1007/s10955-017-1776-0 · Cited by 35
Model discrimination using an algorithmic information criterion
Maciejowski, J. M. (1979) · Automatica · doi:10.1016/0005-1098(79)90006-2 · Cited by 33
Minimum message length encoding and the comparison of macromolecules
Allison, L., & Yee, C. N. (1990) · Bulletin of Mathematical Biology · doi:10.1007/bf02458580 · Cited by 33
Complexity and viability in service ecosystems
Gummesson, E., Mele, C., & Polese, F. (2018) · Marketing Theory · doi:10.1177/1470593118774201 · Cited by 33
Replacing Causal Faithfulness with Algorithmic Independence of Conditionals
Lemeire, J., & Janzing, D. (2012) · Minds and Machines · doi:10.1007/s11023-012-9283-1 · Cited by 32
Some theorems on the algorithmic approach to probability theory and information theory
Levin, L. A. (2010) · Annals of Pure and Applied Logic · doi:10.1016/j.apal.2010.09.007 · Cited by 32
Renyi complexities and information planes: Atomic structure in conjugated spaces
Antolín, J., López‐Rosa, S., & Angulo, J. C. (2009) · Chemical Physics Letters · doi:10.1016/j.cplett.2009.04.061 · Cited by 32
Kiani, N. A., Zenil, H., Olczak, J., & Tegner, J. N. (2016) · Seminars in Cell and Developmental Biology · doi:10.1016/j.semcdb.2016.01.012 · Cited by 32
Young, K., & Crutchfield, J. P. (1994) · Chaos Solitons & Fractals · doi:10.1016/0960-0779(94)90015-9 · Cited by 32
Meyer, A. R., & McCreight, E. M. (1971) · Elsevier eBooks · doi:10.1016/b978-0-12-417750-5.50006-3 · Cited by 32
Grammatical complexity of strange sets
Auerbach, D., & Procaccia, I. (1990) · Physical Review A · doi:10.1103/physreva.41.6602 · Cited by 32
KAMPIS, G., & Csányi, V. (1987) · Journal of Theoretical Biology · doi:10.1016/s0022-5193(87)80256-4 · Cited by 32
Universal MAP estimation in compressed sensing
Baron, D., & Duarte, M. F. (2011) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2011.6120245 · Cited by 31
Modularity, reuse, and hierarchy: Measuring complexity by measuring structure and organization
Hornby, G. S. (2007) · Complexity · doi:10.1002/cplx.20202 · Cited by 31
Svozil, K. (2018) · Fundamental theories of physics · doi:10.1007/978-3-319-70815-7 · Cited by 33
The complexity of hierarchical systems
Ceccatto, H. A., & Huberman, B. A. (1988) · Physica Scripta · doi:10.1088/0031-8949/37/1/021 · Cited by 31
ON KOLMOGOROV MACHINES AND RELATED ISSUES
Gurevich, Y. G. (1993) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789812794499_0017 · Cited by 31
Knowledge and Meaning: Chaos and Complexity
Crutchfield, J. P. (1992) · Woodward Conference · doi:10.1007/978-1-4613-9229-3_3 · Cited by 31
Determinism Is Ontic, Determinability is EpistemicPreprint
Harald Atmanspacher, A. (2001) · PhilSci-Archive (University of Pittsburgh) · Cited by 31
Quantum Algorithmic Complexities and Entropy
Benatti, F. (2009) · Open Systems & Information Dynamics · doi:10.1142/s1230161209000025 · Cited by 30
Complexity and its measures in cognitive and other complex systems
Kinsner, W. (2008) · IEEE International Conference on Cognitive Informatics · doi:10.1109/coginf.2008.4639147 · Cited by 30
Modelling and Complexity Assessment of Assembly Supply Chain Systems
Modrák, V., & Márton, D. (2012) · Procedia Engineering · doi:10.1016/j.proeng.2012.09.536 · Cited by 30
Entropy and complexity of finite sequences as fluctuating quantities
Jiménez-Montaño, M. A., Ebeling, W., Pohl, T., & Rapp, P. E. (2002) · Biosystems · doi:10.1016/s0303-2647(01)00171-x · Cited by 30
Measuring graph abstractions of software: an information-theory approach
Allen, E. B. (2003) · IEEE International Software Metrics Symposium (METRICS) · doi:10.1109/metric.2002.1011337 · Cited by 30
The Problem with Evolutionary Art Is ...
Galanter, P. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12242-2_33 · Cited by 29
Algorithm selection for sorting and probabilistic inference: a machine learning-based approach
Guo, H., & Hsu, W. H. (2003) · Cited by 29
Information in the knowledge acquisition process
Bosančić, B. (2016) · Journal of Documentation · doi:10.1108/jd-10-2015-0122 · Cited by 29
Semantic Information Retrieval
Amati, G., & van Rijsbergen, K. (1998) · Springer eBooks · doi:10.1007/978-1-4615-5617-6_8 · Cited by 29
Basic Elements and Problems of Probability TheoryPreprint
Primas, H. (1999) · PhilSci-Archive (University of Pittsburgh) · Cited by 29
Data compression to define information content of hydrological time series
Weijs, S. V., van de Giesen, N., & Parlange, M. B. (2013) · Hydrology and earth system sciences · doi:10.5194/hess-17-3171-2013 · Cited by 28
Sequential codes, lossless compression of individual sequences, and Kolmogorov complexity
Kieffer, J. C., & Yang, E. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.481775 · Cited by 28
On principles of emergent organization
Rupe, A., & Crutchfield, J. P. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.04.001 · Cited by 33
Borel Normality and Algorithmic Randomness.
Calude, C. S. (1993) · Developments in Language Theory · Cited by 27
Justifying Additive Noise Model-Based Causal Discovery via Algorithmic Information Theory
Janzing, D., & Steudel, B. (2010) · Open Systems & Information Dynamics · doi:10.1142/s1230161210000126 · Cited by 27
Unsupervised Learning of Correlated Multivariate Gaussian Mixture Models Using MML
Agusta, Y., & Dowe, D. L. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-24581-0_40 · Cited by 27
Microscopic and macroscopic entropy
Lindgren, K. (1988) · Physical Review A · doi:10.1103/physreva.38.4794 · Cited by 27
Resource-bounded Kolmogorov complexity of hard languages
Huynh, D. T. (1986) · Lecture notes in computer science · doi:10.1007/3-540-16486-3_97 · Cited by 27
Editorial Comment on the Special Issue of “Information in Dynamical Systems and Complex Systems”
Bollt, E. M., & Sun, J. (2014) · Entropy · doi:10.3390/e16095068 · Cited by 27
On Macrostates in Complex Multi-Scale Systems
Harald Atmanspacher, A. (2016) · Entropy · doi:10.3390/e18120426 · Cited by 26
Entropy, Complexity, Predictability, and Data Analysis of Time Series and Letter Sequences
Ebeling, W., Molgedey, L., Kurths, J., & Schwarz, U. D. (2002) · Springer eBooks · doi:10.1007/978-3-642-56257-0_1 · Cited by 26
Complexity of algorithms and computations
Marchenkov, S. S., & Матросов, В. Л. (1981) · Journal of Mathematical Sciences · doi:10.1007/bf01084283 · Cited by 26
Folkman, L., Pitt, K. A., & Stantić, B. (2025) · Applied Intelligence · doi:10.1007/s10489-024-06224-0 · Cited by 25
Structure and Randomness of Continuous-Time, Discrete-Event Processes
Marzen, S., & Crutchfield, J. P. (2017) · Journal of Statistical Physics · doi:10.1007/s10955-017-1859-y · Cited by 26
Algorithmic complexity of recursive and inductive algorithms
Burgin, M. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2003.12.003 · Cited by 25
Dynamics of a generic Brownian motion: Recursive aspects
Fouché, W. L. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2007.12.010 · Cited by 25
A generalized relative complexity measure
Romera, E., Sen, K. D., & Nagy, Á. (2011) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2011/09/p09016 · Cited by 25
Efficiency Theory : a Unifying Theory for Information, Computation and Intelligence
Yampolskiy, R. V. (2013) · Journal of Discrete Mathematical Sciences and Cryptography · doi:10.1080/09720529.2013.821361 · Cited by 25
The Induction of Dynamical Recognizers
Pollack, J. B. (1991) · Springer eBooks · doi:10.1007/978-1-4615-4008-3_6 · Cited by 25
Algorithmic Information Theory
Chaitin, G. J. (2005) · Wiley eBooks · doi:10.1002/0471667196.ess0029.pub2 · Cited by 25
Self-citationMindstorms in Natural Language-Based Societies of Mind
Zhuge, M., Liu, H., Faccio, F., Ashley, D. R., Csordás, R., Gopalakrishnan, A., Hamdi, A., Hammoud, H. A. A. K., Herrmann, V., Irie, K., et al. (2023) · arXiv · doi:10.48550/arxiv.2305.17066 · Cited by 24
Mindstorms in Natural Language-Based Societies of Mind
Zhuge, M., Liu, H., Faccio, F., Ashley, D. R., Csordás, R., Gopalakrishnan, A., Hamdi, A., Hammoud, H. A. A. K., Herrmann, V., Irie, K., et al. (2025) · Computational Visual Media · doi:10.26599/cvm.2025.9450460 · Cited by 24
Complexism and the Role of Evolutionary Art
Galanter, P. (2007) · Natural computing series · doi:10.1007/978-3-540-72877-1_15 · Cited by 24
Image similarity using the normalized compression distance based on finite context models
Pinho, A. J., & Ferreira, P. J. S. G. (2011) · Proceedings - International Conference on Image Processing · doi:10.1109/icip.2011.6115866 · Cited by 24
Astroglial hydro-ionic waves guided by the extracellular matrix: An exploratory model
Pereira, A. (2017) · Journal of Integrative Neuroscience · doi:10.3233/jin-160003 · Cited by 24
Subjectivity in Inductive Inference
Gilboa, I., & Samuelson, L. (2009) · Theoretical Economics · doi:10.3982/te845 · Cited by 24
López, C. (2018) · Advanced Optical Materials · doi:10.1002/adom.201800439 · Cited by 25
Open Problems in Universal Induction & Intelligence
Hütter, M. (2009) · Algorithms · doi:10.3390/a2030879 · Cited by 24
On the problem of finding minimal programs for tables
Pager, D. (1969) · Information and Control · doi:10.1016/s0019-9958(69)90323-4 · Cited by 24
Life as the Explanation of the Measurement Problem
Łukaszyk, S. (2024) · Journal of Physics Conference Series · doi:10.1088/1742-6596/2701/1/012124 · Cited by 23
On the Approximation of the Kolmogorov Complexity for DNA Sequences
Pratas, D., & Pinho, A. J. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-58838-4_29 · Cited by 23
Statistics and meta-statistics in the concept of complexity
Harald Atmanspacher, A., Rath, C. W., & Wiedenmann, G. (1997) · Physica A Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(96)00293-2 · Cited by 23
Balance of information in bipartite quantum-communication systems: Entanglement-energy analogy
Horodecki, R., Horodecki, M., & Horodecki, P. (2001) · Physical Review A · doi:10.1103/physreva.63.022310 · Cited by 26
Weijs, S. V., & Ruddell, B. L. (2020) · Water Resources Research · doi:10.1029/2019wr026471 · Cited by 27
The complexity landscape of viral genomes
Silva, J. M., Pratas, D., Caetano, T., & Matos, S. (2022) · GigaScience · doi:10.1093/gigascience/giac079 · Cited by 22
Enumerations of the Kolmogorov function
Beigel, R., Buhrman, H., Fejer, P. A., Fortnow, L., Grabowski, P., Longpré, L., Muchnik, A., Stephan, F., & Torenvliet, L. (2006) · Journal of Symbolic Logic · doi:10.2178/jsl/1146620156 · Cited by 22
On the advice complexity of the k-server problem
Böckenhauer, H.-J., Komm, D., Kráľovič, R., & Královič, R. (2017) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2017.01.001 · Cited by 22
Wesolowski, C. A., Yahil, A., Puetter, R. C., Babyn, P., Gilday, D. L., & Khan, M. (2005) · Computerized Medical Imaging and Graphics · doi:10.1016/j.compmedimag.2004.08.003 · Cited by 22
Reconstructing Language Hierarchies
Crutchfield, J. P. (1991) · NATO ASI series. Series B : Physics · doi:10.1007/978-1-4899-2305-9_4 · Cited by 22
Discovery by Minimal Length Encoding: A Case Study in Molecular Evolution
Milosavljević, A., & Jurka, J. (1993) · Machine Learning · doi:10.1007/bf00993061 · Cited by 22
Circuit size relative to pseudorandom oracles
Lutz, J. H., & Schmidt, W. J. (1993) · Theoretical Computer Science · doi:10.1016/0304-3975(93)90256-s · Cited by 22
Structured audio, Kolmogorov complexity, and generalized audio coding
Scheirer, E. D. (2001) · IEEE Transactions on Speech and Audio Processing · doi:10.1109/89.966095 · Cited by 22
Evolution of complexity in real-world domains
Pollack, J. B., & Funes, P. (2001) · Cited by 22
HydroZIP: How Hydrological Knowledge can Be Used to Improve Compression of Hydrological Data
Weijs, S. V., van de Giesen, N., & Parlange, M. B. (2013) · Entropy · doi:10.3390/e15041289 · Cited by 21
Configuration complexity assessment of convergent supply chain systems
Modrák, V., & Márton, D. (2014) · International Journal of General Systems · doi:10.1080/03081079.2014.885512 · Cited by 21
Unbiased pattern detection in microarray data series
Ahnert, S. E., Willbrand, K., Brown, F., & Fink, T. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl121 · Cited by 21
Circular clustering of protein dihedral angles by Minimum Message Length.
Dowe, D. L., Allison, L., Ti, D., Hunter, L., Cs, W., & Edgoose, T. C. (1996) · PubMed · Cited by 21
Salamon, P., Wootton, J. C., Konopka, A. K., & Hansen, L. K. (1993) · Computers & Chemistry · doi:10.1016/0097-8485(93)85005-w · Cited by 21
Minimal-program complexity of pseudo-recursive and pseudo-random sequences
Daley, R. (1975) · Theory of Computing Systems · doi:10.1007/bf01698128 · Cited by 21
Emergence in complex networks of simple agents
Green, D. G. (2023) · Journal of Economic Interaction and Coordination · doi:10.1007/s11403-023-00385-w · Cited by 20
Unraveling complexity in assembly supply chain networks
Modrák, V., Márton, D., Kulpa, W., & Hricová, R. (2012) · IEEE International Symposium on Logistics and Industrial Informatics (LINDI) · doi:10.1109/lindi.2012.6319478 · Cited by 20
Algorithmic Information Dynamics
Zenil, H., Kiani, N. A., Abrahão, F. S., & Tegner, J. N. (2020) · Scholarpedia · doi:10.4249/scholarpedia.53143 · Cited by 20
What Lies Between Order and Chaos?
Crutchfield, J. P. (2003) · Elsevier eBooks · doi:10.1016/b978-044450944-4/50004-9 · Cited by 20
Unsupervised learning of Gamma mixture models using Minimum Message Length
Agusta, Y., & Dowe, D. L. (2003) · Cited by 20
Artificial sequences and complexity measures
Baronchelli, A., Caglioti, E., & Loreto, V. (2005) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2005/04/p04002 · Cited by 20
Complexity Measures for System Architecture Models
Kinnunen, M. (2006) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 20
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
