On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers

DOI10.1145/321526.321530zbMATH Open0187.28401DBLPjournals/jacm/Chaitin69aOpenAlexW1977165845WikidataQ56038297 ScholiaQ56038297MaRDI QIDQ5579042FDOQ5579042

Authors: Gregory J. Chaitin 

Publication date: 1969

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321526.321530

zbMATH Keywords

languages, automata, networks

Cited In (13)

• Fractal analysis of pi normality
• The whole and the parts: the minimum description length principle and the a-contrario framework
• One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions
• Temperature effects, Frieden-Hawkins' order-measure, and Wehrl entropy
• On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
• Language-theoretic complexity of disjunctive sequences
• `Ideal learning' of natural language: positive results about learning from positive evidence
• Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations
• Algorithmic complexity as a criterion of unsolvability
• The principles of informational genomics
• On grammars, complexity, and information measures of biological macromolecules
• Toward an abstract theory of data compression
• The critical roles of information and nonequilibrium thermodynamics in evolution of living systems

This page was built for publication: On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5579042)