THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

DOI10.1070/rm1970v025n06ABEH001269zbMath0222.02027MaRDI QIDQ5626617

Alexander K. Zvonkin, Leonid A. Levin

Publication date: 1970

Published in: Russian Mathematical Surveys (Search for Journal in Brave)

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

Related Items

Program size complexity for possibly infinite computations, Effective entropies and data compression, Constructive chaos by cellular automata and possible sources of an arrow of time, On the syntactic structure of protein sequences and the concept of grammar complexity, Constructive dimension equals Kolmogorov complexity, Dynamic modeling of internet traffic for intrusion detection, Quantum cooperative search algorithm for 3-sat, On generalized computable universal priors and their convergence, Algorithmic complexity bounds on future prediction errors, Milking the Aanderaa argument, Efficient coding of approximations of real numbers, Effectively closed sets of measures and randomness, Algorithmically independent sequences, Kolmogorov-Loveland stochasticity and Kolmogorov complexity, On a definition of random sequences with respect to conditional probability, Gales suffice for constructive dimension, Scaled dimension and the Kolmogorov complexity of Turing-hard sets, Dimension extractors and optimal decompression, On calibration error of randomized forecasting algorithms, On universal transfer learning, Instability, complexity, and evolution, Stationary algorithmic probability, The dynamics of symmetric nets, On the relation between descriptional complexity and algorithmic probability, On the notion of infinite pseudorandom sequences, Complexity of algorithms and computations, Complexity of functions: Some questions, conjectures, and results, Some properties of random number generators, Average case completeness, Organization by rules in finite sequences, Inductive reasoning and Kolmogorov complexity, Average case complexity under the universal distribution equals worst- case complexity, Note on the topological structure of random strings, On the inference of optimal descriptions, Model discrimination using an algorithmic information criterion, Mathematical metaphysics of randomness, On common information, Ergodic theorems for individual random sequences, Non-stochastic infinite and finite sequences, Noncomputability arising in dynamical triangulation model of four- dimensional quantum gravity, Computational depth and reducibility, The discovery of algorithmic probability, \(\varepsilon\)-Entropy of compact sets in \(C\) and tabulation of continuous functions, Random elements in effective topological spaces with measure., Algorithmic complexity of recursive and inductive algorithms, Inequalities for Shannon entropy and Kolmogorov complexity, The Kolmogorov complexity of real numbers., Predictive complexity and information, Symmetry of information and one-way functions, Symbolic dynamics of one-dimensional maps: Entropies, finite precision, and noise, Complexity measures of words based on string matching and edit distance, Recursive computational depth., Most sequences are stochastic, Suboptimal measures of predictive complexity for absolute loss function, On complexity of easy predictable sequences, Algorithmic analysis of irrational rotations in a single neuron model, Randomness and reducibility, The dimensions of individual strings and sequences, The Kolmogorov complexity of random reals, Universal computation and physical dynamics, Geometry of the space of triangulations of a compact manifold, Limit complexities revisited, A cell dynamical system model of chemical turbulence., Physical complexity of symbolic sequences, On the computational power of random strings, On semimeasures predicting Martin-Löf random sequences, On universal prediction and Bayesian confirmation, `Ideal learning' of natural language: positive results about learning from positive evidence, The Kolmogorov complexity of infinite words, Computability of probability measures and Martin-Löf randomness over metric spaces, A coding theorem for enumerable output machines, Predicting non-stationary processes, Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem, Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets, Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series, Uniform test of algorithmic randomness over a general space, How many strings are easy to predict?, Resource bounded symmetry of information revisited, Kolmogorov-Loveland randomness and stochasticity, Experimental investigation of forecasting methods based on data compression algorithms, Sequential predictions based on algorithmic complexity, An almost machine-independent theory of program-length complexity, sophistication, and induction, THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS, Partial Randomness and Dimension of Recursively Enumerable Reals, Unnamed Item, Calibrating Randomness, On Sequences with Non-learnable Subsequences, On initial segment complexity and degrees of randomness, On Universal Transfer Learning, On Calibration Error of Randomized Forecasting Algorithms, Algorithmically Independent Sequences, Quantum Algorithmic Complexities and Entropy, An Application of Martin-Löf Randomness to Effective Probability Theory, On Generating Independent Random Strings, Unnamed Item, On universal computably enumerable prefix codes, Coding Strings by Pairs of Strings, Embedding recursive functions in universal algorithms, Unnamed Item, Generalized kolmogorov complexity and other dual complexity measures, A test for randomness based on a complexity measure, Algorithmic complexity of points in dynamical systems, Relations between varieties of kolmogorov complexities, Enumerations of the Kolmogorov function, New error bounds for Solomonoff prediction, Comparison between the complexity of a function and the complexity of its graph, Descriptive complexity of computable sequences, Kolmogorov complexity conditional to large integers, General linear relations between different types of predictive complexity, Unnamed Item