THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
From MaRDI portal
Publication:5626617
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
Related Items
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, Continuous randomness via transformations of 2-random sequences, Martingales in the Study of Randomness, Andrei Kolmogorov and Leonid Levin on Randomness, One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions, Extraction rates of random continuous functionals, Turing degrees and randomness for continuous measures, On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \), Randomness extraction in computability theory, A Quest for Algorithmically Random Infinite Structures, II, A Note on Blum Static Complexity Measures, Computer Runtimes and the Length of Proofs, Symmetry of Information: A Closer Look, Computational depth and reducibility, The Whole and the Parts: The Minimum Description Length Principle and the A-Contrario Framework, Equivalence of measures of complexity classes, A Correspondence Principle for Exact Constructive Dimension, The Intersection of Algorithmically Random Closed Sets and Effective Dimension, A test for randomness based on a complexity measure, 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, Partial Randomness and Dimension of Recursively Enumerable Reals, Unnamed Item, The Kolmogorov complexity of infinite words, An almost machine-independent theory of program-length complexity, sophistication, and induction, DEGREES OF RANDOMIZED COMPUTABILITY, Computability of probability measures and Martin-Löf randomness over metric spaces, MODELING QUANTUM MECHANICAL OBSERVERS VIA NEURAL-GLIAL NETWORKS, A coding theorem for enumerable output machines, Algorithmic complexity of points in dynamical systems, Clustering with respect to the information distance, Gacs-Kucera theorem, Unnamed Item, Generalized kolmogorov complexity and other dual complexity measures, Unnamed Item, Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy, Universality probability of a prefix-free machine, DEEP CLASSES, On the Regularities of Mass Random Phenomena, On Sequences with Non-learnable Subsequences, The Kučera-Gács theorem revisited by Levin, On initial segment complexity and degrees of randomness, Predicting non-stationary processes, Closed left-r.e. sets, On Universal Transfer Learning, On Calibration Error of Randomized Forecasting Algorithms, Unnamed Item, Relations between varieties of kolmogorov complexities, Algorithmically Independent Sequences, Embedding recursive functions in universal algorithms, An incomplete set of shortest descriptions, Algorithmic information theory and its statistical mechanical interpretation, Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem, Hilbert’s sixth problem: the endless road to rigour, Closed Left-R.E. Sets, Quantum Algorithmic Complexities and Entropy, Hilbert’s 6th Problem: exact and approximate hydrodynamic manifolds for kinetic equations, THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS, Things that can be made into themselves, Refined Bounds on Kolmogorov Complexity for ω-Languages, On Oscillation-free ε-random Sequences, An Application of Martin-Löf Randomness to Effective Probability Theory, On Generating Independent Random Strings, Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization, Algorithmic randomness over general spaces, Bicompletions of Distance Matrices, Selection by Recursively Enumerable Sets, On Martin-Löf Convergence of Solomonoff’s Mixture, Zipf's law and L. Levin probability distributions, Unnamed Item, New error bounds for Solomonoff prediction, On the computational power of random strings, Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets, Unnamed Item, Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series, 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, Algorithmic tests and randomness with respect to a class of measures, On joint conditional complexity (entropy), On universal computably enumerable prefix codes, RANK AND RANDOMNESS, Predictive Complexity for Games with Finite Outcome Spaces, Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension, Increasing the gap between descriptional complexity and algorithmic probability, Enumerations of the Kolmogorov function, On Approximate Decidability of Minimal Programs, Things Bayes Can’t Do, TIME AND A TEMPORALLY STATISTICAL QUANTUM GEOMETRODYNAMICS, Calibrating Randomness, Uniform test of algorithmic randomness over a general space, Randomness for non-computable measures, How many strings are easy to predict?, Measures and their random reals, Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness, 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, Effective randomness for continuous measures, Thinking with notations: epistemic actions and epistemic activities in mathematical practice, On Martin-Löf (non-)convergence of Solomonoff's universal mixture, Coding Strings by Pairs of Strings, Trivial measures are not so trivial
