Sequences containing all finite sequences

[Franklin T. Adams-Watters]

"Christian G.Bower" <bowerc at usa.net> wrote:
>If I take a "typical" irrational number and express it in binary, ...
>
>I would expect it to contain every finite binary sequence.  I suspect
>this is very difficylt to prove though.  If it does contain every
>binary sequence, then the sequence of run lengths ...
>contains every finite sequence of positive integers.

Yes.  I've been looking at this since my initial message.  Given a finite binary sequence that includes every finite binary sequence, there are three natural ways to turn it into a sequence of non-negative or positive integers that includes every finite sequence or non-negative or positive integer.  One can take all run lengths, as Christian does above, getting a sequence of positive integers.  Alternatively, one can take the lengths of runs of zeros (or ones) only, counting zero zeros (ones) between adjacent ones (zeros), getting a sequence of non-negative integers.  Note that taking the zeros and ones sequences, dropping all zeros, and interleaving the results gets the overall run length sequence (after dealing properly with initial elements and the order of interleaving).

Interestingly, these are all three essentially invertible (with all run lengths, one must know whether to start with zero or one).  So one can define transforms between sequences by using one of these to map to a binary sequence, and then another to map back to a more general sequence.

Furthermore, the transform defined by using the inverse ones transform to go to binary, and the zeros transform to go back, is the same as using the inverse zeros transform to binary and the ones transform back; and is thus self-inverse.

The issue of whether the binary representation for a real number contains every subsequence is closely related to the issue of base 2 normality for these numbers.  While normality is a stronger condition, I doubt that this property is easier to prove for typical irrational numbers - and, of course, normality for most all mathematically interesting irrationals is unproven.
-- 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645


__________________________________________________________________
Switch to Netscape Internet Service.
As low as $9.95 a month -- Sign up today at http://isp.netscape.com/register

Netscape. Just the Net You Need.

New! Netscape Toolbar for Internet Explorer
Search from anywhere on the Web and block those annoying pop-ups.
Download now at http://channels.netscape.com/ns/search/install.jsp