Re: You will be sorry you asked: was Re: Counting
Trent Shipley wrote: ... I did not recognize this as a simple pigeonhole problem of 2n choose n, so I cross posted to lists where I thought I might get help and would not be accused of an off topic post. David Hobby, do you live in the Phoenix area? No, upstate New York. This is a design issue. Since EEs do not want metastability screwing up their designs, they minimize the window where metastability can occur. Working from scratch, one could MAXIMIZE a flip-flop's metastable window. If you take it too far, it won't BE metastable any more. It's a matter of definitions. It shouldn't be hard to design a device with three states, where the middle one has any desired degree of stability. Now with an ordinary latch we have an input control lead (it sets the latch to remember current state or receive a new state) an data input lead (if the control is T, then the data lead sets the latch to either T or F), and an output lead that just tells you whether the latch is remembering T or F. More literally the latch has TWO output leads, but if one is T the other must be F, so we gain no data from the second one. So one is the complement of the other. O.K.. I had my Digital Design textbook stolen partway through the semester, but as i remember it a latch was mathematically: A[out] - B[in], Output B[out] - A[in] Sorry, I can't decipher this. What is - supposed to mean, and while we are at it, what are A and B? So, if we have a latch with two output leads we should be able to get it to act as the brain of a trivial qpu: it will perform the not so interesting operation of ADD 1. Unfortunately if we have two latches we do not get either a 2 or a 4 q-bit computer. We just have two weak little 1 q-bit qpu's. They cannot be quantum entangled. I conjecture that a three component latch (3-latch) will not be stable, but have a tendency to ring. (Note this is a K-3 graph.) A[o] - B[i],C[i], Out B[o] - A[i],C[i], Out C[o] - A[i],C[i], Out A 4-latch, however, should be stable. Like a 2-latch I conjecture it should only output bits so that the number of Fs equals the number of Ts. A[o] - B[i], C[i], D[i], Out B[o] - A[i], C[i], D[i], Out C[o] - A[i], B[i], D[i], Out D[o] - A[i], B[i], C[i], Out That is 4 pick 2. The conjecture is that THIS 4-latch can be built and used in a QPU (designed by someone more clever than my self). It will have 6 states. Unfortunately, mapping these states to numbers is not as straightforward as in a determinate ALU, but counting to 3 should be straight forward. I don't understand exactly how the internal parts of your 4-latch are hooked up. You have some sort of mix of excitatory and inhibitory connections? But it should be possible to design something that always has two output leads high, where all six possible pairs of leads might be high. Indeed, if one can build a 4-latch QPU then one should, But it's quantum, too? ... Imagine we have a device that must produce output in pairs so that for every F there is a T. It cannot produce an odd number of outputs. How many symbols can be represented by such a machine's output (how big is the output's alphabet) for any output block size 2N that implicitly includes N F's and N T's. Now aren't you sorry you asked? ... Well, maybe a little... I don't understand the question completely. But if these are just C(2n,n), you can use Sterling's formula to approximate the factorials, and get a very accurate estimate. By the way, the estimate for C(2n,n) is approximately (pi * n)^(-.5) * 4^n ---David ___ http://www.mccmedia.com/mailman/listinfo/brin-l
You will be sorry you asked: was Re: Counting
On Friday 2005-03-04 06:27, David Hobby wrote: Trent Shipley wrote: What the I can't find any context for this. But see comments, below. ---David 1) You might have seen this on brin-l aztechlist or [EMAIL PROTECTED] I did not recognize this as a simple pigeonhole problem of 2n choose n, so I cross posted to lists where I thought I might get help and would not be accused of an off topic post. David Hobby, do you live in the Phoenix area? == As for context: Well all the chatter about things quantum on brin-l made me think of quantum computers and computation. Thinking about quantum computing reminded me that I know virtually nothing about the topic, but that ever since taking introductory digital circuit design I have known that flip-flops (the basis of memory circuits) can be put into an indeterminate state called metastable. Metastability is usually regarded by EEs as A Bad Thing.My immediate reaction was that looks like a QM effect at a macro scale. When I read about metastability in my text book my first idea was that one could use the phenomenon to build a random number generator or coin tosser. (It turns out that there are references on the web to patents for random generators based on metastability.) Then I thought, if you can use metastability to make random generators, then MAYBE (if you can find a way to entangle more states) you could use metastability to make a quantum computer with off the shelf parts ... in a garage on your vacation. Shure, there is at best a 0.05% chance of success, but IF it worked it would rank as more important than the integrated circuit and less important than the solid-state transistor. I even wrote to ask about inducing metastability. See: http://www.sigcon.com/Pubs/news/4_4.htm Most of Dr. Howard Johnson's objections to inducing metastability can either be answered or are generically a problem for ANY quantum-ALU (QLU) design one might consider. The metastable window on a flip-flop is extremely narrow, perhaps only a few picoseconds wide. This is a design issue. Since EEs do not want metastability screwing up their designs, they minimize the window where metastability can occur. Working from scratch, one could MAXIMIZE a flip-flop's metastable window. Furthermore, it [the metastable window] drifts with time, temperature, power supply voltage, and other factors. For quantum computation you need to be able to (more or less) reliably induce metastability. The latch is touchy about initial conditions, so if you want to build a quantum computer around one you need to carefully control those initial conditions. Once you set the potentiometer to create a lot of metastable events, drift in the flip-flop's metastable window will soon cause the circuit to fall off the metastable cusp, and the circuit will return to normal operation. You have to keep chasing the metastable window around if you want to observe events over a long period of time. Using a latch (or any other basis for a QC) throws the basis out of its initial state. Any engine (including a latch) will have a refractory period before it returns to an initial or 'ground' state and is again ready to perform another operation. These refractory periods are likely to be best described with probability curves. One can partly overcome this problem by having multiple QPUs in a series so that a fresh QPU in ground state is always waiting to take the output from the last QPU that performed an operation. == Now with an ordinary latch we have an input control lead (it sets the latch to remember current state or receive a new state) an data input lead (if the control is T, then the data lead sets the latch to either T or F), and an output lead that just tells you whether the latch is remembering T or F. More literally the latch has TWO output leads, but if one is T the other must be F, so we gain no data from the second one. I had my Digital Design textbook stolen partway through the semester, but as i remember it a latch was mathematically: A[out] - B[in], Output B[out] - A[in] So, if we have a latch with two output leads we should be able to get it to act as the brain of a trivial qpu: it will perform the not so interesting operation of ADD 1. Unfortunately if we have two latches we do not get either a 2 or a 4 q-bit computer. We just have two weak little 1 q-bit qpu's. They cannot be quantum entangled. I conjecture that a three component latch (3-latch) will not be stable, but have a tendency to ring. (Note this is a K-3 graph.) A[o] - B[i],C[i], Out B[o] - A[i],C[i], Out C[o] - A[i],C[i], Out A 4-latch, however, should be stable. Like a 2-latch I conjecture it should only output bits so that the number of Fs equals the number of Ts. A[o] - B[i], C[i], D[i], Out B[o] - A[i], C[i], D[i], Out C[o] - A[i], B[i], D[i], Out D[o] -
