Binary numbers and cellular automata
December 31, 2005
In most of our daily life we use a "positional, base ten" system for writing numbers. This means we form numbers by writing the digits 0,1,2,3,4,5,6,7,8,9 in some order; for example: 23059. The digit furthest to the right stands for "units" (multiples of 1, or 100) -- in this case there are 9 of them. The digit just to left, the 5, stands for that many 10s (10 = 101): thus, we have five 10s. Next comes 100s (100 = 102), of which we have none in this example. Next, we have 3 thousands (1000 = 103) and 2 ten-thousands (10000 = 104). Thus:
We can express arbitrarily large numbers in this way, using only the ten digits 0 through 9. The thing that makes this work is that the position of the digits determines their value. The number 50392 uses the same digits but has a completely different value.
The ancient Babylonians, the most advanced mathematical culture of 5000 or so years ago, also used a positional system, but one based on 60, called the sexigesimal system. By contrast, our base 10 or decimal system is fairly recent: probably not more than 2000 years old, and didn't reach Europe (from India via the Arabs) until about 1200. It took more than a century to be widely accepted -- Leonardo of Pisa, a.k.a. Fibonacci, was a central figure in pushing for its use.
There is another system, based on 2 instead of 10 or 60, called the binary system. It uses powers of 2, and only needs the digits 0 and 1. This makes it ideal for all sorts of theoretical uses, as well as for "digital" computers (where 0 represents "off" and 1 represents "on" in a circuit). Here's how it works.
Consider the "binary" number 11010011. The rightmost 1 stands for one unit or 1(20). The 1 to its left stands for one 2, or 1(21). The next two zeros mean we don't have any 4s (4 = 22) or 8s (8 = 23). The 1 to the left of the zeros stands for 1(24) = 16. We then have no 32s (32 = 25), one 64 = 1(26) and one 128 = 1(27). Thus, the binary number 11010011 stands for the number we would write as 211 = 128 + 64 + 16 + 2 + 1.
Conversely, starting with a number, say 185 in our system, we can write it in binary by finding the highest power of 2 that can be part of it, subtracting that off, finding the highest power of 2 in what remains, subtracting it off, and continuing in this way.
Thus,
184 = 128 + 56, so we will have 1(128) = 1(27).
56 = 32 + 24, so we will have 1(32) = 1(25).
24 = 16 + 8, so we will have 1(16) = 1(24).
8 = 1(23).
There are no 64s, no 4s, no 2s and no 1s.
So 185 (decimal) = 10111000 (binary).
Each binary "place" -- a 0 or a 1 -- is sometimes called a bit. A number made up of eight bits -- such as 11010011 or 10111000 that we have just dealt with -- is sometimes called a byte. A bit is the smallest unit of "information". A byte can be used to represent numbers from 0 to 255 (= 11111111 binary). A megabyte is (210)(210) = (1024)(1024) = (approx.) a million bytes or 8 million bits of information.
What does this have to do with cellular automata? Remember in the Game of Life (GoL) blog (early December) we considered a flat region in a plane, divided into a rectangular grid of boxes or cells. A cell can be either alive or dead. Now, let's take an even simpler idea. Instead of a flat planar region, take just a series of boxes or cells in a row, like this:
... [ ] [ ] [ ] [ ] [ ] [ ] [ ] ...
Let us agree that when a cell is alive, we'll put a "1" in that cell; if it's dead, we'll put in a "0". So we might have a bunch of cells that look like:
... [1] [1] [0] [1] [0] [0] [1] [1] ...
The idea of a cellular automaton is that we have some collection of rules which determine what happens to each cell in succeeding generations: whether it dies (goes from 1 to 0), whether it's "born" (goes from 0 to 1), or whether it stays the same. The rules can be simple or complicated, and what happens to a cell will depend on what its neighboring cells are like.
A one-dimensional cellular automaton, then, is basically a series of 1's and 0's (alive or dead cells), so corresponds to a (binary) number. The rules for the automaton determine how the cells evolve over succeeding generations, so they provide a way of converting the starting number into a series of new ones. Thus, we start with a "seed" number, in binary, then apply the rules to get a new number, then apply the rules to get a newer number, then apply the rules again and again -- iterate them -- to get a whole sequence of numbers. If you don't know the rules for the automaton, this sequence of numbers can be nearly impossible to predict. So, they can be used as codes for, say, a keyless entry system for a car, as in the Numb3rs episode. (Note that it was Amita who suggested this.) One-dimensional cellular automata can work as (pseudo) random number generators.
As a final word, there is the "3N+1" game, described in my blog of last May 3 (5/3/05). Starting with any number N: if it is even divide it by two until it becomes odd; if it is odd, multiply it by 3 and add 1. Keep doing this until you get the number 1, then stop. Every time this processing has ever been done on any starting number -- by hand or by computer -- the sequence of numbers produced has always, eventually, produced the number 1 -- though it may take a very long time (try it starting with 27, for example). If you write the starting number in binary, then the rules become very automaton-like. When a number is even, its binary form ends in 0s, so, dividing by 2 repeatedly simply chops of these 0s (same as dividing by 10 in the decimal system simply knocks off 0s). What about multiplying by 3 and adding 1? Well, 3N is simply 2N + N. Multiplying by 2 simply shifts the digits over (adding a 0 at the end), so multiplying by 3 and adding 1 simply adds each cell to the one on its right (but watch out for "carries"!), except for the last, where 1 is added. For example, start with 13 = 8 + 4 + 1 = 1101. Doubling "shifts left", and we add this to the original:
1 1 0 1
1 1 0 1
________________
1 0 0 1 1 1
So 3 times 1101 is 100111; adding 1 (and noting all the carries):
Now continue with the 3N+1 algorithm: 101000 is even, so we knock off the trailing 0s (dividing by 2 three times), giving us 101. Now we do the shift-and-add again (3N), then add 1:
1 0 11 0 1
__________
1 1 1 1
+ 1
_____________
1 0 0 0 0
Chopping off the trailing 0s (dividing by 16) gives 1, so the 3N+1 algorithm terminates, as usual, with 1.
It is possible to write the 3N+1 algorithm as a cellular automaton, though you have to adjust the rules to take into account carrying. With some modifications, cellular automata can do just about anything a digital computer can do if you are willing to make the rules complicated enough.
Some practice with 1-dimensional cellular automata can be found at the Numb3rs/TI website:
Cellular automata have been studied pretty extensively. There is a book called "A New Kind of Science", by Stephen Wolfram, which discusses them at length. If you choose to read the book (it's not too technical), you should also read some of the reviews, since it has generated a fair amount of controversy as to its significance and the perspective its author gives to his work vs. the work done by others in the field. As you know from a certain Numb3rs episode, there are strong personalities and egos involved in mathematical research...(or any research, for that matter).
Your blogmeister