The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Algorithmic Information Theory
Abstract
This paper reviews algorithmic information theory, which is an attempt to apply information-theoretic and probabilistic ideas to recursive function theory. Typical concerns in this approach are, for example, the number of bits of information required to specify an algorithm, or the probability that a program whose bits are chosen by coin flipping produces a given output. During the past few years the definitions of algorithmic information theory have been reformulated. The basic features of the new formalism are presented here and certain results of R. M. Solovay are reported.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,337
Theory of Self-Reproducing Automata
Schwartz, J. T., von Neumann, J., & Burks, A. W. (1967) · Mathematics of Computation · doi:10.2307/2005041 · Cited by 5,422
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679
Three approaches to the quantitative definition of information*
Kolmogorov, A. N. (1968) · International Journal of Computer Mathematics · doi:10.1080/00207166808803030 · Cited by 2,031
A formal theory of inductive inference. Part II
Solomonoff, R. J. (1964) · Information and Control · doi:10.1016/s0019-9958(64)90131-7 · Cited by 1,758
The definition of random sequences
Martin-Löf, P. (1966) · Information and Control · doi:10.1016/s0019-9958(66)80018-9 · Cited by 1,220
On the Length of Programs for Computing Finite Binary Sequences: statistical considerations
Chaitin, G. J. (1969) · Journal of the ACM · doi:10.1145/321495.321506 · Cited by 918
Self-citationA Model of Set-Theory in Which Every Set of Reals is Lebesgue Measurable
Solovay, R. M. (1970) · The Annals of Mathematics · doi:10.2307/1970696 · Cited by 865
A Theory of Program Size Formally Identical to Information Theory
Chaitin, G. J. (1975) · Journal of the ACM · doi:10.1145/321892.321894 · Cited by 849
Self-citationZvonkin, A. K., & Levin, L. A. (1970) · Russian Mathematical Surveys · doi:10.1070/rm1970v025n06abeh001269 · Cited by 665
Randomness and Mathematical Proof
Chaitin, G. J. (1975) · Scientific American · doi:10.1038/scientificamerican0575-47 · Cited by 656
Self-citationA Fast Monte-Carlo Test for Primality
Solovay, R., & Strassen, V. (1977) · SIAM Journal on Computing · doi:10.1137/0206006 · Cited by 635
Logical basis for information theory and probability theory
Kolmogorov, A. (1968) · IEEE Transactions on Information Theory · doi:10.1109/tit.1968.1054210 · Cited by 592
Complexity-based induction systems: Comparisons and convergence theorems
Solomonoff, R. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055913 · Cited by 388
Theories of Probability: An Examination of Foundations
Fine, T. L. (1973) · International Linear Collider · Cited by 328
Process complexity and effective random tests
Schnorr, C. P. (1973) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(73)80030-3 · Cited by 257
Information-Theoretic Limitations of Formal Systems
Chaitin, G. J. (1974) · Journal of the ACM · doi:10.1145/321832.321839 · Cited by 216
Self-citationINFORMATION-THEORETIC COMPUTATIONAL COMPLEXITY
Chaitin, G. J. (1987) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789814434058_0003 · Cited by 119
Self-citationOn the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
Chaitin, G. J. (1969) · Journal of the ACM · doi:10.1145/321526.321530 · Cited by 99
Self-citationTo a mathematical definition of 'life'
Chaltin, G. J. (1970) · ACM SIGACT News · doi:10.1145/1247047.1247052 · Cited by 88
Information-theoretic characterizations of recursive infinite strings
Chaitin, G. J. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90005-0 · Cited by 87
Self-citationOn the difficulty of computations
Chaitin, G. J. (1970) · IEEE Transactions on Information Theory · doi:10.1109/tit.1970.1054390 · Cited by 53
Self-citationComputational Complexity and Probability Constructions
Willis, D. G. (1970) · Journal of the ACM · doi:10.1145/321574.321578 · Cited by 49
Minimal-program complexity of pseudo-recursive and pseudo-random sequences
Daley, R. (1975) · Theory of Computing Systems · doi:10.1007/bf01698128 · Cited by 21
Noncomplex sequences: characterizations and examples
Daley, R. (1976) · Journal of Symbolic Logic · doi:10.1017/s0022481200051197 · Cited by 11
Cited by
The thermodynamics of computation—a review
Bennett, C. H. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02084158 · Cited by 2,006
Universality and complexity in cellular automata
Wolfram, S. (1984) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(84)90245-8 · Cited by 1,914
Fractals and the analysis of waveforms
Katz, M. J. (1988) · Computers in Biology and Medicine · doi:10.1016/0010-4825(88)90041-8 · Cited by 826
Computation theory of cellular automata
Wolfram, S. (1984) · Communications in Mathematical Physics · doi:10.1007/bf01217347 · Cited by 625
A First Course in Information Theory
Yeung, R. W. (2002) · Information Technology: Transmission, Processing and Storage · doi:10.1007/978-1-4419-8608-5 · Cited by 533
Metadata
- Authors
- Chaitin, G. J.
- Venue
- IBM Journal of Research and Development
- Publisher
- IBM
- Published
- 1977-07
- Volume
- 21
- Issue
- 4
- Pages
- 350-359
- ISSN
- 0018-8646 (ISSN-L)
- OpenAlex
- W2567782165
- Cited by
- 982
- References
- 25
- FWCI
- 2.94
- Type
- journal article
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.