Non-algorithmic theory of randomness

This paper covers two topics: first an introduction to Algorithmic Complexity Theory: how it defines probability, some of its characteristic properties and past successful applications. Second, we apply it to problems in A.I. - where it promises to give near optimum search procedures for two very broad classes of problems.

In the book we present main concepts of probabilistic automata theory.

This work starts from definition of randomness, the results of algorithmic randomness are analyzed from the perspective of application. Then, the source and nature of randomness is explored, and the relationship between infinity and randomness is found. The properties of randomness are summarized from the perspective of interaction between systems, that is, the set composed of sequences generated by randomness has the property of asymptotic completeness. Finally, the importan...

We study the logic obtained by endowing the language of first-order arithmetic with second-order measure quantifiers. This new kind of quantification allows us to express that the argument formula is true in a certain portion of all possible interpretations of the quantified variable. We show that first-order arithmetic with measure quantifiers is capable of formalizing simple results from probability theory and, most importantly, of representing every recursive random functi...

The notion of probability plays a crucial role in quantum mechanics. It appears in quantum mechanics as the Born rule. In modern mathematics which describes quantum mechanics, however, probability theory means nothing other than measure theory, and therefore any operational characterization of the notion of probability is still missing in quantum mechanics. In this paper, based on the toolkit of algorithmic randomness, we present a refinement of the Born rule, as an alternati...

We survey recent developments in the study of probabilistic complexity classes. While the evidence seems to support the conjecture that probabilism can be deterministically simulated with relatively low overhead, i.e., that $P=BPP$, it also indicates that this may be a difficult question to resolve. In fact, proving that probabilistic algorithms have non-trivial deterministic simulations is basically equivalent to proving circuit lower bounds, either in the algebraic or Boole...

This is a survey of constructive and computable measure theory with an emphasis on the close connections with algorithmic randomness. We give a brief history of constructive measure theory from Brouwer to the present, emphasizing how Schnorr randomness is the randomness notion implicit in the work of Brouwer, Bishop, Demuth, and others. We survey a number of recent results showing that classical almost everywhere convergence theorems can be used to characterize many of the co...

We address the problem of detecting deviations of binary sequence from randomness,which is very important for random number (RNG) and pseudorandom number generators (PRNG). Namely, we consider a null hypothesis $H_0$ that a given bit sequence is generated by Bernoulli source with equal probabilities of 0 and 1 and the alternative hypothesis $H_1$ that the sequence is generated by a stationary and ergodic source which differs from the source under $H_0$. We show that data comp...

This progress report covers recent developments in the area of quantum randomness, which is an extraordinarily interdisciplinary area that belongs not only to physics, but also to philosophy, mathematics, computer science, and technology. For this reason the article contains three parts that will be essentially devoted to different aspects of quantum randomness, and even directed, although not restricted, to various audiences: a philosophical part, a physical part, and a tech...

Algorithmic theories of randomness can be related to theories of probabilistic sequence prediction through the notion of a predictor, defined as a function which supplies lower bounds on initial-segment probabilities of infinite sequences. An infinite binary sequence $z$ is called unpredictable iff its initial-segment "redundancy" $n+\log p(z(n))$ remains sufficiently low relative to every effective predictor $p$. A predictor which maximizes the initial-segment redundancy of ...