Process complexity and effective random tests

Cites work

A formal theory of inductive inference. Part I
A variant of the Kolmogorov concept of complexity
Complexity oscillations in infinite binary sequences
scientific article; zbMATH DE number 3427210 (Why is no real title available?)
scientific article; zbMATH DE number 3339412 (Why is no real title available?)
Optimal enumerations and optimal gödel numberings
The definition of random sequences

Cited in

(only showing first 100 items - show all)

Dimension extractors and optimal decompression
On the relation between descriptional complexity and algorithmic probability
On the notion of infinite pseudorandom sequences
An improved zero-one law for algorithmically random sequences
On independent random oracles
Almost everywhere high nonuniform complexity
Information-theoretic characterizations of recursive infinite strings
Toward a mathematical theory of graph-generative systems and its applications
On the inference of optimal descriptions
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
Identifying randomness given by high descriptive complexity
Computational depth and reducibility
On collapsing the polynomial-time hierarchy
The discovery of algorithmic probability
Algorithmic complexity of recursive and inductive algorithms
Dimension 1 sequences are close to randoms
A generalized characterization of algorithmic probability
Epistemic horizons and the foundations of quantum mechanics
A Chaitin number based on compressible strings
Recursive computational depth.
A stronger Kolmogorov zero-one law for resource-bounded measure
Randomness and reducibility
Scaled dimension and nonuniform complexity
Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations
The dimensions of individual strings and sequences
Weakly complete problems are not rare
Time-bounded Kolmogorov complexity and Solovay functions
Feasible reductions to Kolmogorov-Loveland stochastic sequences
Randomness deficiencies
Randomness and initial segment complexity for measures
Randomness is inherently imprecise
Thinking with notations: epistemic actions and epistemic activities in mathematical practice
Randomness? What randomness?
On the computational power of random strings
Cryptography and algorithmic randomness
Kolmogorov-Loveland stochasticity for finite strings
Strong jump-traceability. I: The computably enumerable case
Algorithmic tests and randomness with respect to a class of measures
Uniform test of algorithmic randomness over a general space
Sequential predictions based on algorithmic complexity
Finite state incompressible infinite sequences
Initial segment complexities of randomness notions
An almost machine-independent theory of program-length complexity, sophistication, and induction
The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite
A note on Blum static complexity measures
Multiple usage of random bits in finite automata
Relative to a random oracle, P/poly is not measurable in EXP
HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
Quantitative aspects of speed-up and gap phenomena
Increasing the gap between descriptional complexity and algorithmic probability
Partial Randomness and Dimension of Recursively Enumerable Reals
Algorithmic information theory and its statistical mechanical interpretation
Calibrating Randomness
Degrees of monotone complexity
Universal Recursively Enumerable Sets of Strings
Schnorr trivial sets and truth-table reducibility
Recognizing strong random reals
Sequential mappings of \omega -languages
Generalized kolmogorov complexity and other dual complexity measures
Kolmogorov and mathematical logic
Strict process machine complexity
General random sequences and learnable sequences
scientific article; zbMATH DE number 3591877 (Why is no real title available?)
scientific article; zbMATH DE number 3605746 (Why is no real title available?)
A test for randomness based on a complexity measure
scientific article; zbMATH DE number 558650 (Why is no real title available?)
Algorithmic complexity of points in dynamical systems
A linearly computable measure of string complexity
Computational depth and reducibility
Relations between varieties of kolmogorov complexities
Schnorr randomness
Solovay functions and their applications in algorithmic randomness
Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs
Equivalence of measures of complexity classes
Effective category and measure in abstract complexity theory
On unstable and unoptimal prediction
Kolmogorov complexity in perspective. I: Information theory and randomness
Kobayashi compressibility
Schnorr randomness
Universal recursively enumerable sets of strings
Algorithmic randomness over general spaces
2005 Annual Meeting of the Association for Symbolic Logic
Program size complexity for possibly infinite computations
Random reals and possibly infinite computations Part I: Randomness in ∅′
Recursively enumerable reals and Chaitin \(\Omega\) numbers
Martingales in the Study of Randomness
Algorithmic randomness and monotone complexity on product space
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}\)
On natural representations of objects
Randomness and imprecision: from supermartingales to randomness tests
Process and truth-table characterisations of randomness
Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets
Comparing notions of randomness
Relativized Schnorr tests with universal behavior
On a definition of random sequences with respect to conditional probability

This page was built for publication: Process complexity and effective random tests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2264549)