First, if X and Y are in the orbit then the 1's of X are not a subset of the 1's of Y. For suppose this is the case. Write down the period starting with X: X, ..., Y, ........, (X) Now add 1's to the first X to turn it into Y and regenerate the period using the monotonic update rule. We get: Y, ........, X, ..., (Y) i.e. the same period but starting with Y. But since the update rule is monotonic, adding 1's to the first term can only add 1's to *all* terms and can never subtract 1's. Thus, the total number of 1's in the period has increased which is impossible. Next, let X_1, X_2, ..., X_k be *any* sequence such that for any X_i, X_j the 1's of X_i are not a subset of the ones of X_j. For each X_i, let T_i be the logical expression which is the AND of the bits which are 1 in X_i. For example, if X_3 = [1 0 0 1 0 1] then T_3 = (x1&x4&x6). To derive the update rule for the first bit, let i_1, i_2, ..., i_s be the indices of the X's in which the first bit is set. The update rule is then: x1 := T_(i_1-1) | T_(i_2-1) | ... | T_(i_s-1) where T_0 = T_k. This works because the term T_i is *only* activated by X_i, which follows from the fact that no other X_j has all the 1's of X_i. The update rules for the other bits are constructed similarly. Thus, the maximum orbit is equal to the maximum number of subsets of n elements that can be chosen so that no subset is contained in any other. J.P. Grossman On Fri, 29 Nov 2002, Allan C. Wechsler wrote:
Ooh, that subject line is so deliciously jargony. You are probably wondering what the hell I mean.
Suppose you have an automaton consisting of an n-bit register, where each bit's next state is a boolean function of the states of all the other bits. We wish to find a rule (that is, an update function for each bit) and an initial state that maximizes the number of states that the automaton traverses before it repeats a state.
The obvious maximum of a 2^n-state trajectory is easily achieved by creating a binary counter. Each bit will be on next time in two cases: if it is now on and some bit to its right is off; or if it is now off and all the bits to its right are on. (This is just the standard carry rule, "flattened" to a boolean function of the present bit values.)
But note that this logic is required to take explicit notice that certain bits are off. Suppose we restrict the logic, and permit only monotonic boolean functions? We now expect that the 2^n maximum cannot be achieved, in general. We can still implement an n-bit counter with monotonic update rules, but it takes 2n actual bits. So a lower bound of the maximum achievable orbit of such an automaton is 2^[n/2].
Can anyone tighten these lower and upper bounds of 2^[n/2] and 2^n?
-A
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun