On Fri, Nov 29, 2002 at 03:09:32PM -0500, Allan C. Wechsler wrote: ...
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? When you say that 2n bits is required to implement an n-bit counter, does this means that you know how to do it with 2n bits, or is this actually a proven bound for something?
Here are a couple of thoughts that improve the upper and lower bounds: For an upper bound: if it ever happens that the state at time t+1 is greater than the state at time t, from then on the sequence of states has to increase. The longest chain (increasing sequence) has length n, so after that it doesn't have long to live. Similarly if the state ever decreases, it plummets to 0. Therefore, if the constant function 0 or 1 is the initial state, then the length is <= n+1, not optimal for n > 1. Otherwise, you can't hit both, for if the chain ever reaches 0 or 1, it is the final state. This gives an upper bound of 2^n - 1 achievable states. I think you can generalize this using > relations between time t and t+k, but I haven't figured out any nice conclusion. In general, the necessary and sufficient condition for a sequence of states to be realizable by a monotone automaton: whenever state s_k < s_{k+l}, (k,l > 0) then for all j > k also s_j < s_{j+l} And similarly, with < replaced by >. This is just repharasing the condition that the map s_k -> s_{k+1} is monotone. Note that a monotone function defined on a subset of n-bit numbers extends to everything, by the defining the value as the sup of values on lesser (bitwise) numbers in the subset. For lower bounds: first, any sequence of incomparable elements can be the sequence of states---eg any sequence of n-bit numbers with k bits turned on (eg a binary counter, with digits repeated negated). But you can append any ascending sequence to the end, to improve the 2^[n/2]. Second, you can repeat any antichain with k of the bits, combined with any valid sequence for the remaining bits that changes once every period. E.g. this implies immediately that if f(n) is the greatest number of states achievable by a monotone automaton on n-bit numbers, f(n+2) >= 2*f(n) + 1: n | Lower bound for f(n) | example[s] of sequence that attains this 1 2 {0, 1} 2 3 {01,10,11} or {00,01,11} 3 5 {010,100,011,101,111} built from (length 2 antichain, length 1 chain) capped off with ascending chain. Is length 6 or 7 possible? 4 7 {0101, 1001, 0110, 1010, 0111, 1011, 1111} (length 2 antichain , length 2 soln) capped with chain. 5 11 {01001, 10001, 01101, 10101, 11101, 01010, 10010, 01110, 10110, 11110, 11111} Bill Thurston