A program that generates sequence B will be essentially the following copying recipe: first print 1, then 0, then 0, then 0, then 1, then 0, then 1, then … there is no way any program can compress the sequence. If we write the program itself in the language of 0's and 1's, it will be at least as long the sequence it generates. Thus sequence B has a complexity of approximately 1 billion bits.
We define a sequence to be random if and only if its complexity is (roughly) equal to its length; that is, if the shortest program capable of generating it has (roughly) the same length as the sequence itself. Thus sequence A is not random, but sequence B is.
Chaitin has employed the notions of complexity and randomness to demonstrate a variety of deep mathematical results. Some involve his astonishing number Omega, which establishes that chance lies at the very heart of deductive mathematics. These results are explained in many of his books, including the forthcoming, "Meta Math" (available on his Web site at http://www.cs.auckland.ac.nz/CDMTCS/chaitin/). Let me here just mention his proof of Godel's theorem.
He begins with a discussion of the Berry sentence, first published in 1908 by Bertrand Russell. This paradoxical sentence asks us to consider the following task: "Find the smallest whole number that requires, in order to be specified, more words than there are in this sentence."
Examples such as "number of hairs on my head," " number of different states of a Rubik cube" and "speed of light in centimeters per decade," each specify, using fewer than the 20 words in the given sentence, some particular whole number. The paradoxical nature of the task becomes clear when we realize that the Berry sentence specifies a particular whole number that, by its very definition, the sentence contains too few words to specify. (Not quite identical, but suggestive is this directive: You're a short person on an elevator in a very tall building with a bank of buttons before you, and you must press the first floor that you can't reach.)
