Lesson 1

A computer may appear to be a device for manipulating numbers, strings, and images, but at the lowest level it manipulates only bits. A single low-level instruction takes one or two input bits and produces a single output bit. A simple model of computation that models this behavior is called a straight-line program. We introduce it using an example. The following program computes the binary representation of the sum of three input bits using five simple instructions (or lines).

def sum3(x1, x2, x3):
    a = x1 ^ x2
    b = x2 ^ x3
    c = a | b
    w0 = a ^ x3
    w1 = c ^ w0
    return w0, w1

One can ensure that this program satisfies its specification, that is, that it computes the sum of three bits, as follows.

from itertools import product

for x1, x2, x3 in product(range(2), repeat=3):
    w0, w1 = sum3(x1, x2, x3)
    assert x1 + x2 + x3 == w0 + 2 * w1

Note that the program is extremely simple. In general, its inputs are Boolean variables \(x_{1}, \dotsc, x_{n}\). Then, each instruction of the program has a form \[g \gets h \circ k \ ,\] where \(\circ\) is a Boolean binary function, \(g\) is a new identifier, and each of \(h\) and \(k\) is either an input variable or the result of one of the previous instructions. And that's all! No loops, no conditional jumps. It's hard to imagine a more simply structured program.

We say that a program computes a function \(f \in B_{n,m}\) if each output of \(f\) is computed by some instruction in the program; that is, for all \((x_{1}, \dotsc, x_{n}) \in \{0,1\}^{n}\), the value produced by that instruction coincides with the corresponding output bit of \(f\).

The computation graph of a straight-line program is obtained by drawing an arrow from each operand to the instruction that uses it. This directed acyclic graph is called a circuit. Its size is defined as the number of internal vertices, equivalently, the number of instructions, which are referred to as gates. By default, we assume a gate may compute any binary Boolean operation.

The circuit corresponding to the straight-line program above is shown below. It is known as Full Adder (FA).

To give another example, below, we show a straight-line program and the corresponding circuit, known as Half Adder (HA), for computing the binary representation of the sum of two bits.

def sum2(x1, x2):
    w0 = x1 ^ x2
    w1 = x1 * x2
    return w0, w1