A variant of the Kolmogorov concept of complexity

DOI10.1016/S0019-9958(69)90538-5zbMath0188.52101WikidataQ56814470 ScholiaQ56814470MaRDI QIDQ5582801

Donald W. Loveland

Publication date: 1969

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

zbMATH Keywords

information, communication

Related Items (35)

Compressibility and uniform complexity ⋮ On the notion of infinite pseudorandom sequences ⋮ A test for randomness based on a complexity measure ⋮ Learning recursive functions from approximations ⋮ An unpredictability approach to finite-state randomness ⋮ Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra ⋮ Several results in program size complexity ⋮ Complexity of algorithms and computations ⋮ Minimal-program complexity of pseudo-recursive and pseudo-random sequences ⋮ Relations between varieties of kolmogorov complexities ⋮ Oracles and Advice as Measurements ⋮ Algorithmic complexity of recursive and inductive algorithms ⋮ Strong jump-traceability. I: The computably enumerable case ⋮ Trivial Reals ⋮ Kobayashi compressibility ⋮ The frequent paucity of trivial strings ⋮ Process complexity and effective random tests ⋮ Information-theoretic characterizations of recursive infinite strings ⋮ Kolmogorov complexity for possibly infinite computations ⋮ Time-bounded incompressibility of compressible strings and sequences ⋮ Comparison between the complexity of a function and the complexity of its graph ⋮ Descriptive complexity of computable sequences ⋮ Kolmogorov complexity and non-determinism ⋮ On the inference of optimal descriptions ⋮ Philosophical issues in Kolmogorov complexity ⋮ Descriptive complexity of computable sequences revisited ⋮ Recursively compressible sets ⋮ Endliche Automaten und Zufallsfolgen ⋮ $K$-triviality in computable metric spaces ⋮ Calibrating Randomness ⋮ Degrees of monotone complexity ⋮ Toward an abstract theory of data compression ⋮ On the relation between descriptional complexity and algorithmic probability ⋮ Sequential predictions based on algorithmic complexity ⋮ Algorithmic analysis of irrational rotations in a single neuron model

This page was built for publication: A variant of the Kolmogorov concept of complexity