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.02027OpenAlexW2029308360MaRDI QIDQ5626617

Leonid A. Levin, Alexander K. Zvonkin

Publication date: 1970

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

Full work available at URL: https://doi.org/10.1070/rm1970v025n06abeh001269

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

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 ⋮ Constructive dimension equals Kolmogorov complexity ⋮ The dimensions of individual strings and sequences ⋮ The Kolmogorov complexity of random reals ⋮ Dynamic modeling of internet traffic for intrusion detection ⋮ On the notion of infinite pseudorandom sequences ⋮ Universal computation and physical dynamics ⋮ Quantum cooperative search algorithm for 3-sat ⋮ Algorithmic complexity of quantum capacity ⋮ Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers ⋮ On generalized computable universal priors and their convergence ⋮ An approach of randomness of a sample based on its weak ergodic limit ⋮ Algorithmic complexity bounds on future prediction errors ⋮ The discovery of algorithmic probability ⋮ Open problems in universal induction \& intelligence ⋮ Obituary: Ray Solomonoff, founding father of algorithmic information theory ⋮ \(\varepsilon\)-Entropy of compact sets in \(C\) and tabulation of continuous functions ⋮ Geometry of the space of triangulations of a compact manifold ⋮ Monoidal computer. I: Basic computability by string diagrams ⋮ Conditional Kolmogorov complexity and universal probability ⋮ Calculating and drawing Belyi pairs ⋮ Strict process machine complexity ⋮ Exact constructive and computable dimensions ⋮ A generalized characterization of algorithmic probability ⋮ Layerwise computability and image randomness ⋮ Random elements in effective topological spaces with measure. ⋮ Using ideas of Kolmogorov complexity for studying biological texts ⋮ One-way functions using algorithmic and classical information theories ⋮ Oscillation in the initial segment complexity of random reals ⋮ Complexity of algorithms and computations ⋮ On an algorithm to generate weakly correlated random numbers ⋮ Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov) ⋮ A linearly computable measure of string complexity ⋮ An algorithmic look at financial volatility ⋮ Milking the Aanderaa argument ⋮ Limit complexities revisited ⋮ Efficient coding of approximations of real numbers ⋮ A cell dynamical system model of chemical turbulence. ⋮ Complexity of functions: Some questions, conjectures, and results ⋮ Physical complexity of symbolic sequences ⋮ Short lists for shortest descriptions in short time ⋮ Some properties of random number generators ⋮ Average case completeness ⋮ Algorithmic complexity of recursive and inductive algorithms ⋮ Organization by rules in finite sequences ⋮ Random sequences with respect to a measure defined by two linear fractional transformations ⋮ Fractal dimension versus process complexity ⋮ Inductive reasoning and Kolmogorov complexity ⋮ Randomness for computable measures and initial segment complexity ⋮ Average case complexity under the universal distribution equals worst- case complexity ⋮ New statistical models of nonergodic cognitive systems and their pathologies ⋮ Effectively closed sets of measures and randomness ⋮ Error-correcting codes and phase transitions ⋮ Strong reductions in effective randomness ⋮ On empirical meaning of randomness with respect to parametric families of probability distributions ⋮ Algorithmically independent sequences ⋮ A Chaitin \(\Omega\) number based on compressible strings ⋮ Randomness on computable probability spaces -- a dynamical point of view ⋮ Kolmogorov-Loveland stochasticity and Kolmogorov complexity ⋮ Note on the topological structure of random strings ⋮ Program size complexity for possibly infinite computations ⋮ Process and truth-table characterisations of randomness ⋮ Nonapproximability of the normalized information distance ⋮ Predictive complexity and information ⋮ The random members of a \({\Pi }_{1}^{0}\) class ⋮ On the inference of optimal descriptions ⋮ On a definition of random sequences with respect to conditional probability ⋮ Symmetry of information and one-way functions ⋮ Gales suffice for constructive dimension ⋮ Model discrimination using an algorithmic information criterion ⋮ Putnam's diagonal argument and the impossibility of a universal learning machine ⋮ 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 ⋮ Effective entropies and data compression ⋮ Constructive chaos by cellular automata and possible sources of an arrow of time ⋮ Mathematical metaphysics of randomness ⋮ On common information ⋮ Ergodic theorems for individual random sequences ⋮ Non-stochastic infinite and finite sequences ⋮ Martin-Löf randomness and Galton-Watson processes ⋮ Inequalities for Shannon entropy and Kolmogorov complexity ⋮ Instability, complexity, and evolution ⋮ Stationary algorithmic probability ⋮ Symbolic dynamics of one-dimensional maps: Entropies, finite precision, and noise ⋮ Complexity measures of words based on string matching and edit distance ⋮ The dynamics of symmetric nets ⋮ On the relation between descriptional complexity and algorithmic probability ⋮ Recursive computational depth. ⋮ Most sequences are stochastic ⋮ Suboptimal measures of predictive complexity for absolute loss function ⋮ On complexity of easy predictable sequences ⋮ On the syntactic structure of protein sequences and the concept of grammar complexity ⋮ Noncomputability arising in dynamical triangulation model of four- dimensional quantum gravity ⋮ The Kolmogorov complexity of real numbers. ⋮ Finite state incompressible infinite sequences ⋮ Algorithmic analysis of irrational rotations in a single neuron model

This page was built for publication: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS