On Fri, Nov 29, 2002 at 03:09:32PM -0500, Allan C. Wechsler wrote:
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].
At 03:49 PM 11/29/02 -0800, Bill Thurston wrote:
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?
My prose was a bit blurry, as a couple of people have pointed out privately. I was trying to say that I knew an actual monotonic implementation of an n-bit counter using 2n bits. It works as follows: the n-bit counter is made of n "metabits", each two bits long. Each such metabit is always in state 10 or 01, never 00 or 11. We use 10 to represent "meta 0" and 01 to represent "meta 1". Now there is a bit that can be depended upon to be on when a given metabit is off. A 3-metabit counter begins to count like this: 10 10 10 10 10 01 10 01 10 10 01 01 ... I leave it as an exercise to the reader to construct the monotonic update rule for each bit. -A