Monday, February 4, 2013

Theory of Computing - Part 1: The Hardware

People like to think of computers as little black boxes where tiny ones and zeros get passed around until the answer is found. Or maybe, as a tiny circuit board that solves problems that are put to it. You can get away with this because, in a sense, that is exactly how they work. But not really. While the roots of a computer as a universal (mathematical) problem solver go back a 150 years or more, the computer we think of today is a product of the semiconductor.

The Role of the Semiconductor

A semiconductor is an electronic component that allows electricity to flow differently in one direction than it does in the other. This allows part of the circuit to store discrete states (“on” or “off”) as opposed to continuous analog states used in other types of electrical components.

Adding different kinds of semiconductor components to the circuit allows you to take the voltages of the stored states and combine them in a predictable way. This is how a computer does mathematical operations. However, these circuits are not laid out arbitrarily, but are based on a specific type of mathematics called Boolean Algebra.

The Math in the Machine

Boolean Algebra (which was developed in the 1850s) is a type of Mathematics based not on Natural Numbers (like 1, 2, 3, 4, … ), but on two values ‘1’ or “True” and ‘0’ or “False”. Rather than doing traditional operations, like addition or subtraction, you combine them logically using operations like “AND”, “OR”, and “NOT”. For example, 1 AND 1 = 1 since both input values are true, but 1 AND 0 = 0, since one input value is true and one is false.

This logic works extremely well with semiconductors since you can create a different type of transistor to correspond to each conceivable type of Boolean operation, and you can then combine these transistors so that they perform these operations and output a voltage equivalent to the correct mathematical result for any given input voltages.

Moreover, as long as the inputs are translated into on/off voltages, these operations can represent anything from simple addition to complex mathematical functions, as long as you string the transistors together correctly. Not only that, but a large portion of the Boolean algebra was devoted to taking standard mathematical operations and translating them into strings of Boolean operations. Which means that as long as you build the circuit to follow the Boolean logic, you can use it to perform most conceivable ordinary mathematical functions.

And that's what the processor in a computer is: a group of circuits that correspond to mathematical operations that can be called upon as needed. If you need to do simple addition, we've got a circuit for that! Need to compare two values and show which is greater? We got a different circuit for that! Need to compute the cosine of a given value: we can do that too!

The real question that follows from that is: how do we move from a simple calculator to a more general problem solver? And the answer is Software!