Edward Fredkin is best known these days for the Fredkin gate, a universal reversible circuit.

I recently found out that Fredkin was one of the pioneers in cellular automata. His student Edwin Banks describes a cellular automaton introduced by Fredkin [1].

Edward Fredkin of MIT has described the following interesting cellular space. If the states are 0 and 1 and if the result state is obtained by taking the sum of the neighbors, modulo 2, then every initial configuration will reproduce copies of itself about the initial configuration.

In other words, start with some bit pattern in an infinite checkerboard of bits. Then at each step, replace each bit by the parity of the sum of the neighboring bits. Eventually you’ll see copies of that original pattern.

There’s some ambiguity regarding what “neighbors” means. Banks’ dissertation considers the neighbors of a bit to be the bits to the north, south, east, and west, and this implies that Banks has these neighbors in mind when he describes Fredkin’s automaton. Other sources say Fredkin also considered diagonally adjacent bits as part of the neighborhood, i.e. northwest, northeast, southwest, and southeast.

Banks goes on to say

Terry Winograd (1970) generalized this result showing that any neighborhood, not just the four nearest neighbors, and any number of dimensions still yields the same results.

I take it by “the four nearest neighbors” the neighbors to the north, south, east, and west. I’m not sure what the “any neighborhood” means in Winograd’s theorem; I imagine there must be some implied restriction.

In any case, I’ll show by example that both definitions of “neighborhood” discussed above lead to reproducing the original pattern, though they do not reproduce it in the same way.

I’ll start with an ‘E’ in the middle of a grid. The black squares represent 0s and the white squares represent 1s.

Here are the first eight steps in evolving this pattern, using the rule that “neighbor” only includes north, south, east, and west neighbors.

If we consider each point to have eight neighbors, i.e. we include diagonals, here’s what the first eight steps look like.

Update: Here’s an animated version of the first automaton

and the second

See the next post for a generalization using more than two states per cell, using colors rather than black and white cells. If the number of colors is prime, and you take the sum of the neighboring states mod p rather than mod 2, you get analogous results.

[1] Edwin R. Banks, Information Processing and Transmission in Cellular Automata. MIT dissertation. January 1971.

I was thumbing through A New Kind of Science [1] and one of the examples that jumped out at me was looking at the bits in the binary representation of the powers of 3. I wanted to reproduce the image myself and here’s the result.

Here a white square represents a 1 and a blue square a 0. There’s a white border on the right edge because all powers of 3 are odd, i.e. end in 1 when written in binary.

As with many of the images in Wolfram’s book, it’s somewhere between regular and chaotic.

I produced the image at the command line with the following Python code.

    from numpy import log2

    N = 60
    k = int(log2(3)*N)+1

    for i in range(N):
        s = format(3**i, str(k)+'b')
        s = s.replace('1', chr(0x2588))
        s = s.replace('0', ' ')
        print(s)

The code writes powers of three as binary strings of length k where k is calculated so the last number in the sequence will fit. It then replaces 1s with a solid block character and replaces 0s with a blank space. My terminal has a blue background and a white foreground, so 1s show up as white squares and 0s as blue.

The characters in my terminal are twice as high as they are wide, so I changed the aspect ratio after taking the screen shot so that the blocks come out more square.

Update: Other bases

What if we look at bases other than 3?

Here’s the revised code to let you specify any base b.

    from numpy import log2

    def out(s):
        s = s.replace('1', chr(0x2588))
        s = s.replace('0', ' ')
        print(s)    

    b = 5
    N = 50
    k = int(log2(b)*N)+1

    for i in range(N):
        s = format(b**i, str(k)+'b')
        out(s)

Here’s what powers of 5 look like:

And here’s what powers of 7 look like:

What if our base isn’t prime? It doesn’t make an obvious difference if the base is odd, but if it’s even we get a skewed image. Here’s the plot for p = 6.

This is just the plot for powers of 3 with the nth row shifted left by n positions.

Related posts

• Sierpinski strikes again
• Cellular automata with random initial conditions
• A complexity fallacy

[1] I’ve looked through the book before for fun, but this time I’m looking through it with a practical project in mind. I never thought that would happen.