On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
Open accessAbstract
It is suggested that there are infinite computable sets of natural numbers with the property that no infinite subset can be computed more simply or more quickly than the whole set. Attempts to establish this without restricting in any way the computer involved in the calculations are not entirely successful. A hypothesis concerning the computer makes it possible to exhibit sets without simpler subsets. A second and analogous hypothesis then makes it possible to prove that these sets are also without subsets which can be computed more rapidly than the whole set. It is then demonstrated that there are computers which satisfy both hypotheses. The general theory is momentarily set aside and a particular Turing machine is studied. Lastly, it is shown that the second hypothesis is more restrictive then requiring the computer to be capable of calculating all infinite computable sets of natural numbers.
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
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?
Kolmogorov complexity is in general uncomputable and therefore of limited practical interest.
“Kolmogorov complexity is in general uncomputable, and, therefore, of limited practical interest.”
From Meta-learned models of cognition (2024) · cites this paper as Chaitin, 1969
The Remark discusses a program-complexity measure, and Section 3 discusses computational complexity in number theory. Neither passage says that Kolmogorov complexity is generally uncomputable or concludes that it is therefore of limited practical interest. Searches for uncomputability and practical usefulness found no passage addressing that claim. (LLM, conf=0.70)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
B., T. A. A. (1946) · The Mathematical Gazette · doi:10.2307/3609182 · Cited by 7,192 · see citing works
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 · see citing works
A formal theory of inductive inference. Part I
Solomonoff, R. J. (1964) · Information and Control · doi:10.1016/s0019-9958(64)90223-2 · Cited by 1,192 · see citing works
Computability and Unsolvability.
Elgot, C. C., & Davis, M. D. (1959) · Mathematical Tables and Other Aids to Computation · doi:10.2307/2002808 · Cited by 1,011 · see citing works
On the Computational Complexity of Algorithms
Hartmanis, J., & Stearns, R. E. (1965) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1965-0170805-7 · Cited by 1,008 · see citing works
On the Length of Programs for Computing Finite Binary Sequences
Chaitin, G. J. (1969) · Journal of the ACM · doi:10.1145/321495.321506 · Cited by 935 · see citing works
Self-citationOn the Length of Programs for Computing Finite Binary Sequences
Chaitin, G. J. (1966) · Journal of the ACM · doi:10.1145/321356.321363 · Cited by 913 · see citing works
Self-citationA Machine-Independent Theory of the Complexity of Recursive Functions
Blum, M. (1967) · Journal of the ACM · doi:10.1145/321386.321395 · Cited by 835 · see citing works
Number; the Language of Science.
Dantzig, T. (1930) · The Economic Journal · doi:10.2307/2224269 · Cited by 355 · see citing works
Fraenkel, A. A. (1953) · Cited by 140 · see citing works
Blum, M. (1967) · Information and Control · doi:10.1016/s0019-9958(67)90546-3 · Cited by 138 · see citing works
Leçons sur la théorie des fonctions
Borel, É. (1898) · Monatshefte für Mathematik · doi:10.1007/bf01707942 · Cited by 116 · see citing works
Dekker, J. C. E., & Myhill, J. R. (1958) · Canadian Journal of Mathematics · doi:10.4153/cjm-1958-035-x · Cited by 74 · see citing works
On the difficulty of computations
Chaitin, G. J. (1970) · IEEE Transactions on Information Theory · doi:10.1109/tit.1970.1054390 · Cited by 53 · see citing works
Self-citationElementary Methods in Analytic Number Theory.
Carlitz, L., Gelfond, A. O., Linnik, Y. V., & Mordell, L. J. (1967) · American Mathematical Monthly · doi:10.2307/2314314 · Cited by 43 · see citing works
Degrees of Unsolvability. (AM-55)
Sacks, G. E. (1964) · Princeton University Press eBooks · doi:10.1515/9781400881840 · Cited by 25 · see citing works
Machine Dependence of Degrees of Difficulty
Arbib, M. A., & Blum, M. (1965) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1965-0181538-0 · Cited by 15 · see citing works
Flagged first, then by citations
Research works printed but not linked: 7
- HARDY, G. H., AND WRIGHT, E.M. An Introduction to the Theory of Numbers. Clarendon Press, Oxford, 1962.
- BLV~, M. Measures on the computation speed of partial recursive functions. Quart. Prog. Rep. 72, Res. Lab. Electronics, MIT, Cambridge, Mass., Jan. 1964, pp. 237-253.
- ARBIB, M. A. Speed-up theorems and incompleteness theorems. In Automata Theory, E. R. Cainiello (Ed.), Academic Press, New York, 1966, pp. 6-24.
- HARDY, G. H. Orders of Infinity. Cambridge Math. Tracts, No. 12, U. of Cambridge, Cambridge, Eng., 1924.
- BIRKHOFF, G. Lattice Theory. Amer. Math. Soc. Colloq. Publ. Vol. 25, Amer. Math. Soc., Providence, R. I., 1967.
- CHAITIN, G.J. A lattice of computer speeds. Abstract 67T-397, Notices Amer. Math. Soc. 14 (1967), 538.
- MOSTOWSKI, A. ~ber gewisse universelle Relationen. Ann. Soc. Polon. Math. 17 (1938), 117-118.
Cited by
Sorted by citations
Algorithmic Information Theory
Chaitin, G. J. (1977) · IBM Journal of Research and Development · doi:10.1147/rd.214.0350 · Cited by 982 · see citing works
Self-citationStructural complexity of minerals: information storage and processing in the mineral world
Krivovichev, S. V. (2013) · Mineralogical Magazine · doi:10.1180/minmag.2013.077.3.05 · Cited by 281 · see citing works
The algorithmic origins of lifePreprint
Walker, S. I., & Davies, P. C. W. (2013) · Cited by 209 · see citing works
The algorithmic origins of life
Walker, S. I., & Davies, P. C. W. (2013) · Journal of The Royal Society Interface · doi:10.1098/rsif.2012.0869 · Cited by 196 · see citing works
When is temporal planning really temporal
Cushing, W., Subbarao Kambhampati, B., & Weld, D. S. (2007) · Cited by 144 · see citing works
‘Ideal learning’ of natural language: Positive results about learning from positive evidence
Chater, N., & Vitanyi, P. M. B. (2007) · Journal of Mathematical Psychology · doi:10.1016/j.jmp.2006.10.002 · Cited by 110 · see citing works
On grammars, complexity, and information measures of biological macromolecules
Ebeling, W., & Jiménez-Montaño, M. A. (1980) · Mathematical Biosciences · doi:10.1016/0025-5564(80)90004-8 · Cited by 93 · see citing works
To a mathematical definition of 'life'
Chaltin, G. J. (1970) · ACM SIGACT News · doi:10.1145/1247047.1247052 · Cited by 88 · see citing works
Consciousness & Brain Functional Complexity in Propofol Anaesthesia
Varley, T. F., Luppi, A. I., Pappas, I., Naçi, L., Adapa, R., Owen, A. M., Menon, D. K., & Stamatakis, E. A. (2020) · Scientific Reports · doi:10.1038/s41598-020-57695-3 · Cited by 81 · see citing works
A Novel Hyperparameter-Free Approach to Decision Tree Construction That Avoids Overfitting by Design
Leiva, R. A. G., Anta, A. F., Mancuso, V., & Casari, P. (2019) · IEEE Access · doi:10.1109/access.2019.2930235 · Cited by 75 · see citing works
Orponen, P., Ko, K., Schöning, U., & Watanabe, O. (1994) · Journal of the ACM · doi:10.1145/174644.174648 · Cited by 65 · see citing works
The Complexity of Computations
Pudlák, P. (2013) · Springer monographs in mathematics · doi:10.1007/978-3-319-00119-7_5 · Cited by 57 · see citing works
On the difficulty of computations
Chaitin, G. J. (1970) · IEEE Transactions on Information Theory · doi:10.1109/tit.1970.1054390 · Cited by 53 · see citing works
Self-citationComplex systems approach to natural language
Stanisz, T., Drożdż, S., & Kwapień, J. (2023) · Physics Reports · doi:10.1016/j.physrep.2023.12.002 · Cited by 46 · see citing works
Complexity, disorder, and functionality of nanoscale materials
Mao, X., & Kotov, N. A. (2024) · MRS Bulletin · doi:10.1557/s43577-024-00698-6 · Cited by 41 · see citing works
On One-way Functions and Kolmogorov Complexity
Liu, Y., & Pass, R. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00118 · Cited by 41 · see citing works
Meta-learned models of cognition
Binz, M., Dasgupta, I., Jagadish, A. K., Botvinick, M., Wang, J. X., & Schulz, E. (2024) · Behavioral and Brain Sciences · doi:10.1017/s0140525x23003266 · Cited by 38 · see citing works
Origo: causal inference by compression
Budhathoki, K., & Vreeken, J. (2017) · Knowledge and Information Systems · doi:10.1007/s10115-017-1130-5 · Cited by 42 · see citing works
Distributed leadership in schools
Hill, A. L. (2016) · International Summit on the Teaching Profession · doi:10.1787/9789264252059-graph22-en · Cited by 37 · see citing works
Causal Inference by Compression
Budhathoki, K., & Vreeken, J. (2016) · Proceedings · doi:10.1109/icdm.2016.0015 · Cited by 36 · see citing works
Zipf’s Law, unbounded complexity and open-ended evolution
Corominas‐Murtra, B., Seoane, L. F., & Solé, R. V. (2018) · Journal of The Royal Society Interface · doi:10.1098/rsif.2018.0395 · Cited by 33 · see citing works
An Information-Theoretic Metric of System Complexity With Application to Engineering System Design
Allaire, D., He, Q., Deyst, J. J., & Willcox, K. E. (2012) · Journal of Mechanical Design · doi:10.1115/1.4007587 · Cited by 32 · see citing works
Knowledge production and world population dynamics
Dolgonosov, B. M. (2015) · Technological Forecasting and Social Change · doi:10.1016/j.techfore.2015.10.023 · Cited by 30 · see citing works
Complexity cores and hard problem instances
Schöning, U. (1990) · Lecture notes in computer science · doi:10.1007/3-540-52921-7_72 · Cited by 28 · see citing works
The Critical Roles of Information and Nonequilibrium Thermodynamics in Evolution of Living Systems
Gatenby, R. A., & Frieden, B. R. (2013) · Bulletin of Mathematical Biology · doi:10.1007/s11538-013-9821-x · Cited by 28 · see citing works
Randomness: Quantum versus classical
Khrennikov, A. Y. (2016) · International Journal of Quantum Information · doi:10.1142/s0219749916400098 · Cited by 27 · see citing works
Principle of maximum Fisher information from Hardy's axioms applied to statistical systems
Frieden, B. R., & Gatenby, R. A. (2013) · Physical Review E · doi:10.1103/physreve.88.042144 · Cited by 26 · see citing works
Mapping efficiency and information content
Tomislav Hengl, A., Nikolić, M., & MacMillan, R. A. (2012) · International Journal of Applied Earth Observation and Geoinformation · doi:10.1016/j.jag.2012.02.005 · Cited by 23 · see citing works
Allen, D. E., McAleer, M. J., & Singh, A. K. (2016) · Applied Economics · doi:10.1080/00036846.2016.1203067 · Cited by 23 · see citing works
Algorithmic Complexity of Multiplex Networks
Santoro, A., & Nicosia, V. (2020) · Physical Review X · doi:10.1103/physrevx.10.021069 · Cited by 22 · see citing works
Complex Systems, Emergence, and Multiscale Analysis: A Tutorial and Brief Survey
Gao, J., & Xu, B. (2021) · Applied Sciences · doi:10.3390/app11125736 · Cited by 21 · see citing works
Life in The Context of Order and Complexity
Mayer, C. (2020) · Life · doi:10.3390/life10010005 · Cited by 20 · see citing works
On graph entropy measures based on the number of independent sets and matchings
Wan, P., Chen, X., Tu, J., Dehmer, M., Zhang, S., & Emmert‐Streib, F. (2019) · Information Sciences · doi:10.1016/j.ins.2019.11.020 · Cited by 18 · see citing works
Linguistic approaches to the analysis of sequence information
Pesole, G., Attimonelli, M., & Saccone, C. (1994) · Trends in biotechnology · doi:10.1016/0167-7799(94)90028-0 · Cited by 17 · see citing works
Probabilistic automata as a model for epigenesis of cellular networks
Milgram, M., & Atlan, H. (1983) · Journal of Theoretical Biology · doi:10.1016/0022-5193(83)90281-3 · Cited by 15 · see citing works
The principles of informational genomics
Manca, V. (2017) · Theoretical Computer Science · doi:10.1016/j.tcs.2017.02.035 · Cited by 13 · see citing works
Complexity: the organizing principle at the interface of biological (dis)order
Bhat, R., & Pally, D. (2017) · Journal of Genetics · doi:10.1007/s12041-017-0793-8 · Cited by 12 · see citing works
Algorithmic complexity as a criterion of unsolvability
Burgin, M. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2007.04.011 · Cited by 13 · see citing works
Order and Complexity in the RNA World
Mayer, C. (2023) · Life · doi:10.3390/life13030603 · Cited by 10 · see citing works
Liu, Y., & Pass, R. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-38545-2_21 · Cited by 10 · see citing works
Introduction to Ray Solomonoff 85th Memorial Conference
Dowe, D. L. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-44958-1_1 · Cited by 12 · see citing works
Language-theoretic complexity of disjunctive sequences
Calude, C. S., & Sheng, Y. (1997) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(97)00061-9 · Cited by 10 · see citing works
On the Possibility of Basing Cryptography on $$\mathsf{EXP}\ne \mathsf{BPP}$$
Liu, Y., & Pass, R. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-84242-0_2 · Cited by 14 · see citing works
Toward an abstract theory of data compression
Storer, J. A. (1983) · Theoretical Computer Science · doi:10.1016/0304-3975(83)90001-4 · Cited by 9 · see citing works
The GARD Prebiotic Reproduction Model Described in Order and Complexity
Mayer, C., Lancet, D., & Markovitch, O. (2024) · Life · doi:10.3390/life14030288 · Cited by 9 · see citing works
A Non-Parametric and Entropy Based Analysis of the Relationship between the VIX and S&P 500
Allen, D. E., McAleer, M. J., Powell, R. J., & Singh, A. K. (2012) · Journal of risk and financial management · doi:10.2139/ssrn.2132065 · Cited by 8 · see citing works
Estimating data complexity and drift through a multiscale generalized impurity approach
Costa, D., Rocha, E. M., & Ferreira, N. (2024) · Journal of Computational Mathematics and Data Science · doi:10.1016/j.jcmds.2024.100098 · Cited by 7 · see citing works
Modular quantum signal processing in many variables
Rossi, Z. M., Ceroni, J., & Chuang, I. L. (2025) · Quantum · doi:10.22331/q-2025-06-18-1776 · Cited by 6 · see citing works
Toussaint, E. R., Artist, I., Dhabi, A., Emirates, U. A., & Toussaint, G. T. (2014) · Cited by 6 · see citing works
Temperature Effects, Frieden–Hawkins’ Order-Measure, and Wehrl Entropy
Pennini, F., Plastino, A., & Ferri, G. L. (2012) · Entropy · doi:10.3390/e14112081 · Cited by 6 · see citing works
Textual Substitution Techniques for Data Compression
Storer, J. A. (1985) · Springer eBooks · doi:10.1007/978-3-642-82456-2_8 · Cited by 6 · see citing works
Toussaint, G. T., Onea, N. S., & Vuong, Q. (2015) · Machine Vision Applications · doi:10.1109/mva.2015.7153235 · Cited by 4 · see citing works
Motion-dependent levels of order in a relativistic universe
Frieden, B. R., & Petri, M. (2012) · Physical Review E · doi:10.1103/physreve.86.032102 · Cited by 4 · see citing works
Biological Information — What is It?
Gitt, W., Compton, R., & Fernandez, J. (2013) · doi:10.1142/9789814508728_0001 · Cited by 4 · see citing works
Fractal Analysis of Pi Normality
Sevcik, C. (2017) · Experimental Mathematics · doi:10.1080/10586458.2017.1279092 · Cited by 4 · see citing works
On the algorithmic foundation of information theory
Heim, R. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1056080 · Cited by 4 · see citing works
On One-way Functions and Kolmogorov ComplexityPreprint
Liu, Y., & Pass, R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.11514 · Cited by 4 · see citing works
Quantum Cryptography and Meta-Complexity
Hiroka, T., & Morimae, T. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-01878-6_18 · Cited by 3 · see citing works
Fisher order measure and Petri’s universe
Frieden, B. R., Plastino, A. R., & Plastino, A. R. (2011) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2011.11.061 · Cited by 3 · see citing works
Algorithmic Information Theory for the Precise Engineering of Flexible Material Mechanics
Luo, L., & Stylios, G. K. (2024) · Machine Learning and Knowledge Extraction · doi:10.3390/make6010012 · Cited by 3 · see citing works
Quantum Kolmogorov complexity and bounded quantum memory
Miyadera, T. (2011) · Physical Review A · doi:10.1103/physreva.83.042316 · Cited by 3 · see citing works
Quantum-inspired identification of complex cellular automata
Ho, M., Pradana, A., Elliott, T. J., Chew, L. Y., & Gu, M. (2023) · The European Physical Journal Plus · doi:10.1140/epjp/s13360-023-04160-5 · Cited by 3 · see citing works
Meaning Naturalism, Meaning Irrealism, and the Work of Language
DeLancey, C. (2006) · Synthese · doi:10.1007/s11229-005-1006-1 · Cited by 3 · see citing works
A Bayesian Framework for Uncertainty Quantification in the Design of Complex Systems
He, Q., Allaire, D., Deyst, J. J., & Willcox, K. E. (2012) · AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference (MAO) · doi:10.2514/6.2012-5479 · Cited by 3 · see citing works
Stochastic modeling of hydrometeorological extremes and their possible relation with global change
Rosmann, T. (2020) · doi:10.11144/javeriana.10554.13103 · Cited by 3 · see citing works
A Mathematical Framework for Enriching Human–Machine Interactions
Ehresmann, A., Béjean, M., & Vanbremeersch, J.-P. (2023) · Machine Learning and Knowledge Extraction · doi:10.3390/make5020034 · Cited by 2 · see citing works
Rowland, M., Maccarone, L., & Clark, A. J. (2022) · Nuclear Technology · doi:10.1080/00295450.2022.2087841 · Cited by 2 · see citing works
Li, M. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-44958-1_4 · Cited by 2 · see citing works
A program for the Minimalist Program
Hornstein, N., & Idsardi, W. J. (2014) · Language faculty and beyond · doi:10.1075/lfab.11.01hor · Cited by 2 · see citing works
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 · see citing works
A test for randomness based on a complexity measure
Martínez-Morales, M., & Duran, B. S. (1993) · Communication in Statistics- Theory and Methods · doi:10.1080/03610929308831062 · Cited by 2 · see citing works
Information Driven Self-Organization of Agents and Agent Collectives
Harder, M. (2014) · University of Hertfordshire Research Archive (University of Hertfordshire) · doi:10.18745/th.13907 · Cited by 2 · see citing works
Consciousness & Brain Functional Complexity in Propofol AnaesthesiaPreprint
Varley, T. F., Luppi, A. I., Pappas, I., Naçi, L., Adapa, R., Owen, A. M., Menon, D. K., & Stamatakis, E. A. (2019) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/680447 · Cited by 2 · see citing works
A superstatistical formulation of complexity measuresPreprint
Fuentes, J., & Obregón, O. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.09147 · Cited by 2 · see citing works
Toward Basing Cryptography on the Hardness of EXP
Liu, Y., & Pass, R. (2023) · Communications of the ACM · doi:10.1145/3587167 · Cited by 1 · see citing works
Construction of pan-cancer regulatory networks based on causal inference
Ji, R., Yan, M., Zhao, M., & Geng, Y. (2024) · Biosystems · doi:10.1016/j.biosystems.2024.105279 · Cited by 1 · see citing works
Objects and processes: Two notions for understanding biological information
Reyes, A., Padilla-Longoria, P., & Arroyo‐Santos, A. (2015) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2015.05.021 · Cited by 1 · see citing works
Randomness: Quantum Versus Classical
(2016) · IMPERIAL COLLEGE PRESS eBooks · doi:10.1142/9781783267972_0007 · Cited by 1 · see citing works
The Symbolism as a Cheap Channel Code: The Symbolic Language’s Role in Cognition
Teixeira, M. H. D. S. (2016) · Psychology and Cognitive Sciences - Open Journal · doi:10.17140/pcsoj-2-109
Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations
Hromkovic̆, J. (2024) · Theoretical Computer Science · doi:10.1016/j.tcs.2024.114747 · Cited by 1 · see citing works
Lower Bounds for Levin–Kolmogorov Complexity
Brandt, N. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-78011-0_7
Can observed entropy detect congestion in Ad-Hoc networks?
Liu, X., & Speidel, U. (2017) · International Telecommunication Networks and Applications Conference (ITNAC) · doi:10.1109/atnac.2017.8215384 · Cited by 1 · see citing works
Bátfai, N. (2018) · Információs Társadalom · doi:10.22503/inftars.xviii.2018.2.2 · Cited by 1 · see citing works
Bapty, T., Neema, S. K., & Sztipanovits, J. (2013) · doi:10.21236/ada589389 · Cited by 1 · see citing works
An Information-Theoretic Metric of System Complexity with Application to Engineering System Design
Allaire, D., He, Q., & Willcox, K. E. (2012) · AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference (SDM) · doi:10.2514/6.2012-1430
Temperature Effects, Frieden-Hawkins' Order-Measure, and
Pennini, F., Plastino, A., & Ferri, G. L. (2012)
Quantum random number generators for industrial applications
Sánchez, C. A. (2018) · doi:10.5821/dissertation-2117-120989
Prause, C. R., & Reiners, R. (2022) · Fraunhofer-Publica (Fraunhofer-Gesellschaft) · doi:10.24406/publica-fhg-372210
Effective Complexity: In Which Sense is It Informative?
Céspedes, E., & Fuentes, M. (2020) · Journal for General Philosophy of Science · doi:10.1007/s10838-019-09487-1
Sobre aspectos contextuales y ontológicos de la emergencia y de la reducción
Céspedes, E. (2020) · Eidos · doi:10.14482/eidos.32.302.35
The Relativity of InductionPreprint
Muhlstein, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.10613
Pass, R., & Venkitasubramaniam, M. (2021) · ACM SIGACT News · doi:10.1145/3457588.3457598
The Whole and the Parts: The Minimum Description Length Principle and the A-Contrario Framework
von Gioi, R. G., Ramírez, I., & Randall, G. (2022) · SIAM Journal on Imaging Sciences · doi:10.1137/21m145745x
A study on comparison of pseudorandom number generator
Padányi, V., & Herendi, T. (2023) · International Journal of Mathematics and Computer in Engineering · doi:10.2478/ijmce-2023-0003
Mazor, N., Pass, R., & Solomon, T. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-12293-3_6
Algebraic barriers to halving algorithmic information quantities in correlated strings
Romashchenko, A. (2025) · Information and Computation · doi:10.1016/j.ic.2025.105396
The Computational Kosmoplex: A Principia for Engineers in the Age of AI
Macedonia, C. R. (2026) · Computer · doi:10.1109/mc.2025.3590236
Complexity of finite statistical systems
Yukalov, V. I., & Yukalova, E. P. (2026) · Laser Physics Letters · doi:10.1088/1612-202x/aeb111
- Authors
- Chaitin, G. J.
- Affiliations
- Mario Bravo 249, Buenos Aires, Argentina and Buenos Aires, Argentina
- Corresponding author
- Chaitin, Gregory J.
- Venue
- Journal of the ACM
- Published
- 1969-07
- Volume
- 16
- Issue
- 3
- Pages
- 407-422
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W1977165845
- Cited by
- 99
- References
- 17
- Citations by year
- 2026: 2 · 2025: 4 · 2024: 7 · 2023: 8 · 2022: 3 · 2021: 5 · 2020: 9 · 2019: 3 · 2018: 3 · 2017: 5 · 2016: 6 · 2015: 3 · 2014: 3 · 2013: 9 · 2012: 9
- FWCI
- 0.95
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Journal of the ACM (publishedVersion)
- 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 › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Keywords
- natural numbers, computational complexity, Turing machines, computable sets
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
