In the first part of this series, I asked the question “What is a computer?” It seems like a simple question with a simple answer. I am typing this on a computer; it has a screen and a keyboard, and inside are the CPU, the RAM, a hard drive and some other fancy electronics.
As H.L. Mencken would no doubt have said, this answer is neat, plausible, and also wrong. Understanding the more complex truth reveals the most fundamental theory in Computer Science.
What machines can do
Machines do one thing. A sewing machine stitches together fabrics of various kinds, but can’t launch satellites into geo-synchronous orbit. On the other hand, a Falcon 9 would do a terrible job of Picot Edging.
Computers are different. They can perform a breathtaking range of tasks. The same machine that allows me to video conference with my friends on the other side of the world can also calculate my taxes, play a mean game of Angry Birds and compose music.
Computers are a special type of machine called a universal machine. They can run programs that do almost anything. The same computer can be programmed to control a sewing machine or fly a rocket. What a universal machine does is determined by the instructions the machine is given, not by the machine itself.
When a computer runs a program, it stops being a universal machine that can do any task and turns into a specific machine that performs the task defined by the program. The program itself is a machine in the traditional sense.
One of the specific types of machine that can be defined using a program is a universal machine. So I can create a program that itself runs programs. Most importantly, a universal machine that is defined purely by a program can ran exactly the same programs as a hardware computer.
All this was discovered by Alan Turing. He was the brilliant British code breaker and scientist who formulated the Church-Turing Thesis. While the mathematics behind the thesis is formidable, the basic idea is fairly easy to understand.
Turing demonstrated three important conclusions:
- There is a small but important class of problems that can never be solved by a program — these are called the non-computable tasks, everything else is a computable task.
- Any machine that can run certain basic operations can be programmed to perform any computable task. These basic operations are loops, logic and variables.
- Running a universal machine is a computable task.
One of the most remarkable aspects of Turing’s work is he published it in 1936, almost a decade before the first computer system was built.
What does this all mean?
Computers are a special class of machine that can be programmed to do almost anything, in particular the can be programmed to run a universal machine. From a program’s perspective, running on a programmed universal machine is exactly the same as running on a physical one.
All of modern computing is built on this idea.
For example, when you use your web browser, you are actually running dozens of different software computers, each layered on the one below. The browser is a computer, which is probably built in the C++ programming language, which uses an operating system, which runs in a virtual machine, which runs another operating system, which is built in another programming language, which translates code down to an assembly language, which runs on the instruction set of your hardware; and there are more layers in between these. Each of these layers is a universal machine: a computer.
Each layer abstracts away the complexity of the layers below. This means that programmers can build immensely complex systems without having to specify every detail of how they work. I can write code that pulls information from a computer on the other side of the world, without needing to know how that other computer works or how the data is transferred across the network to my machine. All that complexity is hidden from me.
This is the heart of computer science. A computer is not a physical device. A computer is a universal machine and can exist purely as software. Almost all of the computers currently in existence are software not hardware machines. Because software machines are precisely as powerful as hardware ones, I can continually add new computer layers to the stack and make ever more powerful systems possible.
That’s it from me. This short series on the Basics of Computer Science has, I hope, introduced you to some of the core ideas that make computers and programming so powerful. There is, of course, much, much more to explore, this is just a taster.
If there is one thing you remember, it should be Turing’s idea of a universal machine. This is what make computers different from all other machines. We have only just set out on the journey towards controlling our world through software. The next decades will see the fastest transformation of human abilities in history, as access to knowledge and computation spreads into everyone’s hands. I hope you are excited by that prospect; I am.