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

DOI10.1145/321526.321530MaRDI QIDQ5579042zbMATH OpenOpenAlexDBLPWikidataFDO

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
• Temperature effects, Frieden-Hawkins' order-measure, and Wehrl entropy
• One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions
• 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)