On the Length of Programs for Computing Finite Binary Sequences
From MaRDI portal
Publication:5541327
DOI10.1145/321356.321363zbMath0158.25301WikidataQ29398287 ScholiaQ29398287MaRDI QIDQ5541327
Publication date: 1966
Published in: Journal of the ACM (Search for Journal in Brave)
Related Items
Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT, Quantum information distance, Entropy estimation of symbol sequences, Counting probability distributions: Differential geometry and model selection, Computational depth and reducibility, [https://portal.mardi4nfdi.de/wiki/Publication:5581622 Eine Bemerkung zum Begriff der zuf�lligen Folge], Algorithmic complexity of points in dynamical systems, Dimension spectra of lines1, A statistical complexity measure with nonextensive entropy and quasi-multiplicativity, Martingales in the Study of Randomness, Renormalized entropy for one dimensional discrete maps: periodic and quasi-periodic route to chaos and their robustness, A LEARNING-THEORETIC CHARACTERISATION OF MARTIN-LÖF RANDOMNESS AND SCHNORR RANDOMNESS, Not all (possibly) “random” sequences are created equal, Minimal-program complexity of pseudo-recursive and pseudo-random sequences, Relations between varieties of kolmogorov complexities, Foundations of Support Constraint Machines, Alan Turing and the Foundation of Computer Science, Quantum Algorithmic Complexities and Entropy, Observations on the generation of permutations from random sequences, Justifying Additive Noise Model-Based Causal Discovery via Algorithmic Information Theory, Asymptotical behaviour of some non-uniform measures, Configuration complexity assessment of convergent supply chain systems, Shannon entropy: a rigorous notion at the crossroads between probability, information theory, dynamical systems and statistical physics, A generalized statistical complexity measure: Applications to quantum systems, Recursively enumerable reals and Chaitin \(\Omega\) numbers, Predictability: a way to characterize complexity, Algorithmic complexity of real financial markets, Regression Estimation from an Individual Stable Sequence, Quantum Kolmogorov complexity, Arithmetical representations of Brownian motion I, APPROXIMATE, NON-DETERMINISTIC MODELLING OF BEHAVIOUR SEQUENCES, Shiner–Davison–Landsberg complexity revisited, Artificial sequences and complexity measures, Quasi-Monte Carlo methods and pseudo-random numbers, Enumerations of the Kolmogorov function, Kolmogorov-Complexity Based on Infinite Computations, Complexity Invariance by Replication in the Quantum Square Well, Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness, Hierarchical approach to complexity with applications to dynamical systems, Information density, structure and entropy in equilibrium and non-equilibrium systems, Observations on Computability, Uncertainty, and Technology, A geometric approach to complexity, Convergence rates for the minimum complexity estimator of counting process intensities∗, Development of metrics and a complexity scale for the topology of assembly supply chains, Computational depth and reducibility, Generation of symmetric exponential sums, A Note on Blum Static Complexity Measures, The structural complexity of DNA templates -- implications on cellular complexity, The dimensions of individual strings and sequences, On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, On the notion of infinite pseudorandom sequences, Sophistication revisited, On solving hard problems by polynomial-size circuits, Sub-computable Bounded Pseudorandomness, The representation and manipulation of the algorithmic probability measure for problem solving., The Kolmogorov complexity of infinite words, Algorithmic complexity as a criterion of unsolvability, Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces, Natural halting probabilities, partial randomness, and zeta functions, What is quantum information?, Algorithmic complexity of quantum capacity, Tape versus queue and stacks: The lower bounds, On the advice complexity of the \(k\)-server problem, Complexity study of \(q\)-deformed quantum harmonic oscillator, The discovery of algorithmic probability, Stochastic complexity in learning, Open problems in universal induction \& intelligence, A network of autoregressive processing units for time series modeling, An unpredictability approach to finite-state randomness, On graph entropy measures based on the number of independent sets and matchings, Complexity as a contrast between dynamics and phenomenology, Information dissipation in quantum-chaotic systems: Computational view and measurement induction, Entropy and algorithmic complexity in quantum information theory, Quantifying complexity in the minority game, On measuring the complexity of networks: Kolmogorov complexity versus entropy, Genus distributions for iterated claws, QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS, Disentangling complexity from randomness and chaos, A catalog of Boolean concepts., Information theory: A multifaceted model of information, Axiomatizing Kolmogorov complexity, One-way functions using algorithmic and classical information theories, Complexity of algorithms and computations, Comment on the Shiner-Davison-Landsberg measure, Approximate Entropy as an Irregularity Measure for Financial Data, Real patterns and indispensability, Statistical complexity and Fisher-Shannon information measure of \(H^{+}_{2}\), Deflating the deflationary view of information, Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov), Theory construction in psychology: The interpretation and integration of psychological data, Minimum message length encoding and the comparison of macromolecules, Low-depth witnesses are easy to find, Information-theoretical complexity for the hydrogenic identity \(S_N2\) exchange reaction, Simplicity and likelihood: an axiomatic approach, Impugning randomness, convincingly, A comparison of Shannon, Kullback-Leibler and renormalized entropies within successive bifurcations, Entropy measures vs. Kolmogorov complexity, Physical complexity of symbolic sequences, Algorithmic complexity of recursive and inductive algorithms, Random languages for nonuniform complexity classes, Algorithmic information theory and its statistical mechanical interpretation, Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem, Nonuniform complexity and the randomness of certain complete languages, Almost everywhere high nonuniform complexity, On the Advice Complexity of the k-Server Problem, LISP program-size complexity, What is Shannon information?, Sophistication vs logical depth, LISP program-size complexity. III, THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS, Dynamics of a generic Brownian motion: Recursive aspects, Circuit size relative to pseudorandom oracles, Infotropism as the underlying principle of perceptual organization, Fisher-Shannon plane and statistical complexity of atoms, Unnamed Item, Process and truth-table characterisations of randomness, Automaton introspection, A theory of information structure I. General principles, Relations between information criteria for model-structure selection Part 2. Modelling by shortest data description, On the inference of optimal descriptions, Finite approximate approach to the study of the complexity of recursive predicates, Model discrimination using an algorithmic information criterion, Hydrozip: how hydrological knowledge can be used to improve compression of hydrological data, Effective entropies and data compression, Towards an Axiomatic System for Kolmogorov Complexity, Sets with small generalized Kolmogorov complexity, Subrecursive programming languages. II. On program size, Some consequences of the existnce of pseudorandom generators, Endliche Automaten und Zufallsfolgen, Degrees of monotone complexity, Computational complementarity, Information and complexity, or: where is the information?, Toward an abstract theory of data compression, The descriptive complexity of Brownian motion, Thinking with notations: epistemic actions and epistemic activities in mathematical practice, On the syntactic structure of protein sequences and the concept of grammar complexity, An upward measure separation theorem, A comparison of two approaches to pseudorandomness, Randomness on full shift spaces, Cryptography and algorithmic randomness, Statistical learning theory, model identification and system information content, Data compression and learning in time sequences analysis, Identifying randomness given by high descriptive complexity
