The 2n bit, n bit counter generalizes as follows. If you start an automaton in a state represented by n bits and their n negations, then you can get an arbitrary automaton on n bits using just AND and OR. De Morgan's laws, NOT(p AND q) = (NOT p) OR (NOT Q), and the corresponding law for OR allow arbitrary boolean functions to be expressed using ANDs and ORs provided you have the negations of the inputs.
X-Sender: Wechsler@pop.theworld.com From: "Allan C. Wechsler" <acw@alum.mit.edu> X-BeenThere: math-fun@mailman.xmission.com X-Mailman-Version: 2.0.11 Precedence: bulk Reply-To: math-fun@mailman.xmission.com List-Help: <mailto:math-fun-request@mailman.xmission.com?subject=help> List-Post: <mailto:math-fun@mailman.xmission.com> List-Subscribe: <http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>, <mailto:math-fun-request@mailman.xmission.com?subject=subscribe> List-Id: math-fun <math-fun.mailman.xmission.com> List-Unsubscribe: <http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>, <mailto:math-fun-request@mailman.xmission.com?subject=unsubscribe> List-Archive: <http://mailman.xmission.com/cgi-bin/mailman/private/math-fun/> Date: Fri, 29 Nov 2002 23:56:42 -0500 X-Spam-Status: No, hits=-101.2 required=7.0 tests=AWL,EMAIL_ATTRIBUTION,IN_REP_TO,KNOWN_MAILING_LIST, MSG_ID_ADDED_BY_MTA_3,QUOTED_EMAIL_TEXT,REFERENCES, SPAM_PHRASE_03_05,USER_IN_WHITELIST version=2.43-cdscf X-Spam-Level:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun