Registered: Feb 2004
Posts: 172

A simple question is asked of the NKS practicioners: Given a cell grid such as the following:

0000000000001
0000000001110
0000001011011
0000101101100
0001111101001
0011111010010
0101110111011
0110101101000

What are some simple guidelines one can use to try to figure out if there is a readily available simple rule to generate the output?

In other words: How do you work backwards to find a rule given the output? My gut feeling is that many other NKS practicioners are finding themselves exploring NKS in this "direction."

Are there some links to other topics on this forum regarding such general techniques and bits of wisdom by others?


Now for some fun stuff:

I have an app in which I needed to store all 2^14 numbers form 0 and up to 16383. I use each number's binary bit stream as a possible sequence of consecutive days for which an on bit in that position represents a "yes" for a given day and a "no" otherwise.

Simple question arose:
How many combinations of these 14 day periods are there in which only X bits are turned on?





# "on" bits; Total Combinations (in decimal and binary)
0 0000000000001 1
1 0000000001110 14
2 0000001011011 91
3 0000101101100 364
4 0001111101001 1001
5 0011111010010 2002
6 0101110111011 3003
7 0110101101000 3432
8 0101110111011 3003
9 0011111010010 2002
10 0001111101001 1001
11 0000101101100 364
12 0000001011011 91
13 0000000001110 14
14 0000000000001 1


Lets say I was crazy enough to explore the distribution of combinations well beyond 2^14. Then obviously the middle of the bell curve will push farther away from 0.

So. Is there an NKS rule to just evolve the answer for each "total" in which I am interested?

The progression above is symmetrical so I only have to find the rule to give me the following evolution:

0000000000001
0000000001110
0000001011011
0000101101100
0001111101001
0011111010010
0101110111011
0110101101000



This is just a fun homework exercise perhaps. I have not thought much about how to compute the distributions above using non NKS methods so I am sure that the stats buffs out there will know some quick formulas.


For the first question I am not asking everyone to repeat the NKS book. I have read it. I am just curious about the "state" of the "common guidlines" for which to go from output to rule. The bits of wisdom if you will.

Thanks,

__________________
P h i l i p . R . D u t t o n

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

As you seem to have guessed, this is a known problem. The numbers you give are the binomial distribution ( Binomial[14,n]), the number of ways of picking n objects from 14 (order of choices doesn't matter). The problem of going from one to the next has at least one answer. In Mathematica, it is implemented as NextKSubset in the Combinatorica package.

One place to read about it from a dynamical NKS perspective is the recent article "Permutation Numbers", Vincenzo De Florio, Complex Systems, Vol 15-2. Basically, it is an iterated Turing Machine. Of course, the TM is very simple. It is a constructed one, so one wonders what else is out there, undiscovered.

Finding a CA to match a fixed pattern is an interesting problem. When looking for a literal match, it is relatively straightforward to check if the evolution is a CA. In this case, the sequence is not a CA, because it is not local.

But if one is looking for overall features, or some other purpose where an exact match is not needed, it is not as straightforward. The place to start though is to perform a search of the appropriate rule space and look at what happens.

Report this post to a moderator | IP: Logged

Registered: Jun 2005
Posts: 39

The question as asked seems to want to know how to use CA rules to get the number of combinations of ones in numbers with a certain number of bits.

Although there is a "simple" equation for that, using factorial and division, I think that the common means of generating Pascal's triangle using addition with as many iterations as bits qualifies as a CA that does that.

But, for designing a CA that can calculate the answer, the 1D CA's (and Turing machines) have been proven equal in computing power to 2D ones such as Conway Life, and the 2D CA most obvious to program which I am aware of is WireWorld, although calculators have been made out of LIFE objects as well. And 3D CA's? A space filling curve is just a really bent line.

IMO, iterating CA's isn't the quickest way to calculate unless you have a CA chip that clocks at planck time (like a quantum computer) already.
In that case, you are the god of your own created universe.

But if you want to quickly find a CA algorithm that
outputs your sequence, you can use the
Berlekamp-Massey algorithm
to get an LFSR type CA which does it.

And I think, that since you needed
to store a sequence of numbers from 0 to 16383,
It's a more practical question, What would
be the Nth number in the sequence with N being positive and less than or equal to 16383?
(review LFSR idea above).

Can anyone tell us how to *immediately*
calculate the number which is the Yth one
in "a set having X 1's in N bits"?
(without using a counter that makes a list of all of the members of the set?)

Lets say we are crazy enough to explore the combinations well beyond 2^14.

------------------------------------------------------

__________________
If something is zero, and zero is nothing, then something must be nothing.

Report this post to a moderator | IP: Logged

Registered: Feb 2004
Posts: 172

I am still slightly puzzled (due to thick skull). Yes it is obvious that if we are interested in 14 bit numbers (or more) and we want to know how many combinations of [0,1,2,3,4...,n] bits we can turn on, then we will find the normal distribution. But how can anyone have predicted that the binary numbering system will point to the normal distribution (as far as combinations of the numbers with "on" bits are concerned)?

More fun: What if we were using all the Gray-codes up to length of 14 bits??? Then what is the distribution???


I am not totally convinced that I can just lightly wash away the fact that the number of combinations of ON bits in the binary numeral system up to n bits is following the normal distribution. I am trying to work backwards so that I can possibly understand how I can could have made such a guess.

Why is this happening? How could anyone have predicted this?

__________________
P h i l i p . R . D u t t o n

Report this post to a moderator | IP: Logged

Registered: Jun 2005
Posts: 39

I've been looking at number sets with N bits and only X 1's for quite some time and have found some interesting patterns, most of which can be found in Pascal's triangle, not only the factorials and binomials but also triangular numbers and symmetries, but I'll have to look over my notebook and make some sense out of it. Wolfram's binary plot of Pascal's triangle looks like that too, and that may have a lot to do with it.

http://mathworld.wolfram.com/PascalsTriangle.html

The gray codes correspond with ordinary binary numbers, with 2^n gray codes AND 2^n binary numbers for n-bits... Even if a non symmetrical gray code is used.

If you asked if gray codes with X 1's in N bits have the same distribution as in binary numbers, it seems to be true. Gray code and binary are similar sets, "x 1's per n bits" is always a smaller set, and all 3 sets can be generated by a kind of counting.

I am wrong if you have a special gray code that counts using "x 1's in n bits". Then it probably has the same distribution as a counter that skips numbers that are not in that set, unless the gray code rule (changing only one bit) is used, which maybe may cause some numbers to be detached from the set.

Indeed there are many ways [of counting] that are not in the order of adding one, gray code being an example. Bit-reversed counting being another.

Binary is a simple number system that reveals unexpected patterns in everything. You can't even generate random numbers without getting a strange attractor.

__________________
If something is zero, and zero is nothing, then something must be nothing.

Report this post to a moderator | IP: Logged

Registered: Feb 2004
Posts: 172

Just while thinking about gray codes (in which only one bit changes from one binary number to the next) I can't help but make the connection to a mobile automata. It just seems like a nice visual fit. Could not a mobile automaton which only changes one bit from one row state to the next basically be some kind of gray code?

__________________
P h i l i p . R . D u t t o n

Report this post to a moderator | IP: Logged

Registered: Jun 2005
Posts: 39

I don't see why not. Unless it can't get to the bit that needs to change in one iteration.
Ordinary gray code is reversibly convertable to binary, both which often subsequently change nonadjacent bits.
If a sequence changes by only one bit, and repeats, and uses all the binary combinations possible, I think it's a gray code.

__________________
If something is zero, and zero is nothing, then something must be nothing.

Report this post to a moderator | IP: Logged