What is a gate? (Part 1)

It's been a bit since my last "what is" post, but I'd like to return to talking about science by taking a pause from my build-up to quantum states and quantum computation to instead discuss something more classical: the notion of a logic gate.

One way of modeling classical computation is as a sequence of operations performed on some data. We can then consider each operation independently. Just as we can build up complicated equations from simple arithmetic operations, these computational operations, typically called gates, can be used to build up arbitrarily complicated computations.

Take a specific example, the NOT gate, also written ¬. This gate takes a bit and produced a bit with the opposite value. Since each bit can only have one of two possible values (either 0 or 1), we can completely specify the behavior of the NOT gate by listing what it does to each of these inputs. That is, if I tell you that ¬ 0 = 1 and that ¬ 1 = 0, then in principle, I have told you everything that there is to know about the NOT gate. If this reminds you of a basis, then your intuition serves you well— we will explore that connection more in due time.

For now, though, I would like to discuss a few more examples of gates: the AND and OR gates, often written as ∧ and ∨, respectively (if these symbols seem arcane, it may think of them in terms of set unions and intersections). Each of these gates takes two bits as inputs and produces one output. AND produces 1 if and only if both its inputs are 1 (1 ∧ 1 = 1, 0 ∧ 0 = 0 ∧ 1 = 1 ∧ 0 = 0), while OR produces 1 if and only if at least one input is 1 (0 ∨ 0 = 0, 0 ∨ 1 = 1 ∨ 0 = 1 ∨ 1 = 1). Finally, the XOR gate (short for exclusive or and written ⊕) returns 1 if and only if exactly one input is 1 (0 ⊕ 0 = 1 ⊕ 1 = 0, 0 ⊕ 1 = 1 ⊕ 0 = 1).

With these four gates, we can build up any arbitrarily complicated Boolean function; that is, a function from strings of bits to a single bit. Functions returning multiple bits can in turn be built up by representing each output bit as a Boolean function. We could actually do with less kinds of gates, but that's besides the point. Rather, the point is that together, NOT, AND, OR and XOR are universal for classical computation.

It takes some effort to prove this, but an example helps to make things concrete. The full adder circuit in particular can be used to add two one-bit numbers, and is built up entirely from two XOR gates, two AND and one OR gate, as shown in this circuit diagram from Wikipedia. These full adders in turn can be combined to add arbitrarily long integers. From addition, one can get to subtraction and multiplication, demonstrating the usefulness of the gate model in capturing arithmetic.

Even more compellingly, we can efficiently simulate Turing machines with these few gates, meaning that NOT, AND, OR and XOR are at least as expressive as Turing machines. Thinking about gates, then, is a powerful way of thinking about classical computation. As we shall see, this power carries very nicely to the quantum case as well.

P ≠ NP?

I don't have much to say on this one yet, but it's too important to stay silent on. Someone is claiming to have proved that P ≠ NP, which wouldn't be new but for the fact that the claimant is actually a credible computer scientist, such that Stephen Cook is saying it may be a correct proof. Since not everyone here is a complexity-head, let me spell out the significance of that: Cook was one of the people behind the Cook-Levin Theorem, which established the existence of NP-complete problems. Without Cook, then, the P vs. NP problem would be much less relevant, so his opinion on the matter should carry no small amount of weight. Of course, this is a science, so that can't be the last word-- hence the question mark in the title. It'll be interesting to see what light the morning brings to this one.

Many others have written on the issue, including: R. J. Lipton, Dave Bacon and Joe Fitzsimmons.