What is Computation?
In your intro programming course, you might have been asked to reflect on what exactly counts as computation. Computer science is ostensibly all about it, and it's no secret we've been doing it going back at least to antiquity.
Abacuses are known to have been in use in Sumer at least as early as 2300 BC. (Wikipedia)
There are plenty of computer scientists around, many of whom even happen to be kinda smart. You might think we would have figured out what computation is by now! But it turns out that giving a precise definition to the word "computation" is very difficult for much the same reason that Biologists have trouble defining the word "life". It's kind of an I know it when I see it kind of situation. The fact of the matter is that computation appears in nature in a variety of different, seemingly unrelated ways.
Slime molds have been known to be able to remember unfavourable lab conditions and even solve optimization problems, even though they don't have neurons.
They must be computing somehow... but they lack the usual computational mechanisms for actually carrying out calculations! (source)
One answer to the question of computation is that computation is what computers do. This is an unhelpful answer in general, because there are plenty of things that can perform computations that are not computers (for example, you). And perhaps more importantly, this answer leaves us wondering what a computer is.
An assumption that we will make going forward is that, whether or not there are entities out there that are not computers but still can do computations, we ultimately only care about the computations that computers do.
What is a computer?
It's important to stress at this point that the questions we are asking are at this point kind of philosophical, since mechanical computers have been around forever. We've already mentioned the abacus. There were also some very early attempts at building a mechanical calculator, like this one designed by Gottfreid Leibniz:
The "Stepped Reckoner" could perform basic arithmetic using a drum and some gears. (Wikipedia)
The original meaning of the term computer actually did refer to a person who would perform calculations in a variety of different contexts. But the computations preformed by computers like the abacus and stepped reckoner, and even for human computers as well, are of a specific and numerical form: numbers, the arcs of trajectories, etc. Your phone can do a whole lot more than that! Your phone is what is known as a general purpose computer, since the type of computation it performs can vary widely by need.
The first appearance of what resembles a general purpose computer was theorized and developed by Charles Babbage and Ada Lovelace in the wake of the Industrial Revolution of England in the 19th century.
A portion of Babbage and Lovelace's "Analytical Engine". (Wikipedia)
It's not hard to see where the inspiration for the Analytical Engine would have come from, putting it into historical perspective. The introduction of industrial machinery into the workforce in England was deeply impactful. They made factory owners tons of money: the machines could do many of the tedious jobs that their factory workers could do, and they didn't need benefits. Heading into the the 19th century, it would have been natural to ask if machines (maybe even just one kind machine) could replace the entire labour force.
Philosophers/logicians Bertrand Russell and Alfred Whitehead were actually very convinced the answer was yes, and they wrote multiple books (collectively titled Principia Mathematica) detailing how all mathematical problems in particular could be mechanized.
An excerpt from Principia Mathematica mechanizing a proof for "1 + 1 = 2".
But even after three tomes of calculations like the one above, their mechanical system for solving mathematical problems seemed to fall short of completely capturing mathematics in general. Perhaps a bit of good news for the proletariat, in the 1930s logicians and mathematicians answered the question as follows:
Obviously, there are many tasks that a computer cannot do. But coming up with a concrete example of such a task and proving it is indeed unmechanizable took great ingenuity. And moreover, proving once and for all that this task cannot be mechanized, especially without a mechanical computer anywhere around, we needed a mathematical model of computers to study.
Several mathematical definitions of the word computer were proposed by Alan Turing, Alonzo Church, John von Neumann, and several others. Modern computers are based on von Neumann's architecture for computing, for practical reasons. But Turing and Church's abstract machines are a lot simpler, came first, and yet hold up very well to this day: we still cannot find a type of computer that can do things their machines cannot. The perspective of theoreticians (the computer scientists who study theoretical aspects of computer science) has roughly settled on Turing's mathematical definition of computer, due to how intuitive it is relative to others.
The theory of computation
With the discovery of an accurate mathematical definition of computer came the start of a whole new scientific area, the theory of computation. The theory of computation, or theoretical computer science, is the subject of this course and the research focus of many thousands of scientists around the world. By now, theoretical computer science is too broad for any one course to touch on even its most important results, but we will do out best to see some of the most interesting bits. The questions we are going to ask/answer in this course are...
- What is a computation?
- What is a computer?
- What is the role of memory in computing?
- What is the role of code in computing?
- What can't a computer compute?
- What tasks are computers good at, and which are they not?
In the next few months, each of these questions will be phrased precisely and answered precisely using mathematical techniques like induction, the pidgeonhole principle, playing videogames, and drawing funky diagrams. Our path will be held up by a lot of scaffolding: we'll start with a number of simpler computer-like machines than Turing's computer (what's called a Turing machine) and discover things like algorithms and programming languages along the way. It won't always be easy, but with a bit of hard work and a whole lot of drawing on whiteboards, you might just find that the theory of computation can be a deeply enjoyable area indeed.
Alright, let's do this!
