Search

As we discuss, a stationary stochastic process is nonergodic when a random persistent topic can be detected in the infinite random text sampled from the process, whereas we call the process strongly nonergodic when an infinite sequence of independent random bits, called probabilistic facts, is needed to describe this topic completely. Replacing probabilistic facts with an algorithmically random sequence of bits, called algorithmic facts, we adapt this property back to ergodic processes. Subsequently, we call a process perigraphic if the number of algorithmic facts which can be inferred from a finite text sampled from the process grows like a power of the text length. We present a simple example of such a process. Moreover, we demonstrate an assertion which we call the theorem about facts and words. This proposition states that the number of probabilistic or algorithmic facts which can be inferred from a text drawn from a process must be roughly smaller than the number of distinct word-like strings detected in this text by means of the PPM compression algorithm. We also observe that the number of the word-like strings for a sample of plays by Shakespeare follows an empirical stepwise power law, in a stark contrast to Markov processes. Hence we suppose that natural language considered as a process is not only non-Markov but also perigraphic., Comment: 29 pages, 1 figure

Realization of modern telecommunication systems is inconceivable without use of different binary sequences. In this paper, an overview of random binary sequences used in different telecommunication systems is given. Basic principles of pseudorandom, chaotic, and true random sequence generation are presented, as well as their application in telecommunications in respect to advantages and drawbacks of the same. Moreover, particular scheme for true random binary sequence generation is given, as well as results of randomness assessment obtained by NIST statistical test suite. Finally, short insight into importance of random binary sequence in secure communications is given.

Given the widespread use of lossless compression algorithms to approximate algorithmic (Kolmogorov-Chaitin) complexity, and that lossless compression algorithms fall short at characterizing patterns other than statistical ones not different to entropy estimations, here we explore an alternative and complementary approach. We study formal properties of a Levin-inspired measure $m$ calculated from the output distribution of small Turing machines. We introduce and justify finite approximations $m_k$ that have been used in some applications as an alternative to lossless compression algorithms for approximating algorithmic (Kolmogorov-Chaitin) complexity. We provide proofs of the relevant properties of both $m$ and $m_k$ and compare them to Levin's Universal Distribution. We provide error estimations of $m_k$ with respect to $m$. Finally, we present an application to integer sequences from the Online Encyclopedia of Integer Sequences which suggests that our AP-based measures may characterize non-statistical patterns, and we report interesting correlations with textual, function and program description lengths of the said sequences., Comment: As accepted by the journal Complexity (Wiley/Hindawi)

Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice because Kolmogorov complexity is not computable.

The randomness rate of an infinite binary sequence is characterized by the sequence of ratios between the Kolmogorov complexity and the length of the initial segments of the sequence. It is known that there is no effective procedure that transforms one input sequence into another sequence with higher randomness rate. By contrast, we display such a uniform effective procedure having as input two independent sequences with positive but arbitrarily small constant randomness rate. Moreover the transformation is a truth-table reduction and the output has randomness rate arbitrarily close to 1.

Consider a universal oracle Turing machine that prints a finite or an infinite binary sequence, based on the answers to the binary queries that it makes during the computation. We study the probability that this output is infinite and computable when the machine is given a random (in the probabilistic sense) stream of bits as the answers to its queries during an infinitary computation. Surprisingly, we find that these probabilities are the entire class of real numbers in (0,1) that can be written as the difference of two halting probabilities relative to the halting problem. In particular, there are universal Turing machines that produce a computable infinite output with probability exactly 1/2. Our results contrast a large array of facts (the most well-known being the randomness of Chaitin’s halting probability) that witness maximal initial segment complexity of probabilities associated with universal machines. Our proof uses recent advances in algorithmic randomness.

