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 801–900 of 907

Information, Communication, and Manipulability
Lombardi, O., & López, C. (2017) · Cambridge University Press eBooks · doi:10.1017/9781316494233.005
Fields of Application of Information Geometry
Ay, N., Jost, J., Lê, H. V., & Schwachhöfer, L. (2017) · Ergebnisse der Mathematik und ihrer Grenzgebiete · doi:10.1007/978-3-319-56478-4_6
A Proof of Syntactic Incompleteness of the Second-Order Categorical Arithmetic
Raguní, G. (2017) · OALib · doi:10.4236/oalib.1103969
How Could Life Have Originated?
Küppers, B. (2017) · The frontiers collection · doi:10.1007/978-3-319-67369-1_3
Theoretical note Acatalog of Boolean concepts
Feldman, J. (2003)
Pixon-Based Multiresolution Image Reconstruction and Quantification of Image Information Content
Puetter, R. C. (1996) · Springer eBooks · doi:10.1007/978-94-011-5430-7_17
Quantum Random Self-Modifiable ComputationPreprint
Fiske, M. S. (2018) · arXiv (Cornell University) · doi:10.13140/rg.2.2.32087.16801
Approximations to Algorithmic Probability
Zenil, H. (2017) · Springer eBooks · doi:10.1007/978-3-642-27737-5_700-1
An Application of Data Compression Models to Handwritten Digit Classification
Pinho, A. J., & Pratas, D. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-01449-0_41
Programs as the Language of SciencePreprint
Pantelis, G. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.05116
On complexiy
Schächter, V. (2002)
Reusable Garbled Turing Machines Without FHE
Wang, Y., & Malluhi, Q. M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-16458-4_22
A dissertation submitted in partial satisfaction of the requirements for the degree Doctor of Philosophy in Cognitive Science and Computer Science
Schraudolph, N. N. (1995)
Topological stability and dynamic resilience in complex networks
Banerjee, S. (2012) · Libraries and Cultural Resources (University of Calgary) · doi:10.11575/prism/5021
Kolmogorov Complexity in Perspective Part II: Classification, Information Processing and Duality
Ferbus-Zanda, M. (2014) · Logic, epistemology, and the unity of science · doi:10.1007/978-94-017-9217-2_4
Complexity in abstract and physical systems
Sieniutycz, S. (2021) · Elsevier eBooks · doi:10.1016/b978-0-12-823460-0.00003-3
Sensing 'Socio-Spatio-Temporal' Activity Patterns from Location Sharing Services DataPreprint
Schintler, L. A., Kulkarni, R., Haynes, K. E., & Stough, R. R. (2012) · SSRN Electronic Journal · doi:10.2139/ssrn.1978959
Logical and Philosophical Foundations of Complexity
Rosser, J. B. (2021) · Springer eBooks · doi:10.1007/978-3-030-70668-5_1
Popular Movies and Technology
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0002
Mise-en-Cadre
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0004
The Power of Movies and a Method to Study It
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0001
Viewing and Lenses
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0003
Continuity, Discontinuity, and Scenes
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0009
Structure, Engagement, and Evolution
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0014
Shots and Sound
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0007
Stories and Their Parts
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0011
An Interlude on Shots and Cultural Change
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0006
The Most Important Shot in Popular Cinema
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0008
Montages, Sequences, and Syntagmas
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0010
Stock Returns, Market Trends, and Information Theory: A Statistical Equilibrium ApproachPreprint
Citera, E. (2021) · SSRN Electronic Journal · doi:10.2139/ssrn.3936846
Applications of kolmogorov complexity to cryptography
Pinto, A. (2007) · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) · doi:10.34626/05dc-c039
Transitions
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0005
Program-size
Calude, C. S. (2002) · Texts in theoretical computer science · doi:10.1007/978-3-662-04978-5_3
A List of Problems
(2011) · CRC Press eBooks · doi:10.1201/b11610-8
Fuzzy Kolmogorov Complexity Based on Fuzzy Decompression Algorithms and Its Application to Fuzzy Data Mining
Yamakami, T. (2022) · Lecture notes in computer science · doi:10.1007/978-3-030-95405-5_30
BACK MATTER
(1993) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789814503563_bmatter
Bibliography
Leleu-Merviel, S. (2018) · Wiley eBooks · doi:10.1002/9781119452867.biblio
Narrational Complexity
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.003.0012
The Relationship between Population Size, Technology Complexity, Economic Growth and Kolmogorov ComplexityPreprint
Myakshin, V. (2022) · Research Square · doi:10.21203/rs.3.rs-6844928/v1
Random Sequences
Calude, C. S. (2002) · Texts in theoretical computer science · doi:10.1007/978-3-662-04978-5_6
Generación de sucesiones criptográficamente fuertes
Santiago, S. D. (2005) · doi:10.24275/uami.3n203z173
References
Saccone, C., & Pesole, G. (2003) · Wiley eBooks · doi:10.1002/0471722723.refs
What is a Random String?
Calude, C. S. (1995) · Springer eBooks · doi:10.1007/978-94-017-3327-4_8
On Complexity
Schächter, V. (2003) · Springer eBooks · doi:10.1007/0-306-48144-8_15
Algorithmen – Berechenbarkeit und Komplexität
Ernst, H., Schmidt, J., & Beneken, G. (2016) · Springer eBooks · doi:10.1007/978-3-658-14634-4_11
Bibliography
(2016) · Elsevier eBooks · doi:10.1016/b978-0-12-804041-6.09998-9
Random Strings
Calude, C. S. (2002) · Texts in theoretical computer science · doi:10.1007/978-3-662-04978-5_5
Bibliography
(1992) · Studies in logic and the foundations of mathematics · doi:10.1016/s0049-237x(08)70025-9
Encoding Arguments
Reddad, T. (2016) · doi:10.22215/etd/2016-11288
About the Nature of Quantum Information
Lombardi, O. (2021) · International Society for the Study of Information Summit (IS4SI Summit) · doi:10.3390/proceedings2022081027
Book reviews
Cooke, J., Calude, C., Harwood, W., & Simpson, D. (1989) · Formal Aspects of Computing · doi:10.1007/bf01887210
Complexity and Emergence of Meaning: Toward a Semiophysics
Arecchi, T. F. (2005) · New economic windows · doi:10.1007/978-88-470-0344-6_1
Redes funcionales cerebrales: organización multicapa y deterioro = Functional brain networks: multilayer architecture and Alzheimer’s disease
Blanco, I. E. (2021) · doi:10.20868/upm.thesis.68885
Algorithmen – Berechenbarkeit und Komplexität
Ernst, H., Schmidt, J., & Beneken, G. (2020) · Springer eBooks · doi:10.1007/978-3-658-30331-0_12
Literature
(2013) · Elsevier eBooks · doi:10.1016/b978-0-12-404627-6.00012-9
References
Ripley, B. D. (1987) · Wiley series in probability and statistics · doi:10.1002/9780470316726.refs
Complexity and Stochastic Synchronization in Coupled Map Lattices and Cellular Automata
López‐Ruiz, R., & Juan, R. H. (2010) · Sciyo eBooks · doi:10.5772/46972
Bibliography
(1988) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70415-1
Exploring, Modelling, and Controlling Discrete Sequential Environments
Witten, I. H. (1978) · Springer eBooks · doi:10.1007/978-1-4757-0555-3_12
Back Matter
Blüm, N. (2006) · Oldenbourg Wissenschaftsverlag eBooks · doi:10.1524/9783486593969.bm
REFERENCES
(1991) · Elsevier eBooks · doi:10.1016/b978-0-08-036979-2.50015-x
Preliminaries
Zenil, H., Toscano, F. S., & Gauvrit, N. (2022) · Emergence, complexity and computation · doi:10.1007/978-3-662-64985-5_1
Martingales in the Study of Randomness
Bienvenu, L., Shafer, G. R., & Shen', A. K. (2022) · Trends in the history of science · doi:10.1007/978-3-031-05988-9_11
Complexity and Governance
Barile, S., Polese, F., Pels, J., & Sarno, D. (2022) · Springer eBooks · doi:10.1007/978-3-030-66252-3_3413
The Imaginary UniversePreprint
Łukaszyk, S. (2023) · Preprints.org · doi:10.20944/preprints202212.0045.v14
The Imaginary UniversePreprint
Łukaszyk, S. (2023) · Preprints.org · doi:10.20944/preprints202212.0045.v15
The Imaginary UniversePreprint
Łukaszyk, S. (2023) · Preprints.org · doi:10.20944/preprints202212.0045.v16
The Imaginary UniversePreprint
Łukaszyk, S. (2023) · Preprints.org · doi:10.20944/preprints202212.0045.v17
Algorithmen – Berechenbarkeit und Komplexität
Ernst, H., Schmidt, J., & Beneken, G. (2023) · Springer eBooks · doi:10.1007/978-3-658-41779-6_12
Highly-Sensitive Measure of Complexity Captures Boolean Networks Regimes and Temporal Order More OptimallyPreprint
Luevano, M. D. J., & Puga, A. (2024) · Preprints.org · doi:10.20944/preprints202403.1569.v1
自发辐射放大的量子随机数快速后处理方法
Qixia, 童. T., Yingying, 胡. H., Deyong, 何. H., & Zhengfu, 韩. H. (2024) · Laser & Optoelectronics Progress · doi:10.3788/lop230839
On the Existence of Consensus Converging Organized Groups in Large Social Networks
Liagkou, V., Nastou, P. E., Spirakis, P. G., & Stamatiou, Y. C. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-60603-8_30
Dedication
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.002.0004
Epigraph
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.002.0005
Copyright Page
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.002.0003
Preface and Acknowledgments
Cutting, J. E. (2021) · Oxford University Press eBooks · doi:10.1093/oso/9780197567777.002.0007
Highly-Sensitive Measure of Complexity Captures Boolean Networks Regimes and Temporal Order More OptimallyPreprint
Luevano, M. D. J., & Puga, A. (2024) · Preprints.org · doi:10.20944/preprints202403.1569.v2
Lower Bounds for Levin–Kolmogorov Complexity
Brandt, N. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-78011-0_7
Unsupervised Learning and Effective Complexity: Introducing JPG and Neural Sophistication
Soto, E. G., Emonet, R., & Sebban, M. (2024) · IEEE International Conference on Tools with Artificial Intelligence (ICTAI) · doi:10.1109/ictai62512.2024.00040
Model Selection from Multiple Model Families in Species Distribution Modeling Using Minimum Message Length
Wen, Z., & Dowe, D. L. (2024) · Entropy · doi:10.3390/e27010006
Introductory Chapter: AI and Statistical Complexity
López‐Ruiz, R. (2025) · IntechOpen eBooks · doi:10.5772/intechopen.1010337
Complexity Measures
Fuentes, M. (2025) · SpringerBriefs in philosophy · doi:10.1007/978-3-031-99994-9_2
Gibbs Randomness-Compression Proposition: An Eﬃcient DeeplearningPreprint
Süzen, M. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5399043
Highly-sensitive measure of complexity captures Boolean networks’ regimes and temporal order more optimally
Luevano, M. D. J., & Puga, A. (2025) · Physica D Nonlinear Phenomena · doi:10.1016/j.physd.2025.134844
Feasibility of Quantum Key Distribution Between Supersonic Aircraft
McKiernan, S., & Collins, R. J. (2025) · IET Quantum Communication · doi:10.1049/qtc2.70018
Artificial Intelligence on the Great Chain of Being
Maliţa, M., & Gheorghe, Ș. (2025) · International Conference on Information Visualisation (IV) · doi:10.1109/iv68685.2025.00043
Kolmogorov Complexity Based Analysis of the Zeros Distribution in Locally Maximal Satisfying Truth Assignments of Random K-SAT Formulas
Liagkou, V., Nastou, P. E., Spirakis, P. G., & Stamatiou, Y. C. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-10759-6_18
The Imaginary UniversePreprint
Łukaszyk, S. (2025) · Preprints.org · doi:10.20944/preprints202212.0045.v21
From Social Engineering to Synergetics
Andersson, Å. E. (1993) · Springer series in synergetics · doi:10.1007/978-3-642-51030-4_9
Dynamical systems of interacting units: Information transport and higher order structures
Helvik, T. (2006) · BIBSYS Brage (BIBSYS (Norway))
Radioactive Information: How Uncomputability Ensures O(1) Precision for Non-Shannon InequalitiesPreprint
Topal, T. (2025) · Preprints.org · doi:10.20944/preprints202512.2361.v1
No Universal Hyperbola: A Formal Disproof of the Epistemic Trade-Off Between Certainty and Scope in Symbolic and Generative AIPreprint
Immediato, G. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.6074588
Probability, Compressibility and AI: A Novel Response to Intelligent Design
Grygiel, W. P. (2026) · Religions · doi:10.3390/rel17030364
L'hyper-calcul : de la logique a la physique
Franchette, F. (2013) · theses.fr (ABES) · doi:10.70675/0b3f6ab0zc577z499azb8e6z4a0425f88e23
Multi-scale and multi-dimensional modelling of music structure using polytopic graphs
Louboutin, C. (2019) · theses.fr (ABES) · doi:10.70675/b64c01b4z669az45c7z8ed9zf148dd0ea7d1
De la précarité épistémique des systèmes complexes en transition critique étendue : vers une épistémologie ouverte des processus de marché
Biasoni, S. (2021) · theses.fr (ABES) · doi:10.70675/3773dea8zb296z418dzb091zcbbfd6a9f8ed
Mind the Gap : A Historico-Philosophical Investigation of the Ontological Status of Computer Programs
Wiggershaus, N. (2025) · theses.fr (ABES) · doi:10.70675/0e2d4688z89bfz49a1z8229zd113f9d427e2
Boundary Permeability in Finite Information SystemsPreprint
Varney, E. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.6774898
Algorithmic Racialism as Structural Metamechanism: Replicating Racial Inequality in the Black Working Class
Adams, B., & Poonamallee, L. (2026) · Springer eBooks · doi:10.1007/978-3-032-20821-7_3
Kolmogorov complexity and Shannon entropy based data analytics for laser fault injection
Babilotte, P., Papin, P., Fontanel, M., Morvan, F., Lohya, N., Guen, H. L., Brizoual, L. L., & Pichon, L. (2026) · Physica Scripta · doi:10.1088/1402-4896/ae7c3a

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