Monday, February 4, 2013

Theory of Computing - Part 2a: The Software

While it is undoubtedly useful to calculate mathematical solutions to problems quickly and accurately a computer's real usefulness stems from the fact that it can be set up to solve abstract problems without actually changing any circuitry. This was not a happy coincidence but was a planned design based on applied mathematics.

The Theory Behind General Computing

The idea for a computer program has its roots in a concept known as a Turing Machine. This theoretical machine is essentially a device that reads actions from a strip of tape, performs those actions according to a rule table and then, depending upon the action, writes the result back to the same strip of tape. In his paper explaining the concept, Alan Turing went on to prove mathematically that a machine like this could, theoretically, be used to compute the answer to any problem that can be computed by a machine.

How Stored Program Computers Work

While computers in general have never worked exactly like a Turing machine, the way they do work is very similar. That is, they go to the section of memory set aside for the computer program, read a step from memory, perform a valid operation based on that step, and then write the result back into program memory.

The "rule table", is a series of circuits that incorporate the various operations the computer can perform. Each circuit is laid out according to the Boolean logic mentioned previously. The processor starts by reading an action code (i.e. a voltage pattern corresponding to a binary number) from the program memory. It then activates the circuit that corresponds to that action number, first setting up the input voltages depending upon the type of operation. The computer then "reads" the corresponding output voltage performing the action and writing the result back into program memory. The computer then goes to the next space in program memory where it reads the next action and performs it. This continues until the end of the program.

This brings us up to around the era of the punch card and vacuum tube computer. Where you would set up everything you need the computer to do, run the program, and take in the result. There are a number of different changes in computing that take place that complicate the model considerably. The first, is the development of programming languages to take over the tedious process of using operation numbers and translate it into something more human-friendly.

Assembly Programming

Assembly programming was a very early development. At the hardware level, a computer program requires everything to be written in binary numbers, referring to the action (also called "operation" or "op") code you want to perform as a binary, and referring to any space in program memory by binary number. This is both tedious and error prone, so early programmers quickly developed a separate computer program that takes a computer program written in a structured language (called "Assembler" and converts it to binary machine code.

Assembly language is not too complicated, as it basically takes each operation the computer supports and assigns it a mnemonic, e.g. it takes "ADD" and replaces it with the binary or hexadecimal operation number for addition on that machine. The assembler program also allows you to define a symbol, like "A" or "B" and have it replace that with the binary number for the memory address. So you could write a program line that says "Add A B" and the assembly program would read that in and replace it with the required binary instructions, e.g., "0A 01 02".

Assembly programming is still used in some specialized applications, but the main reason to cover it is because this is where you see the beginnings of the layers of abstraction used in modern computing. Instead of writing directly for the processor, you write one program that is used as the input for another program, which outputs the binary you need. This abstraction is important in that it allows you to develop complex behaviors by combining two simpler ones. You also see the roots of computer programming languages in the mnemonics used to describe computer operation codes, which are arbitrary in terms of what the computer needs to work, but meaningful to human programmers.

At this point, I'm going to split this into another post as it's becoming unwieldy. So, to be continued...