What Is a Random String?
Cristian Calude
Computer Science Department
The University of Auckland, New Zealand
email: cristian@cs.auckland.ac.nz
Abstract:
Chaitin's algorithmic definition of random strings  based
on the complexity induced by selfdelimiting computers  is critically discussed.
One shows that Chaitin's model
satisfy many natural
requirements related to randomness, so it can be considered as an
adequate model for finite random objects. It is a better model
than the original (Kolmogorov) proposal. Finally, some open problems
will be discussed. Keywords:
Blankendmarker complexity, Chaitin (selfdelimiting) complexity, random strings. Category:
G.3
1 Motivation
Suppose that persons and give us a sequence of 32 bits each,
saying that they were obtained from independent coin flips. If gives the string and gives the string then we would tend to believe and would not believe : the string seems to be random,
but the string does not. Further on, if we change the value of a bit (say, from 1 to 0) in
a (non) ´random´ string, then the result is still a (non) ´random´ string.
If we keep making such changes in a ´random´ string, then we
will eventually complete distroy randomness. Laplace[21], pp.1617 was, in a sense, aware of the above paradox,
as it may be clear from the following phrase: In the game of heads and tails, if head comes up a hundred times in a row
then this appears to us extraordinary, because after dividing the nearly
infinite number of combinations that can arise in a hundred throws into regular
sequences, or those in which we observe a rule that is easy to grasp, and into
irregular sequences, the latter are incomparably more numerous. Page 48
In other words: non random strings are strings possessing some kind
of regularity, and since the number of all those strings (of a given length)
is small, the occurrence of such a string is extraordinary. Furthermore, regularity is a good basis for compression. Accordingly,
randomness means the absence of any compression possibility; it corresponds
to maximum information content (because after dropping any part of the
string, there remains no possibility of recovering it). As we shall prove
in Section 5, most strings have this property. In opposition, most strings we deal
with do not.
The information content of a phrase in a natural language (English, for example)
can be recovered even some letters (words) are
omitted.
The reason comes
from the redundancy of most spoken languages. As a consequence, there exist
many efficient programs to compress texts written in natural languages. It is
important to emphasize that all these methods work very well on texts written
in some natural language, but they do
not work well on average, i.e.
on all possible combinations of letters of the same length. Redundancy
is also a very powerful handle
to readers of mathematical books (and, in general, of scientific literature),
and also to
cryptanalysts (for example, Caesar's
ciphersjust permutations of letterscan be broken by frequency analysis;
see more on this topic in Salomaa [27]). A hypothetical language
in which there are only strings with maximum information content gives no
preference to strings (i.e. they have
equal frequency); this makes the cipher impossible
to break. However, such languages do not exist (and cannot be constructed,
even with the help of the best computers, available now and in the future);
redundancy is essential and inescapable in a spoken language (and to a large
extent in most artificial languages; see Marcus[25]). Before passing to some the formal treatment it is natural to ask the
following question: Are there any random strings? Of course, we do not
have yet the necessary tools to properly answer this question, but we may
try to approach it informally. Let us call canonical
program the smallest
program generating a string. We claim that every
canonical program should be random, independently if it generates or not a
random output. Indeed, assume that is a canonical program generating . If is not random, then there exists a program
generating which is substantially smaller than . Now, consider the program from calculate , then from calculate . This program is only a few letters longer than , and thus it should be
much shorter than , which was supposed to be canonical. We have reached
a contradiction. Borel [1][2] was the first author who systematically studied random
sequences. The complexitytheoretic approach was independently initiated
by Kolmogorov [22] and Chaitin [9]. For more historical facts see
Chaitin [17] (A Life in Math), Uspensky [31], Li and Vitanyi [23] and Calude [4].
2 Computers and Complexities
Denote by
the set of natural numbers;
.
If is a finite set, then denotes the cardinality
of . We shall use the following functions: i) , the
remainder of the integral division of by ,
ii), the integral part of the real , iii)
the base logarithm, . Page 49
Fix , a finite alphabet. By
we denote the free monoid generated by (under
concatenation). The elements of are called strings;
is the empty string.
For in , is the
length of .
For in , . For every and natural put , (n times); . Every total ordering on , say
, induces a quasilexicographical
order on .
We denote by string(n) the nth string in
according to the quasilexicographical order. The induced order on each set
coincides with the lexicographical order.
Working with partial recursive (p.r.) functions
(called sometime blankendmarker
computersee Chaitin [15])
we adopt the notations from Calude [3].
If , that is is in the domain
of , then we write .
A Chaitin computer
is a p.r. function with a
prefixfree domain (i.e. for every string , there is no
pair of distinct strings such that ,
and
is a prefix of ). To a Chaitin computer
one associates the selfdelimiting complexity or Chaitin complexity with the convention min ;
here ,
the operator min being taken according to the quasilexicographical order. The basic result obtained by Chaitin [9] (called the Invariance Theorem)
states the existence of a Chaitin computer
(called universal Chaitin computer) such that
for every Chaitin computer there exists a constant (depending
upon U and C) such that for all ( Exact values for all
additive constants discussed in this paper have been recently
computed by Chaitin [19]using a Lisp model of computation.) The complexity induced by a blankendmarker
computer is defined by .
A similar Invariance Theorem holds true for
blankendmarker computers.
See also Chaitin [9][10], Kolmogorov [22], MartinLöf [26],
Calude [3]. For this paper we fix a universal Chaitin computer U and denote by H
the induced complexity. Also, fix a universal blankendmarker computer
and denote by the induced complexity.
By we denote
the complexities , respectively.
Let be three functions. We write
in case there exists such that , for almost all strings
. We write in case and ;
means that there exists two positive reals such that and , for almost all strings .
3 Chaitin Random Strings
To motivate our approach we use
the analogy between ´tallness´ and ´randomness´. To
appreciate if a person is or is not tall we proceed as follows. We choose
a unity measure (say, centimetre) and we evaluate the height. We get an absolute Page 50
value. Next, we establish ´a set of people of reference´ .
For instance, if we have to appreciate how tall is a little girl
we fix
an age and we relate her height to the average height of girls of
that age. But, if we discuss the same question for a teenager, the
situation is completely different. It follows that the adjective tall is
relative. To correctly appreciate it we need both components: the exact
one (height) and the relative one (comparison within a fixed set). It
is fortunate that in English we have two words to express this:
height and tall. For randomness we proceed in a similar way, trying
to capture, as best as
possible, the idea that a string is random if it cannot be
algorithmically compressed. First we use a measure of complexity for
strings (H); this represents the ´absolute component´. Secondly,
we define randomness ´relative to a set´the relative component. In
our case we appreciate the degree of randomness of a string with
respect to the set of all strings, over a fixed
alphabet, having the same length.
(So, the ´context´ is determined
by the length and the size of the alphabet.) Of course, the success or failure of the approach depends upon the
measure of complexity we are adopting.
The use of selfdelimiting programs instead
of blankendmarker programs is motivated by Chaitin [16] as
follows: A key point that must be stipulated ... is that an input program must be
selfdelimited: its total length (in bits) must be given within the program
itself.
(This seemingly minor point, which paralyzed progress in the field for
nearly a decade, is what entailed the redefinition of algorithmic
randomness.) Real programming languages are selfdelimiting, because they
provide constructs for beginning and ending a program. Such constructs
allow a program to contain welldefined subprograms nested in them. Because
a selfdelimiting program is built up by concatenation and nesting
selfdelimiting subprograms, a program is syntactically complete only when
the last open subprogram is closed. In essence the beginning and ending
constructs for
programs and subprograms function respectively like left and right
parentheses in mathematical expressions. We first recall the asymptotical behaviour of the complexity H (see
Chaitin [12][14]): Theorem 3.1. Let f: be an injective, recursive function. a) One has: b) Consider a recursive function (Actually, this part is still true in case g is a function semicomputable in the limit from above.) Proof.
a) It is plain that: Page 51
b) i) Assume first that .
If there exists a natural N such that then we get a contradiction: In view of the hypothesis in b) ii),
there exists a natural N such that . We can use KraftChaitin Theorem in order
to construct a Chaitin computer with the following property: For every there
exists with and . So,
there exists a natural c such that for all , . Example 3.2. Example 3.3. i) Take . It is seen
that ,
so , for infinitely many . ii) For , one has: so . For , one has: Remark.
Chaitin complexity H can be characterized as a minimal
function, semicomputable in the limit from above,
that lies on the borderline between the convergence and the
divergence of the series . Put , where <,> : is a recursive bijection. The following three formulae come from Chaitin [12][13][14]: Lemma 3.4. There exists a natural such that for all string one has Page 52
We are in the position to evaluate the complexity of the most complex
strings of a given length (first obtained in Chaitin [12]). Theorem 3.5.
For every , one has: Proof. In view of Lemma 3.4, for every string x of length n, To get the relation we shall prove that for every string x of length n, Fix and define the Chaitin computer by Accordingly, and By Lemma ?? one has: so Accordingly, not all strings of length n have the complexity less than , i.e. The above discussion may be concluded with the following definition.
Let be the function defined by
In view of Theorem 3.5,. We define the random
strings of length n to be the strings with maximal selfdelimiting complexity among the strings of length n, i. e. the strings having . Page 53
Definition 3.6. A string is Chaitin mrandom
(m is a natural number) if ; is Chaitin random if it is 0random. The above definition depends upon the fixed universal computer U; the generality of the approach comes from the Invariance Theorem.
Obviously, for every length n and for every there exists a Chaitin mrandom string
of length n.
Denote by , , respectively, the sets of Chaitin mrandom strings and random strings. It is worth to note that the property of Chaitin mrandomness is asymptotic.
Indeed, for , the larger is the difference between and m, the more random is . There is no sharp
dividing line between randomness and pattern, but it looks as though all
with have a true random behaviour. How many strings have maximal complexity, i.e. ? The answer was given by Chaitin [18]: Theorem 3.7. There exists a natural constant (which depends upon the size of the underlying alphabet, ) such that for all natural n. How large is c? Out of strings of length n, at most
can be described by programs of
length less than nm. The ratio between and
is less than as , irrespective of the value of n.
For instance, this happens in case Q=2, m=20, i=6; it says that
less than one in a million among the binary strings of any given length
is not Chaitin 20random. So, in a strictly quantitative sense, almost all strings are Chaitin random. Problem. Denote by the sequence of constants appearing in Theorem 3.7. Is this sequence bounded? The rest of this paper will be devoted to the analysis of the adequacy of
Chaitin's definition of randomness.
4 A Statistical Analysis Random Strings
In this section we confront Chaitin's definition of randomness with the
probability point of view. As we have already said, the present proposal
identifies randomness with incompressibility. In order to
justify this option we have to show that the strings that are
incompressible justify the various properties of stochasticity
identified by the classical Probability Theory. It is not so difficult,
although tedious, to check separately such a single property.
However, we may proceed in a better way, due to the celebrated theory
developed by MartinLöf: We demonstrate that the incompressible
strings do possess all conceivable effectively testable properties of
stochasticity. Here we include the known properties, but also the
possible unknown ones. A general transfer principle will emerge,
by Page 54
virtue of which various results from classical probability
theory carry automatically for random strings. The ideas of MartinLöf theory are rooted in the statistical
practice. We are given an element x of some sample space (associated
to some distribution) and we want to test the hypothesis x
is a typical outcome. Being typical means ´belonging to every
reasonable majority´.
An element will be ´random´ just in case lies in the intersection of all such majorities. A level of a statistical test is a set of strings which are found relatively
nonrandom (by the test). Each level is a subset of the previous level,
containing less and less strings, considered more and more
nonrandom. The number of strings decreases exponentially fast at each
level. In the binary case, a test contains at level 0 all possible
strings, at level two only at most 1/2 of the strings, at level three only
1/4 of all strings, and so on; accordingly, at level m the test
contains at most strings of length n. We give now the formal definition. Definition 4.1. An r.e. set is called a
MartinLöf test if the following two properties hold true: By definition, the empty set is a MartinLöf test.
The set is called the
critical region at level .
(Getting an outcome string in means the rejection of the randomness hypothesis
for x.) A string x is declared ´random´ at level m by V
in case . The following example models the following simple idea: If a binary string x
has too many ones (zeros), then it cannot be random. Example 4.2. The set where is the number of occurrences of the letter in x, is a MartinLöf test. Proof. Clearly, V is r.e. and satisfies condition 1).
In view of the formula: one gets Page 55
Definition 4.3. To every MartinLöf test V we associate the critical level
, A string x is declared random by a MartinLöf test V if , for some , or, equivalently, if . Definition 4.4. A MartinLöf test is called
universal in case for every
MartinLöf test V,
there exists a constant c (depending upon and V) such that It is easy to see that a MartinLöf test is
universal iff for every MartinLöf
test V there exists a constant c (depending upon and V) such that Our aim is to prove that almost all Chaitin random strings pass all
conceivable effective tests of stochasticity, i.e. they are declared
random by every MartinLöf test. Theorem 4.5.
Fix . Almost all strings
in will be declared eventually random by every MartinLöf test. Proof. If K is the complexity induced by a fixed universal
blankendmarker computer, then by a result in Calude, Chitescu [7], the set is a universal MartinLöf of test. Every section is r.e.,
so when a string belongs to , then
we can eventually discover this.
Moreover, there are less than strings of length n having this property. Thus
if we are given and t we need to only know digits to
pick out any particular string with this property. I.e.,
as the first x that we discover has this property, the second x that
we discover has this property,...,the ith x that we discover has
this property, and . Accordingly, every string has the property that So, by Lemma 3.4: since in general Page 56
Finally, take , i.e. ,
and fix an arbitrary MartinLöf test V.
Take a natural T such that . It
follows that  otherwise we would have which means .
By virtue of the universality of we get a constant c such that . The
constant is independent of x. So, for large enough random
strings x, one has and .
5 A Computational Analysis Random Strings
We pursue the analysis of the relevance of Chaitin's
definition
by confronting it with a natural, computational requirement:
there should be no algorithmic way to recognize what strings are
random. The following result, due to Chaitin [11], Theorem 4.1, was used
for deriving the first informationtheoretic incompleteness results (see
also Chaitin [17]). We
use it now to discuss the uncomputability of . Let be a recursive bijective function. Theorem 5.1.
We can effectively compute a constant d such that if then
for all . Recall that a subset is immune iff it is infinite and
has no infinite r.e. subsets. Corollary 5.2. Let be a recursive function
such that the set
is infinite. Then, the set is immune. Proof.
Let .
Put ;
clearly, is r.e. and for
some recursive function .
So, and in view of Theorem 5.1 from
we deduce ,
is finite. This shows that itself is finite.
Corollary 5.3. The set is immune for every . Proof.
Fix . It is plain that The set is immune by
Corollary 5.2 and every infinite subset of an immune set is
itself immune. Page 57
The above theorem can be expressed as: There are two (classically equivalent) ways to represent the above statement: Based on theses statements we can formulate two constructive
versions of immunity: It is worth noticing that
there exist constructively immune sets which are not
effectively immune and viceversa. Moreover, if the
complement of an immune set is r.e., then that set is constructively immune.
Hence, we get: Theorem 5.4. For every is constructively immune. Proof.
Fix . The set is
constructively immune since its complement is r.e.
As is an infinite subset of a constructive
immune set it follows that itself is constructive immune.
As a scholium of Corollary 5.2 one obtains: Scholium 5.5 If is a recursive function with (i.e. there
exists an increasing recursive function ,
such that if , then and
the set
is infinite,
then S is effectively immune. Proof. In the context of the proof of Corollary 5.2.
and if , then and the upper bound is a recursive function of e. Corollary 5.6. For all is effectively immune. Proof. An infinite subset of an effectively immune set is effectively immune. Page 58
6 Random Strings Are Borel Normal
Another important restriction pertaining a good definition of
randomness concerns the frequency of letters and blocks of letters.
In a ´true random´ string
each letter has to appear with
approximately the same frequency, namely .
Moreover, the same property should extend to ´reasonably long´ substrings. These ideas have been stated by Borel [1][2] for sequences. In
Chaitin [10] one shows that Chaitin Omega Number representing the
halting probability of a universal selfdelimiting computer is Borel
normal. Motivated by these facts we
formalize the Borel normality property for strings.
First, let be the number of occurrences of the letter
in the string , .
Accordingly,
the ratio is
the relative frequency of the letter in the string x. For strings of length
we proceed as follows. We consider the alphabet
and construct the free monoid .
Every belongs to , but
the converse is false. For we denote by the length of x (according to ) which is exactly . For
every denote by the
number of occurrences of in the string .
For example, take . It is easy to see that .
Note that the string appears
three times into x, but not on the right positions. Not every string belongs to . However,
there is a possibility "to approximate" such a string by a string
in . We proceed as follows. For and
we denote by the prefix of x of
length (i.e. is the longest prefix of whose length is divisible by ). Clearly, and . We are now in a position to extend
the functions from to : put , in case is not
divisible by . Similarly, . Definition 6.1. A nonempty string is called
limiting ( is a fixed positive real)
if for all satisfies the inequality: Definition 6.2. A string is called Borel normal iff for every natural for every . In Calude [5] one proves the following result: Theorem 6.3. For every natural we can effectively compute a natural
number (depending upon ) such that every
string of length greater than in is Borel normal. Page 59
Theorem 6.3 can be used to prove the following result (a weaker
version was obtained in Calude, Campeanu [6]): Theorem 6.4. For every natural and for every string we can find two strings such that . Proof. Fix . Almost all strings are
Borel normal by Theorem 6.3, i.e. they satisfy the inequality for every . Take , to be the jth string of length and pick a
string such that . It
follows that in particular,
To prove that it is enough to show that which is true because and
7 Extensions of Random Strings
In this section we deal with the following problem: To what extent is it
possible to extend an arbitrary string to a Chaitin random or no
nrandom string ? Theorem 6.4 says that every string can be embedded
into a Chaitin random string. The next results will put some
more light on this phenomenon. Theorem 7.1. For every natural and every string there exists a string
such that for every string Page 60
Proof.
Fix and . Append to a string such that and ,
where is a natural number such
that . Put Next define the Chaitin computer ,
where is a selfdelimiting program for . It is seen
that This shows that every extension of lies in . Corollary 7.2.
For every natural we can find a string no extension
of which is in . The above result shows that in Theorem 6.4 we need both
the prefix and the suffix , i.e. it is not possible to fix
and then find an appropriate . However, such a
possibility is regainedconforming
with the probabilistic intuitionas
far as we switch from with a fixed t to
with an appropriate, small . We start first with a preliminary result: Lemma 7.3. Let be a partial order on which is recursive and unbounded.
Assume that satisfies the relation Then, for every string we can find a string such that and
. Proof.
Assume, by absurdity, that there exists
such that for all one has .
Put and notice that
So, since We have got a contradiction. Page 61
Theorem 7.4. For every string and natural we can find a string such that:
i) , ii) for some natural (which is about , . Proof.
Let
be the prefix order ( in case ,
for some string ). First it is seen that all
conditions in Lemma 7.3 are verified: is recursive,
unbounded and
Now take and . Let be an arbitrary string
such that . By virtue of
the preceding argument we can
find a string
such that and where is about
.
8 Chaitin's Model vs Kolmogorov's Model
The original definition of random strings (see Kolmogorov [22],
Chaitin [9][10][15])
is motivated by the fact that accordingly, is called Kolmogorov trandom if
stands for the set of Kolmogorov trandom strings. (MartinLöf [26]
used the blankendmarker complexity of a string relative to its
length to measure the degree of randomness of a string ´within´ the context
of all strings having the same length.)
All results proven in this paper concerning the adequacy
of Chaitin's definition of random strings
actually hold true for Kolmogorov's model
of random strings. (See Chaitin
[11][12][13][14][15], MartinLöf [26], Solovay [28],
Calude [3][4], Li and Vitanyi [23] for a more
detailed discussion.) To the best of our knowledge there are no ´natural´
properties associated with randomness valid for one model and not valid for the other
one.
The underlying complexities and are ´asymptotical
equivalent´. Indeed, a crude relation between and is the following: Page 62
A more exact relation was obtained by Solovay [28]. Put: Theorem 8.1.
The following relations hold true: In view of Theorem 8.1 it might be the case
that the set of Kolmogorov random strings
actually coincid
es with the set of Chaitin random strings. This is not the case! Using the proof of Theorem 3.5 one can show that
every Chaitin random string is Kolmogorov random. However, the converse is not true as
Solovay [28] has shown.
Actually, Solovay [29] conjectures that
there exists a constant such that for all sufficiently large , there
are at least strings of length , such that: So, many
Kolmogorov random strings only ´look´ random, but in fact, they are not.
It is an open question to find out ´natural´ properties related to the informal
notion of randomness which hold true for Chaitin random strings, but fail to be true for
Kolmogorov random strings. MartinLöf analysis, developed in Section 4, is not fine
enough for this problem.
9 The Role of the Underlying Alphabet
It seems th
at there is a wide spread feeling that the binary case
encompasses the whole strength and generality of coding phenomena, at
least from an algorithmic point of view. The problem is the following:
Does there exist a binary asymptotical optimal coding of
all strings over an alphabet with elements? Surprisingly,
the answer is negative. The answer is negative for
both complexities K and H. As our main
interest is directed to Chaitin complexity we shall outline the results for
this complexity measure. Let be naturals, and fix two alphabets, , having
and elements, respectively. The lengths of
and will be
denoted by and , respectively. Fix a
universal Chaitin computer and denote by its
induced complexity. Does there exist a Chaitin computer
which is universal for the class of all Chaitin computers acting on ? The upshot is the following result (see Calude [4], Calude, Jürgensen, and
Salomaa [8]): Theorem 9.1.
There is no Chaitin computer
which is universal for the class of all Chaitin
computers acting on . Page 63
The proof is based on the fact that Chaitin complexity cannot be optimized better than linearly, i.e.
the Invariance Theorem is the best possible result in this direction:
For every fix a real number ,
there is no Chaitin
computer such that for all
Chaitin computers one has: Let us study Chaitin complexity acting on alphabets of different size. We need some more notation.
For every natural put , and let us denote
by the
nth string in (according to the quasilexicographical
order induced by ; let be Chaitin complexity. Theorem 9.2. Let . Then, there exists a constant (which depends upon )
such that for all we have: Proposition 9.3. For every and all , So, no string is random over . (This result follows also from Theorem 6.3.) In the binary case we have only
two such strings, namely which are obviously nonrandom. In the nonbinary case we have strings over the alphabet which are nonbinary because they do
not contain all letters. For instance, for one has
such strings, some of them (in fact, according to Theorem 3.7,
more then , where is a constant which depends
on the size of the alphabet but not on the length n) are random as
binary strings. So, it is shown once again, that randomness is
a contextual property.
10 Conclusion
In view of the above discussion we conclude that Chaitin's model of
random strings satisfy many natural
requirements related to randomness, so it can be considered as an
adequate model for finite random objects. It is a better model
than the original (Kolmogorov) proposal.
The distinction between Chaitin and
Kolmogorov models is far from being elucidated, e.g. no propertynaturally associated
with randomnessholding true for Chaitin random strings and failing to be
satisfied by Kolmogorov random strings is actually known.
All descriptional complexities in the binary and nonbinary cases have
crucial differences, so it appears that it is only natural to discuss the
complexity
and randomness of finite objects in a nonnecessarily
binary framework. Page 64
Acknowledgment I wish to warmly thank Greg Chaitin for many stimulating discussions
on random strings (by email, in Auckland, New Zealand and Bar
Harbor, Maine, US) and for kindly permitting to incorporate his
proofs for Theorems 4.5 and 6.4. I express my gratitude to Helmut
Jürgensen, Per MartinLöf, Charles Rackhoff, Arto Salomaa, and Bob
Solovay for their illuminating comments.
References
[1] É. Borel. Les probabilités dénombrables et leurs
applications arithmétiques, Rend. Circ. Mat. Palermo 27(1909), 247271.
[2] É. Borel. Leçons sur la théorie des fonctions,
GauthierVillars, Paris, 2nd ed., 1914.
[3] C. Calude. Theories of Computational Complexity, NorthHolland,
Amsterdam, New York, Oxford, Tokyo, 1988.
[4] C. Calude. Information and Randomness. An Algorithmic Perspective,
SpringerVerlag, Berlin, 1994. (Forewords by G. J. Chaitin and A. Salomaa)
[5] C. Calude. Borel normality and algorithmic randomness, in G. Rozenberg,
A. Salomaa (eds.). Developments in Language Theory, World Scientific,
Singapore, 1994, 113129. (With a note by G. J. Chaitin)
[6] C. Calude, C. Cámpeanu. Note on the topological structure of random
strings, Theoret. Comput. Sci. 112(1993), 383390.
[7] C. Calude, I. Chiçescu. A class of universal P. MartinLöf tests,
EATCS Bull. 25 (1984), 1419.
[8] C. Calude, H. Jürgensen, A. Salomaa. Coding without Tears, manuscript,
February 1994, 15 pp.
[9] G. J. Chaitin. On the length of programs for computing finite binary
sequences, J. Assoc. Comput. Mach.. 13(1966),547569. (Reprinted
in: Chaitin [15], 369410.)
[10] G. J. Chaitin. On the length of programs for computing finite binary
sequences: statistical considerations, J. Assoc. Comput.
Mach. 16(1969), 145159. (Reprinted in: Chaitin [15], 411434.)
[11] G. J. Chaitin. Informationtheoretic limitations of formal systems,
J.Assoc. Comput. Mach. 21(1974), 403424. (Reprinted in: Chaitin [15], 291333.)
[12] G. J. Chaitin. A theory of program size formally identical to
information theory, J. Assoc. Comput. Mach. 22(1975), 329340.
(Reprinted in: Chaitin [?], 197223.)
[13] G. J. Chaitin. Algorithmic information theory, IBM J. Res. Develop.
21(1977), 350359,496. (Reprinted in: Chaitin [15], 83108.)
[14] G. J. Chaitin. Algorithmic Information Theory,
Cambridge University Press, Cambridge,1987. (third printing 1990)
[15] G. J. Chaitin. Information, Randomness and Incompleteness,
Papers on Algorithmic Information Theory,
World Scientific, Singapore, New Jersey, Hong Kong, 1987.( 2nd ed., 1990)
[16] G. J. Chaitin. Randomness in arithmetic, Scientific American 259(1988), 8085. (Reprinted in: Chaitin [15], 1419.)
[17] G. J. Chaitin. InformationTheoretic Incompleteness,
World Scientific, Singapore, New Jersey, Hong Kong, 1992.
[18] G. J. Chaitin. On the number of Nbit strings with
maximum complexity, Applied Mathematics and Computation 59(1993), 97100.
[19] G. J. Chaitin. The Limits of Mathematics, IBM Watson Center,
Yorktown Heights, Draft July 23, 1994, 219 pp. Page 65
[20] P. Gács. Lecture Notes on Descriptional Complexity and Randomness,
Boston University, 1988, manuscript, 62 pp.
[21] P. S. Laplace. A Philosophical Essay on Probability Theories,
Dover, New York, 1951.
[22] A. N. Kolmogorov. Three approaches for defining the concept of
´information quantity´, Problems Inform. Transmission 1(1965), 311.
[23] M. Li, P. M. Vitányi. An Introduction to Kolmogorov Complexity
and Its Applications, SpringerVerlag, Berlin, 1993.
[24] X. Li. Effective immune sets, program index sets and
effectively simple sets  generalizations and applications of the
recursion theorem, in C. T. Chong, M. J. Wicks (eds.). SouthEast
Asian Conference on Logic, Elsevier, Amsterdam, 1983, 97106.
[25] S. Marcus (ed.). Contextual Ambiguities in Natural & Artificial
Languages, Vol. 2, Ghent, Belgium, 1983.
[26] P. MartinLöf. The definition of random sequences, Inform. and Con
trol9(1966), 602619.
[27] A. Salomaa. PublicKey Cryptography, Springer Verlag, Berlin, 1990.
[28] R. M. Solovay. Draft of a paper (or series of papers) on Chaitin´s
work ... done for the most part during the period of Sept.  Dec. 1974, unpublished manuscript, IBM
Thomas J. Watson Research Center, Yorktown Heights, New York, May 1975, 215 pp. [29] R. M. Solovay. Email to C. Calude, August 13, 1994. [30] R. M. Smullyan. Effectively simple sets, Proc. Amer. Math. 15(1964), 893895.
[31] V. A. Uspensky. Kolmogoro and mathematical logic, J. Symbolic Logic 57(1992), 385412.
Page 66