We present an axiomatic approach that introduces algorithmic randomness into various classes of structures. The central concept is the notion of a branching class. Through this technical yet simple notion we define measure, metric, and topology in many classes of graphs, trees, relational structures, and algebras. As a consequence we define algorithmically random structures. We prove the existence of algorithmically random structures with various computability-theoretic properties. We show that any nontrivial variety of algebras has an effective measure 0. We also prove a counter-intuitive result that there are algorithmically random yet computable structures. This establishes a connection between algorithmic randomness and computable model theory.

An infinite binary sequence X is Kolmogorov–Loveland (or KL-) random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X . A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence. One of the major open problems in the field of effective randomness is whether Martin-Lof randomness is the same as KL-randomness. Our first main result states that KL-random sequences are close to Martin-Lof random sequences in so far as every KL-random sequence has arbitrarily dense subsequences that are Martin-Lof random. A key lemma in the proof of this result is that for every effective split of a KL-random sequence at least one of the halves is Martin-Lof random. However, this splitting property does not characterize KL-randomness; we construct a sequence that is not even computably random such that every effective split yields two subsequences that are 2-random. Furthermore, we show for any KL-random sequence A that is computable in the halting problem that, first, for any effective split of A both halves are Martin-Lof random and, second, for any computable, nondecreasing, and unbounded function g and almost all n , the prefix of A of length n has prefix-free Kolmogorov complexity at least n − g ( n ) . Again, the latter property does not characterize KL-randomness, even when restricted to left-r.e. sequences; we construct a left-r.e. sequence that has this property but is not KL-stochastic and, in fact, is not even Mises–Wald–Church stochastic. Turning our attention to KL-stochasticity, we construct a non-empty Π 1 0 class of KL-stochastic sequences that are not weakly 1-random; by the usual basis theorems we obtain such sequences that in addition are left-r.e., are low, or are of hyperimmune-free degree. Our second main result asserts that every KL-stochastic sequence has effective dimension 1, or equivalently, a sequence cannot be KL-stochastic if it has infinitely many prefixes that can be compressed by a factor of α 1 . This improves on a result by Muchnik, who has shown that were they to exist, such compressible prefixes could not be found effectively.

This work is a survey about the definition of “random sequence”. We emphasize the definition of Martin-Löf and the definition based on incompressibility (Kolmogorov complexity). Kolmogorov complexity is a profound and sofisticated theory of information and randomness based on Turing machines. These two definitions solve all the problems of the other approaches, satisfying our intuitive concept of randomness, and both are mathematically correct. Furthermore, we show the Schnorr’s approach, that includes a requisite of effectiveness (computability) in his definition. We show the relations between all definitions in a critical way. Keywords: randomness, Kolmogorov complexity, Turing machine, computability, probability., Este trabalho apresenta uma revisão bibliográfica sobre a definição de “seqüência aleatória”. Nós enfatizamos a definição de Martin-Löf e a definição baseada em incompressividade (complexidade de Kolmogorov). Complexidade de Kolmogorov é uma teoria sofisticada e profunda da informação e da aleatoriedade baseada na máquina de Turing. Estas duas definições resolvem todos os problemas das outras abordagens e satisfazem o nosso conceito intuitivo de aleatoriedade, sendo matematicamente corretas. Adicionalmente, apresentamos a abordagem de Schnorr que inclui um requisito de efetividade (computabilidade) em sua definição. São apresentadas as relações entre estas diversas definições de forma crítica. Palavras-chave: aleatoriedade, complexidade de Kolmogorov, máquina de Turing, computabilidade, probabilidade.

We study reals with infinitely many incompressible prefixes. Call A ∈ 2ωKolmogorov random if . where C denotes plain Kolmogorov complexity. This property was suggested by Loveland and studied by Martin-Löf. Schnorr and Solovay. We prove that 2-random reals are Kolmogorov random. Together with the converse—proved by Nies. Stephan and Terwijn [11]—this provides a natural characterization of 2-randomness in terms of plain complexity. We finish with a related characterization of 2-randomness.

