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 701–800 of 907
From Claude Shannon’s Information Entropy to Spike-Time Data Compression Theory
Kasabov, N. K. (2018) · Springer series on bio- and neurosystems · doi:10.1007/978-3-662-57715-8_21 · Cited by 1
LIGO series, dimension of embedding and Kolmogorov’s complexity
Kovalsky, M. G., & Hnilo, A. A. (2021) · Astronomy and Computing · doi:10.1016/j.ascom.2021.100465 · Cited by 1
Observations on Computability, Uncertainty, and Technology
Rosser, J. B. (2021) · Springer eBooks · doi:10.1007/978-3-030-58131-2_15 · Cited by 1
Li, M., & Vitanyi, P. M. B. (1997) · Springer eBooks · doi:10.1007/978-1-4757-2606-0_2 · Cited by 1
Citera, E. (2022) · Springer eBooks · doi:10.1007/978-981-19-3296-0_7 · Cited by 1
Necessary Condition of Self-Organisation in Nonextensive Open Systems
Afsar, O., & Tırnaklı, U. (2023) · Entropy · doi:10.3390/e25030517 · Cited by 1
Inductive knowledge under dominance
Campi, M. C. (2023) · Synthese · doi:10.1007/s11229-023-04172-9 · Cited by 1
Meaning in Action: a Qualitative Approach of Information
ȘTEFAN, G. (2023) · Romanian Journal of Information Science and Technology · doi:10.59277/romjist.2023.3-4.03 · Cited by 1
Fairness and Randomness in Machine Learning: Statistical Independence and Relativization
Derr, R., & Williamson, R. C. (2024) · The New England Journal of Statistics in Data Science · doi:10.51387/24-nejsds73 · Cited by 2
The optimisation of functional brain network dynamics when learning to perform complex tasks
Parkin, B., Daws, R. E., Scott, G., Soreq, E., Leech, R., Hellyer, P. J., & Hampshire, A. (2025) · Neuropsychologia · doi:10.1016/j.neuropsychologia.2025.109188 · Cited by 1
Complex Systems and the Evolution of Computability
Mainzer, K. (2004) · Springer eBooks · doi:10.1007/978-3-662-05364-5_5 · Cited by 1
Harald Atmanspacher, A., Thomas Filk, A., Finke, R., & Gruber, G. (2010) · The Open Cybernetics & Systemics Journal · doi:10.2174/1874110x01004010006 · Cited by 1
Oracle Hypermachines Faced with the Verification Problem
Franchette, F. (2013) · Studies in applied philosophy, epistemology and rational ethics · doi:10.1007/978-3-642-37225-4_13 · Cited by 1
Niitsoo, M. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33272-2_7 · Cited by 1
Antunes, L. F., Souto, A., & Teixeira, A. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-30870-3_4 · Cited by 1
Entropy measures vs. algorithmic information
Teixeira, A., Souto, A., Matos, A. B., & Antunes, L. F. (2010) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2010.5513643 · Cited by 1
Information measures for infinite sequences
Antunes, L. F., & Souto, A. (2010) · Theoretical Computer Science · doi:10.1016/j.tcs.2010.03.026 · Cited by 1
Quantum Entropy and Complexity
Benatti, F., Oskouei, S. K., & Abad, A. S. D. (2017) · Open Systems & Information Dynamics · doi:10.1142/s1230161217500056 · Cited by 1
About the Concept of Information
Fortín, S., & Lombardi, O. (2017) · Cambridge University Press eBooks · doi:10.1017/9781316494233.003 · Cited by 1
An Information Theoretic Analysis of Random Number Generator based on Cellular Automaton
Nayyeri, A., & Dastghaibyfard, G. (2018) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2018.090144 · Cited by 1
Devine, S. (2018) · Entropy · doi:10.3390/e20100798 · Cited by 1
A LEARNING-THEORETIC CHARACTERISATION OF MARTIN-LÖF RANDOMNESS AND SCHNORR RANDOMNESS
Blando, F. Z. (2019) · The Review of Symbolic Logic · doi:10.1017/s175502031900042x · Cited by 1
Intelligent Computing: Oxymoron?
Schroeder, M. J. (2020) · International Society for the Study of Information Summit (IS4SI Summit) · doi:10.3390/proceedings2020047031 · Cited by 1
Blackledge, J., & Mosola, N. (2020) · Arrow - TU Dublin (Technological University Dublin) · Cited by 1
Computable Approaches to Rational Choice and Decision-Making
Seo, H., & Thorson, S. J. (2021) · Hawaii International Conference on System Sciences (HICSS) · doi:10.24251/hicss.2021.171 · Cited by 1
Information Similarity Metrics in Information Security and Forensics
Quach, T. (2009) · Cited by 1
The Web and Flow of Popular Cinema
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0013 · Cited by 1
Martino, L., Luengo, D., & Mı́guez, J. (2018) · Statisctics and computing/Statistics and computing · doi:10.1007/978-3-319-72634-2_1 · Cited by 1
Grinin, L. E., Леонидович, Г. А., & Леонидович, Г. И. (2023) · Философия и общество · doi:10.30884/jfio/2023.04.01 · Cited by 2
Randomness Behaviour in Blum Universal Static Complexity Spaces
Câmpeanu, C. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31623-4_10 · Cited by 1
Using Algorithms as Keys in Stream Ciphers
Wagner, N. R., Putter, P. S., & Cain, M. R. (2007) · Springer eBooks · doi:10.1007/3-540-39805-8_18 · Cited by 1
ON VON MISES "REGELLOSIGKEITSAXIOM"
Landro, A. H. (2010) · Cuadernos del CIMBAGE · Cited by 1
Scalassara, P. R. (2009) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/t.18.2009.tde-03122009-085230 · Cited by 1
Complexity of computing pseudorandom sequences
Agafonov, V. N. (1968) · Algebra and Logic · doi:10.1007/bf02218627 · Cited by 1
Generative Complexity and Randomness of Finite Sequence of Symbols
Nozaki, A. (1976) · Behaviormetrika · doi:10.2333/bhmk.3.29 · Cited by 1
Non-uniform complexity classes and random languages
Mundhenk, M., & Schuler, R. (2002) · Structure in Complexity Theory Annual Conference · doi:10.1109/sct.1990.113960 · Cited by 1
Kobayashi, K. (1997) · IEEE Transactions on Information Theory · doi:10.1109/18.568693 · Cited by 1
Modelling errors in restriction mapping
MacKenzie, T., Platt, D., & Dix, T. I. (2002) · Hawaii International Conference on System Sciences (HICSS) · doi:10.1109/hicss.1993.270679 · Cited by 1
Approximating Algorithmic Complexity
Rodda, O., & Figures, L. O. (2011) · Cited by 1
Thermodynamics and Complex Systems
Saunders, P. T., & Ho, M. W. (1986) · Springer eBooks · doi:10.1007/978-94-009-4718-4_18 · Cited by 1
Position Paper: Towards Transparent Machine LearningPreprint
Juliano, D. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.06612 · Cited by 1
La géographie cellulaire. Esquisse d'une épistémologie géographique des automates cellulaires
Ourednik, A. (2005) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 1
Observement as Universal MeasurementPreprint
Green, D. G., Morgan, K. J., & Cheong, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.12095 · Cited by 1
No system can be improved in all respects
Marcus, S. (1998) · De Gruyter eBooks · doi:10.1515/9783110801194.143 · Cited by 1
(2006) · Studies in computational intelligence · doi:10.1007/978-3-540-33461-3_6 · Cited by 1
Sunehag, P., & Hütter, M. (2015) · Elsevier eBooks · doi:10.1016/b978-0-08-097086-8.43001-1 · Cited by 1
Łukaszyk, S. (2024) · Preprints.org · doi:10.20944/preprints202212.0045.v20 · Cited by 1
Information Theory-Based Measurement of Software
Allen, E. B. (2011) · Birkhäuser Boston eBooks · doi:10.1007/978-0-8176-4904-3_12 · Cited by 1
Guichaoua, C. (2017) · theses.fr (ABES) · doi:10.70675/7de2d8eazec1cz4c90zbe28zdd4970f08e6e · Cited by 1
A generic and adaptive approach to explainable AI in autonomic systems : the case of the smart home
Houzé, É. (2022) · theses.fr (ABES) · doi:10.70675/cd5e3060zd7a7z4c5czb731z7a240fad0c49 · Cited by 1
Sobre la Complejidadde una columna de gas perfectoen un campo de gravedad constante
Monroy, Á. C. (2003) · Redalyc (Universidad Autónoma del Estado de México)
Armless Climbing and Walking in Robotics
Maki, K. (2007) · doi:10.5772/5500
Implementing a support vector machine in a message length framework
Kornienko, L. (2022) · Figshare · doi:10.26180/19562575
Eye Movements and the Complexity of Visual Processing
Pavel, M., & Cunningham, H. A. (1996) · Springer series in perception engineering · doi:10.1007/978-1-4612-3984-0_4
Run-Length-Encoded Compression Scheme
Babu, T. R., Murty, M. N., & Subrahmanya, S. V. (2013) · Advances in computer vision and pattern recognition · doi:10.1007/978-1-4471-5607-9_3
Pragmatic Computational Biology: Sequence Analysis and Biological Systems Description
Konopka, A. K. (2006) · Wiley-VCH eBooks · doi:10.1002/3527600906.mcb.200400132
Kolmogorov-Complexity Based on Infinite Computations
Hotz, G. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03456-5_4
Complexity: A Language-Theoretic Point of View
Calude, C. S., & Hromkovic̆, J. (1997) · Springer eBooks · doi:10.1007/978-3-662-07675-0_1
An Algorithmic Information Theory Critique of Statistical Arguments for Intelligent DesignPreprint
Devine, S. D. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0901.0399
Algorithmic Problem ComplexityPreprint
Burgin, M. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0807.0672
Information Theory, Kolmogorov Complexity and Algorithmic Probability in Network BiologyPreprint
Zenil, H., & Tegner, J. N. (2014) · arXiv (Cornell University)
Comparing Notions of Computational Entropy
Pinto, A. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73001-9_63
Life Spacies and Life Spacies II: modelling complex systems for interactive art
Sommerer, C., & Mignonneau, L. (2010) · Artnodes · doi:10.7238/a.v0i9.778
An effective Procedure for Speeding up AlgorithmsPreprint
Hütter, M. (2001) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0102018
Not only a lack of right definitions: Arguments for a shift in information-processing paradigmPreprint
Diamant, E. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1009.0077
Axiomatizing Kolmogorov Complexity
Taveneaux, A. (2012) · Theory of Computing Systems · doi:10.1007/s00224-012-9395-2
Minimum Message Length and Classical Methods for Model Selection in Univariate Polynomial Regression
Viswanathan, M., Yang, Y.-K., & Whangbo, T. K. (2005) · ETRI Journal · doi:10.4218/etrij.05.0104.0180
Phenomenal experience and the measure of information
DeLancey, C. (2007) · Erkenntnis · doi:10.1007/s10670-006-9024-z
Complex Properties of Grammars
Abramson, F. G., Breitbart, Y. J., & Lewis, F. D. (1980) · Journal of the ACM · doi:10.1145/322203.322210
Triviality and Minimality in the Degrees of Monotone Complexity
Calhoun, W. C. (2010) · Journal of Logic and Computation · doi:10.1093/logcom/exq003
Finite approximate approach to the study of the complexity of recursive predicates
Freidson, R. I. (1978) · Journal of Soviet Mathematics · doi:10.1007/bf01091745
Estimating product evolution graph using Kolmogorov complexity
Hayase, Y., Kanda, T., & Ishio, T. (2015) · International Workshop on Principles of Software Evolution · doi:10.1145/2804360.2804368
Generation of symmetric exponential sums
Sergeyev, Y. D. (2004) · Journal of Number Theory · doi:10.1016/j.jnt.2004.04.010
Response to “Comment on ‘Exact solutions to chaotic and stochastic systems’ ” [Chaos 13, 123 (2003)]
González, J. A., Reyes, L., & Guerrero, L. E. (2003) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.1532191
Theory construction in psychology: The interpretation and integration of psychological data
Becker, G. M., & K�hler, E. (1981) · Theory and Decision · doi:10.1007/bf00126282
Veres, S. M. (1990) · International Journal of Control · doi:10.1080/00207179008953543
A framework for generating and complexity assessment of assembly supply chains
Modrák, V., & Márton, D. (2012) · International Conference on Nonlinear Science and Complexity (NSC) · doi:10.1109/nsc.2012.6304712
Representation and Measure of Structural InformationPreprint
Ishikawa, H. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0711.4508
Munshaw, S. (2010) · DukeSpace (Duke University)
Algorithmen – Berechenbarkeit und Komplexität
Ernst, H., Schmidt, J., & Beneken, G. (2015) · Springer eBooks · doi:10.1007/978-3-658-01628-9_11
Church’s Theorem and Randomness
Mar, G. R. (2001) · Springer eBooks · doi:10.1007/978-94-010-0526-5_23
Levels of Abstraction and the Apparent Contradictory Philosophical Legacy of Turing and ShannonPreprint
Zenil, H. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.1099
No information without manipulationPreprint
Lombardi, O., López, C., & Fortín, S. (2015) · PhilSci-Archive (University of Pittsburgh)
Angulo, J. C., & Antolín, J. (2009) · Progress in theoretical chemistry and physics · doi:10.1007/978-90-481-2596-8_20
Complexity and Stochastic Synchronization in Coupled Map Lattices and Cellular AutomataPreprint
López‐Ruiz, R., & SANCHEZ, J. R. (2010) · arXiv (Cornell University) · doi:10.5772/intechopen.83862
GENERALIZED KOLMOGOROVCOMPLEXITY AND THE STRUCTUREOF FEASmLE COMPUTATIONS
Hartmanis, J. (1983)
Should Computability Be Epistemic? a Logical and Physical Point of View
Franchette, F. (2015) · Philosophies · doi:10.3390/philosophies1010015
Vergleich von Speicherstrukturen
Reischuk, K. R. (1999) · Leitfäden der Informatik · doi:10.1007/978-3-322-80139-5_4
An Introduction to Learning and Generalisation
Giorgio Parisi, A. (1994) · Springer eBooks · doi:10.1007/978-94-011-1068-6_6
A Formal System: Rigorous Constructions of Computer ModelsPreprint
Pantelis, G. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.04469
Hromkovic̆, J. (2015) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-a-010520978
Descriptional Complexity for Classes of Ianov-Schemes
Trum, P., & Wotschke, D. (1985) · North-Holland mathematics studies · doi:10.1016/s0304-0208(08)73080-9
Classifying distributions via symbolic entropy estimation
Speidel, U. (2015) · International Conference on Information, Communications & Signal Processing (ICICS) · doi:10.1109/icics.2015.7459844
Paul, G., & Maitra, S. (2011) · CRC Press eBooks · doi:10.1201/b11310-15
A Few Notes on Multiple Theories and Conceptual Jump Size
Solomonoff, G. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-41649-6_24
Natural computation: evolving solutions to complex problems
Green, D. G. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511980381.019
USlNG A!-GO RITHMSAS KFYS IN STREAM CIPHERS
Wagner, N. R., Putter, P. S., & Cain, M. R. (1986)
Inferring gene-gene interactions from microarray data series using unbiased pattern detection
Ahnert, S. E., & Fink, T. (2006)
Traducción del alemán al español del artículo "Endliche Automaten und Zufallsfolgen"
Schnorr, C. P., Stimm, H., & Bristot, L. (2012)
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
