A variant of the Kolmogorov concept of complexity
From MaRDI portal
Publication:5582801
DOI10.1016/S0019-9958(69)90538-5zbMath0188.52101WikidataQ56814470 ScholiaQ56814470MaRDI QIDQ5582801
Publication date: 1969
Published in: Information and Control (Search for Journal in Brave)
Related Items
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
