Process complexity and effective random tests
From MaRDI portal
Publication:2264549
DOI10.1016/S0022-0000(73)80030-3zbMath0273.68036DBLPjournals/jcss/Schnorr73WikidataQ29999183 ScholiaQ29999183MaRDI QIDQ2264549
Publication date: 1973
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items (98)
Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets ⋮ Randomness and reducibility ⋮ Computational depth and reducibility ⋮ Scaled dimension and nonuniform complexity ⋮ A Note on Blum Static Complexity Measures ⋮ The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite ⋮ Computational depth and reducibility ⋮ Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations ⋮ On collapsing the polynomial-time hierarchy ⋮ Relative to a random oracle, P/poly is not measurable in EXP ⋮ The dimensions of individual strings and sequences ⋮ Multiple Usage of Random Bits in Finite Automata ⋮ Equivalence of measures of complexity classes ⋮ On the notion of infinite pseudorandom sequences ⋮ Comparing notions of randomness ⋮ A test for randomness based on a complexity measure ⋮ Initial segment complexities of randomness notions ⋮ Partial Randomness and Dimension of Recursively Enumerable Reals ⋮ An almost machine-independent theory of program-length complexity, sophistication, and induction ⋮ Kolmogorov-Loveland stochasticity for finite strings ⋮ Schnorr randomness ⋮ Algorithmic complexity of points in dynamical systems ⋮ The discovery of algorithmic probability ⋮ Unnamed Item ⋮ Generalized kolmogorov complexity and other dual complexity measures ⋮ Weakly complete problems are not rare ⋮ Unnamed Item ⋮ Randomness? What randomness? ⋮ An improved zero-one law for algorithmically random sequences ⋮ Dimension 1 sequences are close to randoms ⋮ Strict process machine complexity ⋮ Kolmogorov and mathematical logic ⋮ Martingales in the Study of Randomness ⋮ On unstable and unoptimal prediction ⋮ A generalized characterization of algorithmic probability ⋮ Sequential mappings of $\omega $-languages ⋮ Algorithmic randomness and monotone complexity on product space ⋮ Time-bounded Kolmogorov complexity and Solovay functions ⋮ A linearly computable measure of string complexity ⋮ Relations between varieties of kolmogorov complexities ⋮ Feasible reductions to Kolmogorov-Loveland stochastic sequences ⋮ Universal Recursively Enumerable Sets of Strings ⋮ Algorithmic complexity of recursive and inductive algorithms ⋮ Algorithmic information theory and its statistical mechanical interpretation ⋮ Epistemic horizons and the foundations of quantum mechanics ⋮ On independent random oracles ⋮ Solovay functions and their applications in algorithmic randomness ⋮ Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs ⋮ Cook versus Karp-Levin: Separating completeness notions if NP is not small ⋮ Effective category and measure in abstract complexity theory ⋮ Weak completeness in \(\text{E}\) and \(\text{E}_{2}\) ⋮ Almost everywhere high nonuniform complexity ⋮ Random reals and possibly infinite computations Part I: Randomness in ∅′ ⋮ Strong jump-traceability. I: The computably enumerable case ⋮ Schnorr trivial sets and truth-table reducibility ⋮ HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT ⋮ Schnorr Randomness ⋮ Kobayashi compressibility ⋮ Universal recursively enumerable sets of strings ⋮ Algorithmic randomness over general spaces ⋮ A Chaitin \(\Omega\) number based on compressible strings ⋮ RECOGNIZING STRONG RANDOM REALS ⋮ Effective category and measure in abstract complexity theory ⋮ Randomness deficiencies ⋮ Recursively enumerable reals and Chaitin \(\Omega\) numbers ⋮ Program size complexity for possibly infinite computations ⋮ Information-theoretic characterizations of recursive infinite strings ⋮ Relativized Schnorr tests with universal behavior ⋮ On the computational power of random strings ⋮ Process and truth-table characterisations of randomness ⋮ General random sequences and learnable sequences ⋮ Toward a mathematical theory of graph-generative systems and its applications ⋮ Quantitative aspects of speed-up and gap phenomena ⋮ Unnamed Item ⋮ On the inference of optimal descriptions ⋮ Algorithmic tests and randomness with respect to a class of measures ⋮ On a definition of random sequences with respect to conditional probability ⋮ Dimension extractors and optimal decompression ⋮ Increasing the gap between descriptional complexity and algorithmic probability ⋮ Randomness and initial segment complexity for measures ⋮ 2005 Annual Meeting of the Association for Symbolic Logic ⋮ On the size of classes with weak membership properties ⋮ Genericity and randomness over feasible probability measures ⋮ Mathematical metaphysics of randomness ⋮ Ergodic theorems for individual random sequences ⋮ Randomness is inherently imprecise ⋮ Calibrating Randomness ⋮ Degrees of monotone complexity ⋮ Uniform test of algorithmic randomness over a general space ⋮ Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness ⋮ On the relation between descriptional complexity and algorithmic probability ⋮ Recursive computational depth. ⋮ Sequential predictions based on algorithmic complexity ⋮ Thinking with notations: epistemic actions and epistemic activities in mathematical practice ⋮ Cryptography and algorithmic randomness ⋮ Finite state incompressible infinite sequences ⋮ A stronger Kolmogorov zero-one law for resource-bounded measure ⋮ Identifying randomness given by high descriptive complexity
Cites Work
This page was built for publication: Process complexity and effective random tests
