On the Length of Programs for Computing Finite Binary Sequences
From MaRDI portal
Publication:5579041
DOI10.1145/321495.321506zbMath0187.28303OpenAlexW2154462988MaRDI QIDQ5579041
Publication date: 1969
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321495.321506
Related Items
Exploring programmable self-assembly in non-DNA based molecular computing ⋮ A Quest for Algorithmically Random Infinite Structures, II ⋮ Computational depth and reducibility ⋮ A Note on Blum Static Complexity Measures ⋮ Computational depth and reducibility ⋮ The dimensions of individual strings and sequences ⋮ On the notion of infinite pseudorandom sequences ⋮ Large alphabets and incompressibility ⋮ Dimension spectra of lines1 ⋮ The discovery of algorithmic probability ⋮ Stochastic complexity in learning ⋮ Complexity as a contrast between dynamics and phenomenology ⋮ Leveraging environmental correlations: the thermodynamics of requisite variety ⋮ Differential equations as deterministic models in science and technology Part I: Modelling ⋮ Structure and randomness of continuous-time, discrete-event processes ⋮ Disentangling complexity from randomness and chaos ⋮ Martingales in the Study of Randomness ⋮ On initial segment complexity and degrees of randomness ⋮ A computable measure of algorithmic probability by finite approximations with an application to integer sequences ⋮ Randomness as an invariant for number representations ⋮ Comparing descriptional and computational complexity of infinite words ⋮ COMPLEXITY, INFORMATION, ENERGY ⋮ Minimal-program complexity of pseudo-recursive and pseudo-random sequences ⋮ Relations between varieties of kolmogorov complexities ⋮ Face Representations via Tensorfaces of Various Complexities ⋮ Quantum Kolmogorov complexity and information-disturbance theorem ⋮ Algorithmic relative complexity ⋮ Quantitative and qualitative growth analysis ⋮ Model selection based on minimum description length ⋮ Alan Turing and the Foundation of Computer Science ⋮ Generic oracles, uniform machines, and codes ⋮ Inductive reasoning and Kolmogorov complexity ⋮ LISP program-size complexity ⋮ LISP program-size complexity. III ⋮ HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT ⋮ Information measures for infinite sequences ⋮ Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks ⋮ Descriptive complexity of computable sequences ⋮ Descriptive complexity of computable sequences revisited ⋮ Symmetry of information and one-way functions ⋮ The calculi of emergence: Computation, dynamics and induction ⋮ Degrees of monotone complexity ⋮ Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness ⋮ Toward an abstract theory of data compression ⋮ Thinking with notations: epistemic actions and epistemic activities in mathematical practice ⋮ Fluctuation spectroscopy ⋮ Turing patterns with Turing machines: emergence and low-level structure formation
