Wikipedia:Reference desk/Archives/Mathematics/2015 April 25
| Mathematics desk | ||
|---|---|---|
| < April 24 | << Mar | April | May >> | April 26 > |
| Welcome to the Wikipedia Mathematics Reference Desk Archives |
|---|
| The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
April 25[edit]
Is 1/0.5/0/0 a universal logic gate?[edit]
Suppose I have a logic gate with the following truth table:
| Input 1 | Input 2 | Output |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1/2 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
...where "1/2" means randomly either 0 or 1. Would this be universal logic gate like NOR? Do not be silly - what I mean is of course an approximation of one, due to the random element. PretendAuthority (talk) 11:02, 25 April 2015 (UTC)
- Well, perhaps a faulty NOR gate. What can we say? 0,1 should map to 0, but in your implementation it sometimes does, sometimes does not. When it does not, it is not acting like a NOR gate. --Tagishsimon (talk) 11:19, 25 April 2015 (UTC)
- Note that you have two possibilities:
Input 1 Input 2 Output 0 0 1 0 1 0 1 0 0 1 1 0
Input 1 Input 2 Output 0 0 1 0 1 1 1 0 0 1 1 0
- Let's try to rephrase this more precisely. There are two versions of this that I consider interesting:
- Is it possible to find a construction in which the output has a probability approaching 1 (as number of gates increases) of being that of a universal gate for each input combination (assuming statistical independence of behaviour of the gates, and with the random entry being probability 0.5 of a 1)?
- Is it possible to construct a universal gate (e.g. NOR) from a finite number of these gates?
- As a start, we can construct an inverter: simply tie input 2 to 0, or tie the two inputs together. This is useful building block. We can use this to form an imperfect OR ("iOR") by inverting the output of an imperfect NOR. Now chain a series of iORs on input 1 with the first input 1 driven by A, and tie every input 2 to B. This produces a truth table, where entries give probability of a 1 (n0: 0 iORs, n1: 1 iOR, etc.):
- Let's try to rephrase this more precisely. There are two versions of this that I consider interesting:
A B n0 n1 n2 n3 0 0 0 0 0 0 0 1 0 1/2 3/4 7/8 1 0 1 1 1 1 1 1 1 1 1 1
- We can see that as we add iORs to the chain, the truth table asymptotically approaches that of an OR gate. Remove the last inverter, and we have what could be considered an approximate universal gate, in the sense of my first bullet. So the answer to my first bullet (and thus to the OP's question) is "yes". So now the challenge would be to answer my second bullet. —Quondum 17:59, 25 April 2015 (UTC)
- The first question is what the OP wanted to ask. The answer to the second question is obviously negative - suppose you built a circuit which outputs NOR with probability 1. Let represent the circuit's output for input x in the case that all gates behave as "NOT Input1". f is not NOR (otherwise "NOT Input1" would have been a universal gate), so there is some x for which . There is a positive probability that the circuit will output for this input x, contradiction. -- Meni Rosenfeld (talk) 19:36, 25 April 2015 (UTC)
- Dang. And here I thought that I had a counterexample, but on closer examination, your logic holds. (But until you pointed it out, it wasn't that obvious to me ...) —Quondum 20:17, 25 April 2015 (UTC)
- The first question is what the OP wanted to ask. The answer to the second question is obviously negative - suppose you built a circuit which outputs NOR with probability 1. Let represent the circuit's output for input x in the case that all gates behave as "NOT Input1". f is not NOR (otherwise "NOT Input1" would have been a universal gate), so there is some x for which . There is a positive probability that the circuit will output for this input x, contradiction. -- Meni Rosenfeld (talk) 19:36, 25 April 2015 (UTC)
- We can see that as we add iORs to the chain, the truth table asymptotically approaches that of an OR gate. Remove the last inverter, and we have what could be considered an approximate universal gate, in the sense of my first bullet. So the answer to my first bullet (and thus to the OP's question) is "yes". So now the challenge would be to answer my second bullet. —Quondum 17:59, 25 April 2015 (UTC)
- I noticed you've tried to remove one of the answers here. It is considered extremely rude and unacceptable to do so, even if it is a poor answer (as is, in general, removing comments from talk pages). -- Meni Rosenfeld (talk) 19:36, 25 April 2015 (UTC)
- I was confused by whom you were talking to, so I searched the page history. For reference, User:PretendAuthority (the original poster) tried to delete an answer in this edit. —SeekingAnswers (reply) 03:55, 30 April 2015 (UTC)