According to a traditional view, scientific laws and theories constitute algorithmic compressions of empirical data sets collected from observations and measurements. This article defends the thesis that, to the contrary, empirical data sets are algorithmically incompressible. The reason is that individual data points are determined partly by perturbations, or causal factors that cannot be reduced to any pattern. If empirical data sets are incompressible, then they exhibit maximal algorithmic complexity, maximal entropy and zero redundancy. They are therefore maximally efficient carriers of information about the world. Since, on algorithmic information theory, a string is algorithmically random just if it is incompressible, the thesis entails that empirical data sets consist of algorithmically random strings of digits. Rather than constituting compressions of empirical data, scientific laws and theories pick out patterns that data sets exhibit with a certain noise.

Let ω be a Kolmogorov–Chaitin random sequence with ω1:n denoting the first n digits of ω. Let P be a recursive predicate defined on all finite binary strings such that the Lebesgue measure of the set {ω|∃nP(ω1:n)} is a computable real α. Roughly, P holds with computable probability for a random infinite sequence. Then there is an algorithm which on input indices for any such P and α finds an n such that P holds within the first n digits of ω or not in ω at all. We apply the result to the halting probability Ω and show that various generalizations of the result fail.

A given finite sequence of letters over a finite alphabet can always be algorithmically generated, in particular by a Turing machine. This fact is at the heart of complexity theory in the sense of Kolmogorov and Chaitin. A relevant question in this context is whether, given a statistically ‘sufficiently long’ sequence, there exists a deterministic finite automaton that generates it. In this paper we propose a simple criterion, based on measuring block entropies by lumping, which is satisfied by all automatic sequences. On the basis of this, one can determine that a given sequence is not automatic and obtain interesting information when the sequence is automatic. Following previous work on the Feigenbaum sequence, we give a necessary entropy-based condition valid for all automatic sequences read by lumping. Applications of these ideas to representative examples are discussed. In particular, we establish new entropic decimation schemes for the Thue–Morse, the Rudin–Shapiro and the paperfolding sequences read by lumping.

Random sequences are usually defined with respect to a probability distribution~$\bf P$ (a $\sigma$-additive set function, normed to one, defined over a $\sigma$-algebra) assuming Kolmogorov's axioms for probability theory. In this paper, without using this axiomatics, we give a definition of random (typical) sequences taking as primitive the notion of a martingale and using the principle of the excluded gambling strategy. In this purely game-theoretic framework, no probability distribution or, partially or fully specified, system of conditional probability distributions needs to be introduced. For these typical sequences, we prove direct algorithmic versions of Kolmogorov's strong law of large numbers (SLLN) and of the upper half of Kolmogorov's law of the iterated logarithm~(LIL).

In the framework of the Kolmogorov approach to verifying the theory of probability an analysis of a result of S. S. Samarova on the length of the longest head-run for the Markov chain with two states is given. This result is a refinement and generalization of P. Erdos and P.~Revesz's corresponding results. An analogous assertion is formulated and proved for individual random sequences. A complexity characterization of its application is also given.

In a recent paper (Merhav and Weinberger, IEEE Trans. Inf. Theory, vol.50, no.1, p.5-20, 2004) we studied the problem of universal simulation of an unknown information source of a certain parametric family, given a training sequence from that source and given a limited budget of purely random bits. The goal was to generate another random sequence (of the same length or shorter), whose probability law is identical to that of the given training sequence, but with minimum statistical dependency (minimum mutual information) between the input training sequence and the output sequence. In this addendum, we point out a concrete optimal simulation scheme that is easy to implement, as opposed to the nonconstructive existence result in that paper, and we make a number of additional observations on the universal simulation problem.

In this paper, by means of the notion of likelihood ratio and by using an analytical technique for the investigation of a.e. convergence presented, an extension of a theorem on the gambling system to arbitrary binary random sequences is obtained.

It is well-known that a rigorous operational definition of randomness is very hard to formulate in terms of classical mathematical primitives. This difficulty is reflected in the difficulty of deciding whether a given (pseudo-)random number sequence is “sufficiently random”. Intuitively, we want the sequence to possess all the properties that a truly random sequence would have, where these properties are well-defined but uncountably infinite in number. This kind of reasoning invariably leads to an infinite number of conditions which must be satisfied, and which in addition are not independent. A more appealing way to approach the problem is through the concepts of chaos and fractals. Certainly a sequence of random numbers is the ultimate self-similar set, since it is (statistically) self-similar at all scales and in all permutations. The idea of applying chaos theory to randomness is not new, but as far as I know, it has only recently given rise to demonstrably “good” random number generators of practical usefulness in massive Monte Carlo calculations. The best of these is probably the algorithm of Martin Luscher which will be described in some detail.

We are faced with the task of storing and communicating increasingly huge amounts of information. The development of digital storage media and communication channels have not been able to keep up with this increasing demand in an economically viable way. Data compression is fast emerging as the key technique in resolving this technological issue. Kolmogorov complexity is the central tool used in this analysis. Informally the Kolmogorov complexity of an object is the length of the shortest string from which the original can be reconstructed lossless by a general-purpose computer. Thus the Kolmogorov complexity of an object measures the maximum amount of compression that any lossless compression program can achieve in theory. The main issue in translating theory to application is the fact that Kolmogorov complexity is non-computable. This means that no computer program can compute precisely the Kolmogorov complexity of a given string. Fortunately Kolmogorov complexity can be approximated by a computer, and this has been used as the standard method of implementing classification techniques.

The Random Oracle model popularized by Bellare and Rogaway in 1993 has proven to be hugely successful, allowing cryptographers to give security proofs for very efficient and practical schemes. In this paper, we discuss the possibility of using an incompressible but fixed, "algorithmically random" oracle instead of the standard random oracle and show that this approach allows for rather similar results to be proven but in a completely different way. We also show that anything provably secure in the standard random oracle model is also secure with respect to any algorithmically random oracle and then discuss the implications.

We describe an alternative method (to compression) that combines several theoretical and experimental results to numerically approximate the algorithmic (Kolmogorov-Chaitin) complexity of all $\sum_{n=1}^82^n$ bit strings up to 8 bits long, and for some between 9 and 16 bits long. This is done by an exhaustive execution of all deterministic 2-symbol Turing machines with up to 4 states for which the halting times are known thanks to the Busy Beaver problem, that is 11019960576 machines. An output frequency distribution is then computed, from which the algorithmic probability is calculated and the algorithmic complexity evaluated by way of the (Levin-Zvonkin-Chaitin) coding theorem., 29 pages, 5 figures. Version as accepted by the journal Applied Mathematics and Computation

Every class C of languages satisfying a simple topological condition is shown to have probability one if and only if it contains some language that is algorithmically random in the sense of Martin-Lof. This result is used to derive separation properties of algorithmically random oracles and to give characterizations of the complexity classesP, BPP, AM, andPH in terms of reducibility to such oracles. These characterizations lead to results like:P =NP if and only if an algorithmically random set exists that is ≤ P -hard forNP.

In 1975 Chaitin introduced his Ω number as a concrete example of random real. The real Ω is defined based on the set of all halting inputs for an optimal prefix-free machine U, which is a universal decoding algorithm used to define the notion of program-size complexity. Chaitin showed Ω to be random by discovering the property that the first n bits of the base-two expansion of Ω solve the halting problem of U for all binary inputs of length at most n. In this paper, we introduce a new representation Θ of Chaitin Ω number. The real Θ is defined based on the set of all compressible strings. We investigate the properties of Θ and show that Θ is random. In addition, we generalize Θ to two directions Θ(T) and Θ(T) with a real T > 0. We then study their properties. In particular, we show that the computability of the real Θ(T) gives a sufficient condition for a real T ∈ (0, 1) to be a fixed point on partial randomness, i.e., to satisfy the condition that the compression rate of T equals to T.

We call a group $G$ {\it algorithmically finite} if no algorithm can produce an infinite set of pairwise distinct elements of $G$. We construct examples of recursively presented infinite algorithmically finite groups and study their properties. For instance, we show that the Equality Problem is decidable in our groups only on strongly (exponentially) negligible sets of inputs.

Chaitin [G. J. Chaitin, J. Assoc. Comput. Mach. , vol. 22, pp. 329---340, 1975] introduced his Ω number as a concrete example of random real. The real Ω is defined as the probability that an optimal computer halts, where the optimal computer is a universal decoding algorithm used to define the notion of program-size complexity. Chaitin showed Ω to be random by discovering the property that the first n bits of the base-two expansion of Ω solve the halting problem of the optimal computer for all binary inputs of length at most n . In the present paper we investigate this property from various aspects. It is known that the base-two expansion of Ω and the halting problem are Turing equivalent. We consider elaborations of both the Turing reductions which constitute the Turing equivalence. These elaborations can be seen as a variant of the weak truth-table reduction, where a computable bound on the use function is explicitly specified. We thus consider the relative computational power between the base-two expansion of Ω and the halting problem by imposing the restriction to finite size on both the problems.

In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received most attention are perhaps Martin-Loef randomness and computable randomness. The latter notion was introduced by Schnorr and is rather natural: an infinite binary sequence is computably random if no total computable strategy succeeds on it by betting on bits in order. However, computably random sequences can have properties that one may consider to be incompatible with being random, in particular, there are computably random sequences that are highly compressible. The concept of Martin-Loef randomness is much better behaved in this and other respects, on the other hand its definition in terms of martingales is considerably less natural. Muchnik, elaborating on ideas of Kolmogorov and Loveland, refined Schnorr's model by also allowing non-monotonic strategies, i.e. strategies that do not bet on bits in order. The subsequent ``non-monotonic'' notion of randomness, now called Kolmogorov-Loveland randomness, has been shown to be quite close to Martin-Loef randomness, but whether these two classes coincide remains a fundamental open question. As suggested by Miller and Nies, we study in this paper weak versions of Kolmogorov-Loveland randomness, where the betting strategies are non-adaptive (i.e., the positions of the bits to bet on should be decided before the game). We obtain a full classification of the different notions we consider., Comment: A preliminary version of this paper was presented at the Sixth International Conference on Computability and Complexity in Analysis, August 18-22, 2009, Ljubljana, Slovenia

How to estimate the randomness in random sequence generation tasks? The aim of the paper was to discuss the accuracy of the multiple indexes used for random sequences generation results calculation. In the first part of the paper the models explaining deviations from randomness were presented. The key role of the structural limitations interpretation was suggested. Secondly, the multiple indexes of the deviation from randomness used in random sequence generation task studies were presented. The authors concluded that too many indexes are used in the studies of deviation from randomness. In order to avoid such problems two indexes were proposed: entropy and correlation function. The last part of the paper presents the preliminary version of the mathematical of random sequences generation in which the limited capacity of the short-term memory assumption was introduce.

CONTENTS Introduction Chapter I. The main notions and facts § 1.1. The notion of randomness depends on a given probability distribution § 1.2. Three faces of randomness: stochasticness, chaoticness, typicalness § 1.3. Typical, chaotic and stochastic sequences: ways to a mathematical definition 1.3.1. Typicalness 1.3.2. Chaoticness 1.3.3. Stochasticness 1.3.4. Comments § 1.4. Typical and chaotic sequences: basic definitions (for the case of the uniform Bernoulli distribution) 1.4.1. Typicalness 1.4.2. Chaoticness Chapter II. Effectively null sets, constructive support, and typical sequences § 2.1. Effectively null sets, computable distributions, and the statement of Martin-Lof's theorem § 2.2. Proof of Martin-Lof's theorem § 2.3. Different versions of the definition of the notion of typicalness 2.3.1. Schorr's definition of typicalness 2.3.2. Solovay's criterion for typicalness 2.3.3. The axiomatic approach to the definition of typicalness Chapter III. Complexity, entropy, and chaotic sequences § 3.1. Computable mappings § 3.2. Kolmogorov's theorem. Monotone entropy § 3.3. Chaotic sequences Chapter IV. What is a random sequence? § 4.1. The proof of the Levin-Schorr theorem for the uniform Bernoulli distribution § 4.2. The case of an arbitrary probability distribution § 4.3. The proofs of the lemmas Chapter V. Probabilistic machines, a priori probability, and randomness § 5.1. Probabilistic machines § 5.2. A priori probability § 5.3. A priori probability and entropy § 5.4. A priori probability and randomness Chapter VI. The frequency approach to the definition of a random sequence § 6.1. Von Mises' approach. The Church and Kolmogorov-Loveland definitions § 6.2. Relations between different definitions. Ville's construction. Muchnik's theorem. Lambalgen's example 6.2.1. Relations between different definitions 6.2.2. Ville's example 6.2.3. Muchnik's theorem 6.2.4. Lambalgen's example § 6.3. A game-theoretic criterion for typicalness Addendum. A timid criticism regarding probability theory References

The problem of characterizing the randomness of finite sequences arises in cryptographic applications. The idea of randomness clearly reflects the difficulty of predicting the next digit of a sequence from all the previous ones. The approach taken in this paper is to measure the (linear) unpredictability of a sequence (finite or periodic) by the length of the shortest linear feedback shift register (LFSR) that is able to generate the given sequence. This length is often referred to in the literature as the linear complexity of the sequence. It is shown that the expected linear complexity of a sequence of n independent and uniformly distributed binary random variables is very close to n/2 and, that the variance of the linear complexity is virtually independent of the sequence length, i.e. is virtually a constant! For the practically interesting case of periodically repeating a finite truly random sequence of length 2m or 2m-1, it is shown that the linear complexity is close to the period length.

The finite sequences the algorithmic complexities of which, with respect to a universal Turing machine, do not differ substantially from their corresponding lengths are known to be good simulations of statistically independent random samples from the equiprobable distribution. The aim of this paper is to suggest a possibility how to define, using the apparatus of algorithmic complexity, pseudo-random independent and equally distributed samples from a general probability distribution over a finite set and pseudo-Markov samples with a finite set of possible states.

We extend the recurrence time theorem, which is originally derived by Wyner and Ziv, to individual Martin-Lof random sequences. We also present a simple, alternative proof of the algorithmic Shannon-McMillan-Breiman theorem that was first proved by V'yugin.

This chapter focuses on randomness—the most important aspect of password security. Randomness is a strange concept. It is the absence of order. The lack of order, however, does not guarantee that something is random. A sequence is only random if there is no way it can be reproduced given any circumstances or information. Three properties of a sequence attribute to its randomness. These properties include (1) even distribution—an equal probability of distribution over the entire set of data; (2) unpredictability—any one piece of data has no relationship to any previous data and provides no information about the data to follow; and (3) uniqueness. It would be extremely rare to randomly produce the same sequence of data more than once. The longer the sequence, the more unique it becomes. These three properties deem random data impossible to guess, therefore making randomness a vital element for strong passwords. Humans are poor sources of randomness, but with a little help and some simple strategies, very strong passwords may be created. Computers have their own problems when it comes to creating randomness. Computer needs precise instructions for creating a random sequence. Computers use a Pseudo Random Number Generator (PRNG) for producing a random character. Pseudo random numbers are not truly random, but rather an algorithm that creates numbers that appear to be random. These numbers are actually predictable.

This paper describes the asymptotic behavior of normalized linear complexity of ultimately nonperiodic binary sequence. The linear complexity of s/sup n/, L/sub s/(n), is defined as the length of the shortest linear feedback shift register which generates s/sup n/. The research method and results studied in this paper seem to be very useful in characterizing the purely random sequence and distinguishing a key stream generator from a uniformly random sequence.

The resource-bounded measure (J. Lutz, 1992) is an extension of classical measure theory which provides a probabilistic means of describing the relative sizes of complexity classes. Lutz proposed the hypothesis that NP does not have measure zero in the class E/sub 2/=DTIME(2/sup polynomial/), meaning loosely that NP contains a non-negligible subset of exponential time. This hypothesis implies a strong separation of P from NP and is supported by a growing body of plausible consequences which are not known to follow from the weaker assertion P/spl ne/NP. It is shown that relative to a random oracle, NP does not have measure zero in E/sub 2/, improving the result of Bennett and Gill (1981) that P/spl ne/NP relative to a random oracle. Several new techniques are introduced; in particular the proof exploits the independence properties of algorithmically random sequences, and a strong independence result is shown: if A is an algorithmically random sequence and a subsequence A/sub 0/ is chosen by means of a bounded Kolmogorov-Loveland place selection, then the sequence A/sub 1/ of unselected bits is random relative to A/sub 0/, i.e. A/sub 0/ and A/sub 1/ are independent. A bounded Kolmogorov-Loveland place selection is a very general type of recursive selection rule which may be interpreted as the sequence of oracle queries of a time-bounded Turing machine, so the methods used may be applicable to other questions involving random oracles. >

The authors investigate combinatorial properties of finite sequences with high Kolmogorov complexity. They also demonstrate the utility of a Kolmogorov complexity method in combinatorial theory by several examples (such as the coin-weighing problem). >

We generalize the concept of randomness in an infinite binary sequence in order to characterize the degree of randomness by a real number D>0. Chaitin's halting probability \Omega is generalized to \Omega^D whose degree of randomness is precisely D. On the basis of this generalization, we consider the degree of randomness of each point in Euclidean space through its base-two expansion. It is then shown that the maximum value of such a degree of randomness provides the Hausdorff dimension of a self-similar set that is computable in a certain sense. The class of such self-similar sets includes familiar fractal sets such as the Cantor set, von Koch curve, and Sierpinski gasket. Knowledge of the property of \Omega^D allows us to show that the self-similar subset of [0,1] defined by the halting set of a universal algorithm has a Hausdorff dimension of one., Comment: 29 pages, LaTeX2e, AMSLaTeX1.2, \usepackage{a4wide}, no figures

A Chaitin Omega number is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Omega number is both computably enumerable (the limit of a computable, increasing, converging sequence of rationals) and random (its binary expansion is an algorithmic random sequence). In particular, every Omega number is strongly non-computable. The aim of this paper is to describe a procedure, which combines Java programming and mathematical proofs, for computing the exact values of the first 64 bits of a Chaitin Omega: 0000001000000100000110001000011010001111110010111011101000010000. Full description of programs and proofs will be given elsewhere., 16 pages; Experimental Mathematics (accepted)

Algorithmic information content is an important fundamental idea for dealing with systems that contain or in the course of time produce large amounts of information. This notion provides a rigorous meaning to the intuitive concept of randomness, and thereby plays an important role in formal mathematics as well as in theoretical computer science. More importantly for applications, however, this idea has succeeded in providing a quantitatively precise way of characterizing the output of a deterministic dynamical system as random, or equivalently, algorithmically complex. This presentation will provide an introduction to the basic ideas of algorithmic complexity and randomness, as well to the applications of these ideas to the characterization of dynamical systems as examples of complex behavior.

This paper presents some results about transformations of infinite random sequences by letter to letter rational transducers. We show that it is possible by observing initial segments of a given random sequence to decide whether two given letter to letter rational transducers have the same output on that sequence. We use the characterization of random sequences by Kolmogorov Complexity. We also prove that the image of a random sequence is either random, or non-random and non-recursive, or periodic, depending on some transducer's structural properties that we give.

Many neural net learning algorithms aim at finding "simple" nets to explain training data. The expectation is that the "simpler" the networks, the better the generalization on test data (--> Occam's razor). Previous implementations, however, use measures for "simplicity" that lack the power, universality and elegance of those based on Kolmogorov complexity and Solomonoff's algorithmic probability. Likewise, most previous approaches (especially those of the "Bayesian" kind) suffer from the problem of choosing appropriate priors. This paper addresses both issues. It first reviews some basic concepts of algorithmic complexity theory relevant to machine learing, and how the Solomonoff-Levin distribution (or universal prior) deals with the prior problem. The universal prior leads to a probabilistic method for finding "algorithmically simple" problem solutions with high generalization capability. The method is based on Levin complexity (a time-bounded generalization of Kolmogorov complexity) and inspired by Levin's optimal universal search algorithm. For a given problem, solution candidates are computed by efficient "self-sizing" programs that influence their own runtime and storage size. The probabilistic search algorithm finds the "good" programs (the ones quickly computing algorithmically probable solutions fitting the training data). Simulations focus on the task of discovering "algorithmically simple" neural networks with low Kolmogorov complexity and high generalization capability. It is demonstrated that the method, at least with certain toy problems where it is computationally feasible, can lead to generalization results unmatchable by previous neural network algorithms. Much remains to be done, however, to make large scale applications and "incremental learning" feasible. Copyright 1997 Elsevier Science Ltd.

Many machine learning algorithms aim at finding “simple” rules to explain training data. The expectation is: the “simpler” the rules, the better the generalization on test data (→ Occam's razor). Most practical implementations, however, use measures for “simplicity” that lack the power, universality and elegance of those based on Kolmogorov complexity and Solomonoff's algorithmic probability. Likewise, most previous approaches (especially those of the “Bayesian” kind) suffer from the problem of choosing appropriate priors. This paper addresses both issues. It first reviews some basic concepts of algorithmic complexity theory relevant to machine learning, and how the Solomonoff-Levin distribution (or universal prior) deals with the prior problem. The universal prior leads to a probabilistic method for finding “algorithmically simple” problem solutions with high generalization capability. The method is based on Levin complexity (a time-bounded extension of Kolmogorov complexity) and inspired by Levin's optimal universal search algorithm. With a given problem, solution candidates are computed by efficient “self-sizing” programs that influence their own runtime and storage size. The probabilistic search algorithm finds the “good” programs (the ones quickly computing algorithmically probable solutions fitting the training data). Experiments focus on the task of discovering “algorithmically simple” neural networks with low Kolmogorov complexity and high generalization capability. These experiments demonstrate that the method, at least with certain toy problems where it is computationally feasible, can lead to generalization results unmatchable by previous neural net algorithms.

Every class C of languages satisfying a simple topological condition is shown to have probability one if and only if it contains some language that is algorithmically random in the sense of Martin-Lof. This result is used to derive separation properties of algorithmically random oracles and to give characterizations of the complexity classes P, BPP, AM, and PH in terms of reducibility to such oracles. These characterizations lead to the following result: (i) P = NP if and only if there exists an algorithmically random set that is ≤ btt P -hard for NP. (ii) P = PSPACE if and only if there exists an algorithmically random set that is ≤ btt P -hard for PSPACE. (iii) The polynomial-time hierarchy collapses if and only if there exists k>0 such that some algorithmically random set is σ k P -hard for PH. (iv) PH = PSPACE if and only if there exists a algorithmically random set that is PH-hard for PSPACE.

A new definition of program-size complexity is made. H(A,B/C,D) is defined to be the size in bits of the shortest self-delimiting program for calculating strings A and B if one is given a minimal-size self-delimiting program for calculating strings C and D. This differs from previous definitions: (1) programs are required to be self-delimiting, i.e. no program is a prefix of another, and (2) instead of being given C and D directly, one is given a program for calculating them that is minimal in size. Unlike previous definitions, this one has precisely the formal properties of the entropy concept of information theory. For example, H(A,B) = H(A) + H(B/A) -~ 0(1). Also, if a program of length k is assigned measure 2 -k, then H(A) = -log2 (the probability that the standard universal computer will calculate A) -{- 0(1).