A Theory of Program Size Formally Identical to Information Theory
From MaRDI portal
Publication:4068087
DOI10.1145/321892.321894zbMath0309.68045OpenAlexW2020311636MaRDI QIDQ4068087
Publication date: 1975
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321892.321894
Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) General topics in the theory of software (68N01)
Related Items (only showing first 100 items - show all)
Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets ⋮ The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity ⋮ Kolmogorov complexity arguments in combinatorics ⋮ Measuring prime program complexity ⋮ Randomness and reducibility ⋮ Computational depth and reducibility ⋮ The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite ⋮ Relating and contrasting plain and prefix Kolmogorov complexity ⋮ Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations ⋮ On collapsing the polynomial-time hierarchy ⋮ Characterising the Martin-Löf random sequences using computably enumerable sets of measure one ⋮ On Kurtz randomness ⋮ The dimensions of individual strings and sequences ⋮ The Kolmogorov complexity of random reals ⋮ On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line ⋮ On the notion of infinite pseudorandom sequences ⋮ Universal computation and physical dynamics ⋮ Incompleteness theorems for random reals ⋮ Natural halting probabilities, partial randomness, and zeta functions ⋮ On generalized computable universal priors and their convergence ⋮ Randomness and universal machines ⋮ Computable model discovery and high-level-programming approximations to algorithmic complexity ⋮ The discovery of algorithmic probability ⋮ On randomness, determinism and computability ⋮ Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy ⋮ Undecidability of the structure of the Solovay degrees of c.e. reals ⋮ Optimal redundancy in computations from random oracles ⋮ Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension ⋮ Universal computably enumerable sets and initial segment prefix-free complexity ⋮ Simplicity via provability for universal prefix-free Turing machines ⋮ Fixed point theorems on partial randomness ⋮ A generalized characterization of algorithmic probability ⋮ Random elements in effective topological spaces with measure. ⋮ Several results in program size complexity ⋮ An additivity theorem for plain Kolmogorov complexity ⋮ Oscillation in the initial segment complexity of random reals ⋮ Elementary differences between the degrees of unsolvability and degrees of compressibility ⋮ A linearly computable measure of string complexity ⋮ The cellular computer DNA: Program or data ⋮ Constraints placed on random sequences by their compressibility ⋮ Feasible reductions to Kolmogorov-Loveland stochastic sequences ⋮ Information-geometric approach to inferring causal directions ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ An extended coding theorem with application to quantum complexities ⋮ On the hierarchy and extension of monotonically computable real numbers. ⋮ Schnorr trivial reals: a construction ⋮ On the number of infinite sequences with trivial initial segment complexity ⋮ Physical complexity of symbolic sequences ⋮ Algorithmic complexity of recursive and inductive algorithms ⋮ Epistemic horizons and the foundations of quantum mechanics ⋮ Generic oracles, uniform machines, and codes ⋮ On independent random oracles ⋮ Random sequences with respect to a measure defined by two linear fractional transformations ⋮ Solovay functions and their applications in algorithmic randomness ⋮ Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs ⋮ Universal forecasting algorithms ⋮ Inductive reasoning and Kolmogorov complexity ⋮ Randomness for computable measures and initial segment complexity ⋮ Conditional measure and the violation of van Lambalgen's theorem for Martin-Löf randomness ⋮ Information-theoretic incompleteness ⋮ Random numbers as probabilities of machine behavior ⋮ Kobayashi compressibility ⋮ The scope of Gödel's first incompleteness theorem ⋮ Algorithmically independent sequences ⋮ Universal recursively enumerable sets of strings ⋮ A Chaitin \(\Omega\) number based on compressible strings ⋮ \(\Sigma^ 0_ n\)-complete properties of programs and Martin-Löf randomness ⋮ On the algorithmic complexity of static structures ⋮ Program size complexity for possibly infinite computations ⋮ Information-theoretic characterizations of recursive infinite strings ⋮ On the computational power of random strings ⋮ Kolmogorov complexity for possibly infinite computations ⋮ Representation of left-computable \(\varepsilon \)-random reals ⋮ Mathematics as information compression via the matching and unification of patterns ⋮ Algorithmic entropy of sets ⋮ Randomness, independence, and hypotheses ⋮ Computing halting probabilities from other halting probabilities ⋮ Polynomial time over the reals with parsimony ⋮ Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega ⋮ Hydrozip: how hydrological knowledge can be used to improve compression of hydrological data ⋮ Scaled dimension and the Kolmogorov complexity of Turing-hard sets ⋮ Dimension extractors and optimal decompression ⋮ On universal transfer learning ⋮ Gödel's theorem and information ⋮ Randomness and initial segment complexity for measures ⋮ Sets with small generalized Kolmogorov complexity ⋮ Some consequences of the existnce of pseudorandom generators ⋮ Stationary algorithmic probability ⋮ Toward an abstract theory of data compression ⋮ On the relation between descriptional complexity and algorithmic probability ⋮ Recursive computational depth. ⋮ Thinking with notations: epistemic actions and epistemic activities in mathematical practice ⋮ Chaitin \(\Omega\) numbers, Solovay machines, and Gödel incompleteness. ⋮ The closure properties on real numbers under limits and computable operators. ⋮ Presentations of computably enumerable reals. ⋮ Uncontrollable computational growth in theoretical physics ⋮ Randomness on full shift spaces ⋮ Finite state incompressible infinite sequences ⋮ Algorithmic analysis of irrational rotations in a single neuron model ⋮ A Church-Turing thesis for randomness?
This page was built for publication: A Theory of Program Size Formally Identical to Information Theory
