Cited by 913Computability, Logic, AI Algorithmssemigroups and automata theoryAlgorithms and Data Compression

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 access

Chaitin, Gregory J.·1966·Journal of the ACM

Open this paper in CoChat — free account Open PDF

Abstract

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.

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

Crossref · 10.1145/321356.321363

Cites

2 of 2 references verified0 citation errors · 0 not checkable

Statistics

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?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

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

Show all 2 references

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

Sorted by citations

Items 601–700 of 907

A Quantitative Reconstruction of Boden's Creativity Theory
Thornton, C. (2007) · Cited by 3
Algorithmic Complexity and Spatial Simplicity
Kulkarni, R., Stough, R. R., & Haynes, K. E. (2009) · Advances in spatial science · doi:10.1007/978-3-642-01554-0_5 · Cited by 3
A comparison of Shannon, Kullback–Leibler and renormalized entropies within successive bifurcations
Afsar, O. (2018) · Physica D Nonlinear Phenomena · doi:10.1016/j.physd.2018.11.002 · Cited by 3
Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness
Ferbus-Zanda, M., & Grigorieff, S. (2014) · Logic, epistemology, and the unity of science · doi:10.1007/978-94-017-9217-2_3 · Cited by 3
Grammar-based compression and its use in symbolic music analysis
Mondol, T., & Brown, D. G. (2021) · Journal of Mathematics and Music · doi:10.1080/17459737.2021.2002956 · Cited by 3
SOME REFLECTIONS ON CYBERNETICS AND ITS SCIENTIFIC HERITAGE
Aldo, D. L. (2006) · Scientiae mathematicae Japonicae · Cited by 3
Notes on Counting with Finite Machines
Chistikov, D. V. (2014) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.fsttcs.2014.339 · Cited by 3
Compression mechanisms in working memory
Lemaire, B., Robinet, V., & Portrat, S. (2012) · Mathématiques et sciences humaines · doi:10.4000/msh.12301 · Cited by 4
Kolmogorov complexity and derandomization
Ronneburger, D., & Allender, E. (2004) · Cited by 3
Tell Them from Me: An Encrypted Application Profiler
Mamun, M., Lu, R., & Gaudet, M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-36938-5_28 · Cited by 3
Statistical Complexity Analysis of Turing Machine tapes with Fixed Algorithmic Complexity Using the Best-Order Markov Model
Silva, J. M., Pinho, E., Matos, S., & Pratas, D. (2020) · Entropy · doi:10.3390/e22010105 · Cited by 3
Complex Systems
Marinescu, D. C. (2016) · Elsevier eBooks · doi:10.1016/b978-0-12-804041-6.00001-3 · Cited by 3
Complexity Versus Complex Systems: A New Approach to Scientific Discovery
Arecchi, F. T. (2001) · Nonlinear Dynamics Psychology and Life Sciences · doi:10.1023/a:1009567228470 · Cited by 3
Assessing Cognitive Randomness: A Kolmogorov Complexity ApproachPreprint
Gauvrit, N., Zenil, H., & Delahaye, J.-P. (2011) · arXiv (Cornell University) · Cited by 3
Completeness and weak completeness under polynomial-size circuits
Juedes, D. W., & Lutz, J. H. (1995) · Lecture notes in computer science · doi:10.1007/3-540-59042-0_59 · Cited by 3
Linking Information, Knowledge and Evolutionary Growth: A Multilevel Interplay between Natural Selection and Informed InterventionPreprint
Hilbert, M. (2013) · SSRN Electronic Journal · doi:10.2139/ssrn.2397751 · Cited by 3
Algorithmic Information Theory and Cellular Automata Dynamics
Cervelle, J., Durand, B., & Formenti, E. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44683-4_22 · Cited by 3
Asymptotical behaviour of some non-uniform measures
Serna, M. (1989) · RAIRO - Theoretical Informatics and Applications · doi:10.1051/ita/1989230302811 · Cited by 3
An Algorithmic Information Theory approach to the emergence of order using simple replication modelsPreprint
Devine, S. D. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0807.0048 · Cited by 3
Effect of the interelectronic repulsion on the information content of position and momentum atomic densities
Angulo, J. C., López‐Rosa, S., & Antolín, J. (2009) · International Journal of Quantum Chemistry · doi:10.1002/qua.22317 · Cited by 3
When is random random?
Yockey, H. (1990) · Nature · doi:10.1038/344823b0 · Cited by 3
Nonuniqueness, Uncertainty, and Complexity in Modeling
Kimura, H. (1999) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4612-0571-5_3 · Cited by 3
An Information-Theoretic Method for the Treatment of Plural Ancestry in Phylogenetics
Munshaw, S., & Kepler, T. B. (2008) · Molecular Biology and Evolution · doi:10.1093/molbev/msn066 · Cited by 3
Identifying randomness given by high descriptive complexity
Fouch�, W. L. (1994) · Acta Applicandae Mathematicae · doi:10.1007/bf00998683 · Cited by 3
Automated equational reasoning in nondeterministic lambda-calculi modulo theories H *
Obermeyer, F. H. (2009) · Cited by 3
Complexity and Governance
Barile, S., Polese, F., Pels, J., & Sarno, D. (2017) · Springer eBooks · doi:10.1007/978-3-319-31816-5_3413-1 · Cited by 3
Trading Rule Search with Autoregressive Inference Agents
Collie, M. J., Dowe, D. L., & Fitzgibbon, L. J. (2022) · doi:10.26180/20365458 · Cited by 3
The Complexity of Scheduling and Coordination on Computational Grids
Marinescu, D. C., Marinescu, G. M., & Ji, Y. (2020) · CRC Press eBooks · doi:10.1201/9781003072492-9 · Cited by 3
The Search for the Universal Concept of Complexity and a General Optimality Condition of Cooperative Agents
Korotkich, V. (2003) · Cooperative systems · doi:10.1007/978-1-4757-3758-5_8 · Cited by 3
Pseudorandomness
Goldreich, O. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45022-x_58 · Cited by 3
Self-Referential Introspection in Large Language Models: The Critical Threshold for Recursive Self-Improvement
Zhang, J., Yuan, B., & Zhang, Q. (2026) · Entropy · doi:10.3390/e28090951 · Cited by 2
Temperature as joules per bit
Bédard, C. A., Berthelette, S., Coiteux-Roy, X., & Wolf, S. (2025) · American Journal of Physics · doi:10.1119/5.0198820 · Cited by 2
Information Theory ＆ Biology: Introductory Comments
Marks, R. J. (2013) · doi:10.1142/9789814508728_others01 · Cited by 2
The information requirements of complex biological and economic systems with algorithmic information theory
Devine, S. D. (2017) · International Journal of Design & Nature and Ecodynamics · doi:10.2495/dne-v12-n3-367-376 · Cited by 2
Kolmogorov One-Way Functions Revisited
Casal, F., Rasga, J., & Souto, A. (2018) · Cryptography · doi:10.3390/cryptography2020009 · Cited by 2
Quantum Entropies and Decoherence for the Multiparticle Quantum Arnol’d Cat
Mantica, G. (2023) · Entropy · doi:10.3390/e25071004 · Cited by 2
Rebuilding the Habitable Zone from the Bottom up with Computational Zones
Scharf, C. A., & Witkowski, O. (2024) · Astrobiology · doi:10.1089/ast.2023.0035 · Cited by 3
Progressive evolution of plants: A critical review
Melkikh, A. V. (2025) · Biosystems · doi:10.1016/j.biosystems.2025.105444 · Cited by 2
Probability and randomness
Pratt, D. (2003) · Routledge eBooks · doi:10.4324/9780203165874-15 · Cited by 2
Quantum information distance
Dai, S. (2021) · International Journal of Quantum Information · doi:10.1142/s0219749921500313 · Cited by 2
Can Information Concepts Have Physical Content?
Anta, J. (2022) · Perspectives on Science · doi:10.1162/posc_a_00424 · Cited by 2
Structural Complexity as a Directional Signature of System Evolution: Beyond Entropy
Shi, D. (2025) · Entropy · doi:10.3390/e27090925 · Cited by 2
Black hole merger as an event converting two qubits into one
Łukaszyk, S. (2025) · Frontiers in Quantum Science and Technology · doi:10.3389/frqst.2025.1656200 · Cited by 2
Enterprises as Complex Systems
Kandjani, H., Bernus, P., & Wen, L. (2013) · Advances in business information systems and analytics book series · doi:10.4018/978-1-4666-4518-9.ch002 · Cited by 2
Toward a Theory of Knowledge Economics: An Information Systems Approach
Hilbert, M. (2015) · Hawaii International Conference on System Sciences (HICSS) · doi:10.1109/hicss.2015.461 · Cited by 2
Towards an Axiomatic System for Kolmogorov Complexity
Taveneaux, A. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-21875-0_30 · Cited by 2
Entropy analysis in foreign exchange markets and economic crisis
Ha, J.-G., Yim, K., Kim, S., & Jung, W. (2012) · Journal of the Korean Physical Society · doi:10.3938/jkps.61.638 · Cited by 2
Comment on the Shiner–Davison–Landsberg Measure
Stoop, R., Kern, A., Steeb, W. ‐., & Stoop, N. (2006) · Nonlinear Dynamics · doi:10.1007/s11071-006-1971-z · Cited by 2
Information dissipation in quantum-chaotic systems: Computational view and measurement induction
Igeta, K., & Ogawa, T. (1995) · Chaos Solitons & Fractals · doi:10.1016/0960-0779(94)e0070-6 · Cited by 2
The structural complexity of DNA templates—Implications on cellular complexity
Yagil, G. (2009) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2009.04.002 · Cited by 2
Observations on the generation of permutations from random sequences
Kimble, G. W. (1989) · International Journal of Computer Mathematics · doi:10.1080/00207168908803745 · Cited by 2
Molecular evolutionary phylogenetic trees based on minimum description length principle
Ren, F., Tanaka, H., Fukuda, N., & Gojobori, T. (2002) · Hawaii International Conference on System Sciences (HICSS) · doi:10.1109/hicss.1995.375340 · Cited by 2
Sub-computable Bounded Pseudorandomness
Cenzer, D., & Remmel, J. B. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-35722-0_8 · Cited by 2
Normalized Unconditional ϵ-Security of Private-Key Encryption
Bi, L., Dai, S., & Hu, B. (2017) · Entropy · doi:10.3390/e19030100 · Cited by 2
Measuring Algorithmic Complexity in Chaotic Lasers
Kovalsky, M. G., Agüero, M., Bonazzola, C., & Hnilo, A. A. (2020) · International Journal of Bifurcation and Chaos · doi:10.1142/s0218127420500571 · Cited by 2
Approximations to Algorithmic Probability
Zenil, H. (2018) · Springer eBooks · doi:10.1007/978-1-4939-6883-1_700 · Cited by 2
Laws of Nature and Theory Choice
Torza, A. (2022) · Synthese · doi:10.1007/s11229-022-03950-1 · Cited by 2
A New Compressor for Measuring Distances among Images
Pinho, A. J., Pratas, D., & Ferreira, P. J. S. G. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11758-4_4 · Cited by 2
The Lempel-Ziv Complexity of Fixed Points of Morphisms
Constantinescu, S., & Ilie, L. (2006) · Lecture notes in computer science · doi:10.1007/11821069_25 · Cited by 2
Alan Turing y los orígenes de la complejidad
Martin-Delgado, M. A. (2013) · Arbor · doi:10.3989/arbor.2013.764n6006 · Cited by 2
Is movement an illusion? Zeno's paradox: From a modern viewpoint
Meyerstein, F. W. (1999) · Complexity · doi:10.1002/(sici)1099-0526(199903/04)4:4 · Cited by 2
Methodological Issues in the Study of Complex Systems
Harald Atmanspacher, A., & Demmel, G. (2016) · John Wiley & Sons, Inc. eBooks · doi:10.1002/9781118865064.ch10 · Cited by 2
How are Concepts of Infinity Acquired?
Trzęsicki, K. (2015) · Studies in Logic Grammar and Rhetoric · doi:10.1515/slgr-2015-0010 · Cited by 2
Algorithmic Probability Method Versus Kolmogorov Complexity with No-Threshold Encoding Scheme for Short Time Series: An Analysis of Day-To-Day Hourly Solar Radiation Time Series over Tropical Western Indian Ocean
Bessafi, M., Mihailović, D. T., Peng, L., Mihailović, A., & Chabriat, J.-P. (2019) · Entropy · doi:10.3390/e21060552 · Cited by 2
Fuzzy Kolmogorov Complexity Based on a Classical Description
Dai, S. (2020) · Entropy · doi:10.3390/e22010066 · Cited by 2
Information and Complexity, Or: Where Is the Information?
Ay, N., Bertschinger, N., Jost, J., Olbrich, E., & Rauh, J. (2022) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-030-95703-2_4 · Cited by 3
Approaches to Defining and Measuring Assembly Supply Chain Complexity
Modrák, V., & Márton, D. (2013) · Nonlinear systems and complexity · doi:10.1007/978-3-319-01411-1_11 · Cited by 2
Measuring Privacy Loss in Statistical Databases
Chirayath, V., Longpré, L., & Крейнович, В. (2006) · scholarworks - UTEP (The University of Texas at El Paso) · Cited by 2
The Interface Between Chemistry and Biology — Laws Determining Regularities in Early Evolution
Schuster, P. M. (1986) · Proceedings in life sciences · doi:10.1007/978-3-642-70905-0_10 · Cited by 2
HLA and HIV Infection Progression: Application of the Minimum Description Length Principle to Statistical Genetics
Hraber, P. T., Korber, B. T., Wolinsky, S., Erlich, H. A., Trachtenberg, E., & Kepler, T. B. (2006) · Lecture notes in computer science · doi:10.1007/11946465_1 · Cited by 2
On the Complexity and Behaviour of Cryptocurrencies Compared to Other MarketsPreprint
Wilson-Nunn, D., & Zenil, H. (2014) · RePEc: Research Papers in Economics · doi:10.48550/arxiv.1411.1924 · Cited by 2
Medidas de información de funciones especiales y sistemas mecano-cuánticos, y dinámica molecular en presencia de campos eléctricos homogéneos y dependientes del tiempo
Moreno, P. S. (2011) · Institutional Repository of the University of Granada (University of Granada) · Cited by 2
Incorporating complex systems dynamics in sustainability assessment frameworks: enhanced prediction and management of socio-ecological systems performance
Limnios, E. M. (2008) · Cited by 2
Approaching the screenplay as a complex system: underlying mechanics, interrelating dynamics and the plot-algorithmic process
Varotsis, G. (2013) · University of Birmingham Institutional Research Archive (University of Birmingham) · Cited by 2
On quantum computation theory
van Dam, W. K. (2002) · Cited by 2
Nonuniform complexity and the randomness of certain complete languages
Huynh, D. T. (1992) · Theoretical Computer Science · doi:10.1016/0304-3975(92)90340-l · Cited by 2
Quantitative and qualitative information in computations
Daley, R. (1980) · Information and Control · doi:10.1016/s0019-9958(80)90615-4 · Cited by 2
Kolmogorov-Chaitin complexity of linear digital controllers implemented using fixed-point arithmetic
Whidborne, J. F., Mckernan, J., & Gu, D. (2005) · International Conference on Control, Automation, Robotics and Vision (ICARCV) · doi:10.1109/icarcv.2004.1469296 · Cited by 2
A model for comparing genomic restriction maps
Platt, D., & Dix, T. I. (2002) · Hawaii International Conference on System Sciences (HICSS) · doi:10.1109/hicss.1995.375354 · Cited by 2
Inferring Phylogenetic Graphs for Natural Languages using MML
Ooi, J. N., & Dowe, D. L. (2022) · doi:10.26180/20365470 · Cited by 2
The Assessment of Rival Models of the Same Finite Set of Observations
Maciejowski, J. M. (1977) · IFAC Proceedings Volumes · doi:10.1016/s1474-6670(17)66838-1 · Cited by 2
Investigating Estimated Kolmogorov Complexity as a Means of Regularization for Link PredictionPreprint
Flood, P. D. L., Viñas, R., & Lió, P. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.04258 · Cited by 2
Preliminaries
Li, M., & Vitanyi, P. M. B. (1997) · Springer eBooks · doi:10.1007/978-1-4757-2606-0_1 · Cited by 2
�ber die Definition von effektiven Zufallstests
Schnorr, C. P. (1970) · Probability Theory and Related Fields · doi:10.1007/bf00533302 · Cited by 2
Kolmogorov Complexity
Korotkich, V. (2008) · Springer eBooks · doi:10.1007/978-0-387-74759-0_315 · Cited by 2
The Foundations of Solomonoff Prediction
Sterkenburg, T. F. (2013) · Utrecht University Repository (Utrecht University) · Cited by 2
Exploratory Analyses of the U.S. Housing Bubble with Kolmogorov Entropy and Principal Component Analysis (PCA)Preprint
Haynes, K. E., Kulkarni, R., Stough, R. R., & Schintler, L. A. (2010) · SSRN Electronic Journal · doi:10.2139/ssrn.1590309 · Cited by 2
Complexity and Persistence of Electrical Brain Activity Estimated by Higuchi Fractal Dimension
Croce, P., & Zappasodi, F. (2026) · Fractal and Fractional · doi:10.3390/fractalfract10020088 · Cited by 1
Development of the algorithmic information theory in Russia
Uspensky, V., & V'yugin, V. V. (2011) · Journal of Communications Technology and Electronics · doi:10.1134/s1064226911060210 · Cited by 1
A Computational Learning Approach for the Development of Karate Sequences
Newth, D., & McDonald, S. (2021) · Advances in Physical Education · doi:10.4236/ape.2021.114041 · Cited by 1
Simplicity and complexity of probabilistically defined concepts.
Feldman, J. (2025) · Psychological Review · doi:10.1037/rev0000563 · Cited by 1
Biological Complexity and Cognitive Evolution
Jedlička, P., Varchola, J., & Betinsky, J. (2026) · Biological Theory · doi:10.1007/s13752-026-00532-z · Cited by 1
A Behavioral Analysis of Cellular Automata
Baetens, J. M., & Bernard De Baets, C. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-21909-7_13 · Cited by 1
A Survey of Some Quantitative Approaches to the Notion of Information
de Luca, A. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45711-9_6 · Cited by 1
Computational depth and reducibility
Juedes, D. W., Lathrop, J. I., & Lutz, J. H. (1993) · Lecture notes in computer science · doi:10.1007/3-540-56939-1_79 · Cited by 1
Complexity Profiles of DNA Sequences Using Finite-Context Models
Pinho, A. J., Pratas, D., & Garcia, S. P. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-25364-5_8 · Cited by 1
The complexity of the real line is a fractal
Cai, J., & Hartmanis, J. (2003) · Structure in Complexity Theory Annual Conference · doi:10.1109/sct.1989.41820 · Cited by 1
Draft: Deep Learning in Neural Networks: An Overview
Idsia, L. (2014) · Cited by 1
Modern Cryptography, Probabilistic Proofs and Pseudorandomness (Second Edition - author's copy)
Goldreich, O. (2000) · Cited by 1
Information as a Basic Constituent of Human Existence.
Niehaus, E. (2002) · Didáctica Lengua y Literatura · Cited by 1

Authors: Chaitin, G. J.
Affiliations: City College of New York (US)
Corresponding author: Chaitin, Gregory J.
Venue: Journal of the ACM
Publisher: Association for Computing Machinery (ACM)
Published: 1966-10
Volume: 13
Issue: 4
Pages: 547-569
ISSN: 0004-5411 (ISSN-L)
1557-735X
DOI: 10.1145/321356.321363
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
Licence: www.acm.org/publications/policies/copyright_policy#Background (vor)
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

On the Length of Programs for Computing Finite Binary Sequences

Abstract

Overview

Integrity signals

Verification

Claims the paper makes

Claims other papers make about this one

Self-check

Citations

Cites

Cited by

Related

Metadata

Record

About these checks