ImperialViolet

Been playing about with Rule 30 CAs (see ANKOS page 53). You might want to read Sunday's post first (if you have not already).

As I said, Rule 30 CA seems to map very regular numbers onto odd sequence numbers. The lack of type A randomness in the input number and the presence of it in the output data, gives rise to seeming `added complexity'.

Today I'm taking a look at that mapping.

The input to the CA is the starting line expressed as a number. A black block is a 1, white is 0. The input size is always odd. The output is the first n bits down the centerline (not including the bit from the starting line). For example

That is a size 3 CA with starting value 6 (101 in binary). The centerline is down the middle (the white column) and the result is 1 (001 in binary).

Now we can cycle through all the possible input values for a given size and record the output. Rather than give a huge table I've taken a tally count of the outputs and plotted output value against count

Results from 5 bits

Results from 7 bits

Results from 9 bits

Results from 15 bits

We can certainly see that the mapping is not one way. In fact there are very few possible output values and all the inputs map to a small number of possible outputs. The maximum count in each case is 2^{n-3} + 2^{n-2} (where n is the size of the input in bits).

The number of different outputs is also noteworthy. It has a maximum of 44 upto 23 bits of input. (of course it gets quite time consuming to run tests with greater than 23 bits of input).

Size of input (x) vs number of different outputs

I don't have any conclusions at the moment, but at least I would be worried about using Rule 30 CAs as random number generators given that all the seeds seem to map to (at most) 44 sequences