Randomness conservation inequalities; information and independence in mathematical theories

DOI10.1016/S0019-9958(84)80060-1zbMath0592.03035MaRDI QIDQ3720586

Publication date: 1984

Published in: Information and Control (Search for Journal in Brave)

intuitionistic logic probability theory algorithmic information theory of algorithms Kolmogorov's algorithmic complexity theory mutual information in individual infinite sequences

Mathematics Subject Classification ID

Information theory (general) (94A15) Applications of computability and recursion theory (03D80) Algorithms in computer science (68W99)

Related Items (63)

Computational depth and reducibility ⋮ Computational depth and reducibility ⋮ When does randomness come from randomness? ⋮ 2011 North American Annual Meeting of the Association for Symbolic Logic ⋮ UNIVERSAL CODING AND PREDICTION ON ERGODIC RANDOM POINTS ⋮ Computational depth: Concept and applications ⋮ NL-printable sets and nondeterministic Kolmogorov complexity ⋮ Universal computation and physical dynamics ⋮ On Quantum Algorithm for Binary Search and Its Computational Complexity ⋮ An almost machine-independent theory of program-length complexity, sophistication, and induction ⋮ DEGREES OF RANDOMIZED COMPUTABILITY ⋮ A zero-one law for RP and derandomization of AM if NP is not small ⋮ Open problems in universal induction \& intelligence ⋮ INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH ⋮ HOW DIFFICULT IS IT TO INVENT A NONTRIVIAL GAME? ⋮ The minimum oracle circuit size problem ⋮ DEEP CLASSES ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Generation Complexity Versus Distinction Complexity ⋮ The Kolmogorov birthday paradox ⋮ Learning efficient logic programs ⋮ Random elements in effective topological spaces with measure. ⋮ Randomness as an invariant for number representations ⋮ Notes on sum-tests and independence tests ⋮ Algorithmic Statistics: Forty Years Later ⋮ The Complexity of Complexity ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Unnamed Item ⋮ Impugning randomness, convincingly ⋮ Algorithmically Independent Sequences ⋮ Unnamed Item ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ Inverse monoids associated with the complexity class NP ⋮ Universal forecasting algorithms ⋮ On the Polynomial Depth of Various Sets of Random Strings ⋮ Effectively closed sets of measures and randomness ⋮ THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS ⋮ On empirical meaning of randomness with respect to parametric families of probability distributions ⋮ Avoiding simplicity is complex ⋮ Algorithmically independent sequences ⋮ Circuit size relative to pseudorandom oracles ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity ⋮ Selection Theorem for Systems with Inheritance ⋮ Unnamed Item ⋮ Equivalences between learning of data and probability distributions, and their applications ⋮ Bounded Turing reductions and data processing inequalities for sequences ⋮ Kolmogorov complexity and non-determinism ⋮ Algorithmic tests and randomness with respect to a class of measures ⋮ Depth as randomness deficiency ⋮ Computability and information in models of randomness and chaos ⋮ Algorithmic Statistics Revisited ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Sample size lower bounds in PAC learning by Algorithmic Complexity Theory ⋮ Non-stochastic infinite and finite sequences ⋮ Some consequences of the existnce of pseudorandom generators ⋮ Uniform test of algorithmic randomness over a general space ⋮ Measures and their random reals ⋮ Most sequences are stochastic ⋮ Sequential predictions based on algorithmic complexity ⋮ An upward measure separation theorem

This page was built for publication: Randomness conservation inequalities; information and independence in mathematical theories