The NOT gate takes one input and inverts it — a 0 becomes a 1, and a 1 becomes a 0.
In terms of marbles:
- If we receive
, we output 
- If we receive , we output
The first one is simple enough, but what about the second condition? To turn into , we need to create a marble out of thin air.
We can achieve this using a reservoir of marbles:
Remember that we can think of an xor 
as checking if its inputs are different. Because the reservoir always provides , this means the xor is checking if our stream is not , which is exactly what we want for a NOT gate.
turing completeness
With the addition of the NOT gate, we’ve reached a critical point. By combining AND, OR, XOR, and NOT gates in different combinations, it turns out we can perform any kind of computation. We say that our system is 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
practicality
Is our collection of gates really Turing complete?
There’s actually another ingredient we need — the ability to fan out the outputs of our gates. This just means copying the signal, so we can send it to 2+ places.
We can easily copy a signal using a reservoir and a switch 
, so fanning out is no problem.
… but reservoirs are bulky and inconvenient. If we need an endless stream of marbles for every copy and every NOT gate, our patterns are going to get cluttered pretty quickly — so in the next tutorial, we’ll look at a way to get rid of them.
continue
