We just encountered the OR gate, which outputs a 1 if either input (or both) is a 1.
We’re now going to build an XOR gate (eXclusive OR) . This is similar to the OR gate, but it rejects the “or both” case — it only outputs a 1 if the left input is 1, or the right input is 1, but not both.
Another way of looking at it: an XOR Gate checks if the inputs are different to each other.
building an XOR
We’re already halfway there with our existing OR gate:
After the OR gate, we need a way to check for the 11 case, and change the output into a 0, which is the only way an XOR differs from an OR.
How do we distinguish the 11 case?
When we get a 11, a 
appears in the left-hand output of the turn 
. This is the only time this happens — remember, this output corresponds to an AND gate.
So we need something that can detect a in the left-hand output, and use that to deflect the right-hand .
How about a switch 
?
We have our XOR gate! Let’s review how it responds to different inputs:
- 00 — no marbles flow in, no marbles flow out, corresponding to a 0
- 10 — the turn moves the marble to the right. It enters the switch as a signal marble, and outputs the centre channel as a 1
- 01 — same as above
- 11 — the marbles move in a straight line through the turn. They enter the switch, and the checker marble blocks the signal marble from falling into the centre channel, corresponding to an output of 0
xor roon
Alternatively, we could just use the xor 
roon:
This behaves exactly the same as our compound roon, just in a smaller package.
turing completeness
Unlike the AND and OR gates, the XOR has a special property: it’s possible to build a computer using only XOR gates. We can say that XOR gates are Turing complete.
Very roughly, for a system to be Turing complete, it must be able to:
- check conditions, and respond differently in each case;
- keep state (data) in memory, to be used later;
- continue operating until finished, without a fixed time limit.
It’s not that different to what a person needs in order to handle everyday life — you need to be able to:
- Act differently depending on the conditions around you
- Remember things
- Keep going until you’ve finished a task — if you had to have a nap every five minutes, many tasks would be impossible
It turns out that we can combine XOR gates in flexible ways to satisfy these three conditions. We’re not going to do that, because I don’t know how it would be wildly impractical.
Instead, in the next tutorial we’ll start combining our XOR gates with other elements so we can build a computer component.
continue
