Everything is a number.

Computers do many amazing things. They are clearly very good with manipulating numbers. They can do calculations that would take us a lifetime to do with paper and pencil just in seconds. They can search ridiculously large amounts of information and get back an answer to a query almost instantaneously. They can let you play and edit songs and videos. They can play video games with you. They can steer trains, cars and airplanes. They can also beat the best human chess player in chess and the best human Jeopardy! player in Jeopardy!

How come they are so versatile? As a computer science professor if I had to give a one-short-sentence explanation for this amazing diversity of computers' capabilities, it would be: Everything is a number.

You may be thinking that I have some kind of fancy numbers in my mind when I say this. But I don't. I am not talking about irrational, or complex, or imaginary, or transcendental, or some other type of fancy numbers. I am not even thinking about real numbers. I am thinking about good old natural numbers which start with 0 and can be obtained by just adding one to the previous number in the sequence like so: 0, 1, 2, 3, . . .

I said "Everything is a number." and everything is a lot to cover, so let's start. The sentence "Everything is a number." is itself a number. The sentence consists of a sequence of alphabet symbols and blank spaces followed by a period at the end.  There is something called American Standard Code for Information Interchange (in short ASCII code) which assigns a number to each letter of the alphabet and each punctuation symbol. In the ASCII encoding, the lower case letter "i" corresponds to the number 105 and the lower case letter "s" corresponds to the number 115. So the word "is" which is concatenation of "i" and "s" corresponds to the number 105115 (which I obtained by concatenating 105 and 115). In the ASCII encoding, the code for " " (the space we leave between words) is the number 32 and the code for the period is 46.  Using the ASCII encoding, the number for the sentence "Everything is a number." happens to be 69118101114121116104105110103032105115032097032110117109098101114046. Seems like a pretty large number, but, then, I did not claim that everything was a small number.

Following this approach we can map any text to a single number, we just keep concatenating the numbers that correspond to the characters and the punctuation symbols. Keep in mind that we will never run out of numbers because there is an infinite number of numbers out there! There is a number for each text. There is a number for Cervantes' Don Quixote and there is a number for Shakespeare's Macbeth. There is a number for any text that anyone has ever written. I can even give you a finite range of numbers and claim that any novel with a reasonable length that anyone has ever written or will ever write is a number within that finite range. So, if you are an author who is having writer's block, there is nothing to worry about, you can just pick a number from that range and map it back to text based on the ASCII encoding, and there, you have a novel. If you use this strategy to write novels, your novels are very likely to be unreadable. But the point of this post is not to discuss which method to use to write novels. The point is, if you do ever write a novel, it will be a number within that finite range.

There is one issue I need to clarify. ASCII code is not the only way one can map characters to numbers. So, although I showed you that there is a way to map any text to a number using the ASCII code, that is not the only way. There are many ways one can do it. So, mapping between the texts and the numbers depends on the encoding you use. Once you decide on the encoding, you can map any text to a number and you can map any number back to the text it represents.

OK, so far we covered written text. What next? How about speech? Or, let's go even further and cover every sound. Yes, there is a number for every sound. Here is one way of mapping a sound to a number. First record the sound using a recording device, and then convert the recording to the MP3 format (the format used by music players like iPod). If you open the MP3 file and look at the contents of it, you will see a very long sequence of 0s and 1s. The MP3 file is a very very very long binary number. So what ever the sound you recorded, it is converted to a number when you store it in the MP3 format.

Conversion of the sounds to numbers are a little more complicated than the conversion of the text. I cannot tell you how it is done for the MP3 format in particular but I can give you a general idea. Any sound we hear corresponds to a wave that travels in air. It is kind of like a wave in the ocean, it has peaks (the highest points of a wave) and troughs (the lowest points of a wave). To convert a sound into a number, you need to measure the height of the sound wave frequently and store those height measurements as numbers one after the other.

The question is how frequently should we measure the height of the wave? If you do not measure frequently enough, you may only measure the wave at its peaks and then you may get the wrong impression that there is no wave at all and the ocean is still, or in our case we might think that it is silent. Luckily, there is a result from the area of signal processing that tells us how frequently we need to measure the height of a wave in order to capture it perfectly. It depends on how rapidly the wave changes from a peak to a trough. You just have to measure the height of the wave two times as fast as that. It turns out, humans cannot hear sound waves that change from a peak to a trough more than twenty thousand times a second and less than twenty times a second. So we do not need to bother with sound waves that are not in that range. This means that it is enough to measure the height of the sound wave forty thousand times a second if we only care about recording a sound for humans. That is a lot of measurements.

There is also the question of how to convert the height of the wave to a number. How precise should we be in measuring the height? It has been observed that a binary number that contains 16 binary digits would give us pretty good precision for storing the height of the wave. Let's recap. One second of sound can be represented with a number that is the concatenation of forty thousand sixteen digit binary numbers. That is one large number, but again, do not worry, we will never run out of numbers. Using this approach, we can convert any sound, no matter how long, to a (very large) number by writing the height measurements one after another. In principle, this is how your MP3 files represent a recording. They also do a lot of clever things to make the resulting numbers smaller but I will not be able to get into those here.

What about images and videos? How do we map them to numbers? First, a video is a concatenation of images like a text is a concatenation of characters. For example each second of a DVD video consists of 25 images. So if we can map an image to a number then we can map a video to a number.

How do we map an image to a number? Did you ever try to manually copy a picture by dividing it into little squares? When you make the squares small enough the image in each square becomes simple enough that you can copy it easily. If you keep making the squares smaller, at the end you will get a square which is just a single color. This is what computers do, they divide an image to small picture elements (called pixels) that can be represented as a single color. It turns out that many colors can be represented as a combination of red, green and blue. To convert an image to a number, you first divide it into small rectangles called pixels, and then for each pixel you measure how much red, how much green and how much blue you need to get the color of that pixel. The amount of red, green and blue needed can all be recorded as numbers and together they represent the number for that pixel. Then, the number for the whole image is the concatenation of all the numbers for all its pixels.

The things I discussed so far are all called data. Computers store data as numbers. It does not mater what type of data, computers convert all data to numbers. In fact, they convert them to numbers stored in binary format as sequences of 0s and 1s. But what about processing of data? The programs that process the data, how are they stored? Interestingly enough, computers also store programs as numbers! Actually this is not very difficult to see. Programs are typically written very much like regular text using characters of the alphabet and punctuation symbols. The languages they are written in are different than the natural languages like English, but, still, the programs are written like any other text. Since we know that any text can be mapped to a number, then clearly every program can also be mapped to a number and that is exactly what computers do, they store programs also as numbers like they store data.

So far I discussed how computers can represent information about the real world as numbers and represent the programs that do things with that data also as numbers. If you think about it, this is a very general concept and in addition to explaining how computers store and play music and video files it also explains how computers can be used for many other things, like physical simulations. For example, gathering as much information about the weather as we can by measuring anything related to it, and then using this data and the rules of physics for weather forecasting is another application of this concept. But does this cover everything? Well, now let's speculate a little. There is this idea that physicists have been working on for a long time: Finding the theory of everything. This would be a set of rules that explain everything that happens in our universe. If they do find these rules, we can implement a program that simulates these rules and map that program to a number. Then, if we can measure everything we can about the universe, and map those to a number, we would end up having a number for everything and a computer that can run the universe for us! Well, that is a lot of "if"s, but it is plausible!

Universality

1936 was an important year for computing. Before I explain why, let's imagine that we travel in time to 1936, find a person on the street, and ask "Where can I buy a computer?" What would be the response of the person from 1936? Maybe the person would say "What is a computer?" This would be a reasonable response since the electronic devices that we call computers nowadays were not invented yet. But, the person is likely to say something like "What do you mean buy a computer? You mean hire a computer, right?"

Hire a computer? Maybe he means rent a computer? It seems like we are having a communication breakdown. Actually, the problem is we are using the word "computer" to mean different things. For the person from 1936, a computer is not a device. Instead, it means a person who performs mathematical calculations. If you had some difficult calculations to do in 1936, you could hire a person called a computer and that person would compute them for you, using paper and pencil. Human computers were used for many purposes including scientific computations such as calculating orbits of comets in astronomy, and military computations such as calculating ballistics trajectories during the First and Second World Wars. In 1936 being a computer was simply a profession.

What is special about 1936, why is it an important year for computing? It is the year a mathematician named Alan Turing published an article that became the foundation of computing. And the ideas in Alan Turing's article are as important today as they were then. They explain what computing is all about.

In his article, Alan Turing was trying to answer the question that is the title of this blog: What is computing? And he was trying to do this at a time when the devices that we call computers today were yet to be invented. Turing was imagining a device that did not exist yet. He was tremendously successful in this endeavor. He managed to come up with an imaginary device that captures the essence of all computation.

Turing was a mathematician and he was thinking about automating computation. He was thinking of a machine that can automatically do the same things that human computers of his time were doing. To design his machine he first thought about how human computers work. Well, how did human computers work? They worked like we would if we wanted to compute something without the assistance of an electronic device. They used a notebook to store the numbers that result from their calculations, a pencil to write the numbers, and an eraser to erase the numbers. They probably started their computation by writing the input numbers for the computation in their notebook. At any moment during the computation, they would look at the intermediate results in their notebook and compute a new result based on the intermediate results and either write it to a new page on the notebook or maybe erase some of the previous intermediate results and write the new result.

Let me give an example to make this a little more concrete. Assume that we hired a human computer to compute the cubes of a set of numbers. So, we will give this person a set of numbers, like 2, 5, 10 and we want human computer to give us back the following results: 8, 125, 1000. Well, maybe that does not seem that difficult. How about if we gave 61, 173, 467 as input? It is not that easy to compute the answer (which is 226981, 5177717, 101847563) without using an electronic device, right? But there were no electronic devices in 1936. If you did not have much time yourself, but had some money, you could hire a human computer to do the computation for you. The human computer would probably first write the input numbers to his notebook. Then he would start with the first number. Multiply the first number with itself (which is done, if you remember the long multiplication, digit by digit while producing some intermediate results which are then added together).  Then he would multiply this intermediate result again with the input number to get the cube. He would continue like this until finishing the list.

OK, we can see how a human computer can compute some stuff. But Turing was interested in figuring out how a machine can do the computation. Being a mathematician, he wanted to come up with a very precise and simple description. The description he came up with was pretty similar to how a human computer works. Here it goes: Turing assumed that the computing machine would need something to write on the input and the intermediate results. Let me call this the notebook of the machine, but it does not have to be a real notebook of course. It is something that Turing's imaginary machine uses as a scratch pad to record its input and intermediate results. To keep things simple, Turing assumed that each page of the notebook could either be blank or could contain a single digit (actually you can even assume that it contains a single binary digit, 0 or 1). He also assumed that at any point during the computation, a single page of the notebook would be open, and the machine could read the digit in that page, and then choose to erase that digit and write another digit or leave it as it is, and then move to the next page or the previous page or stay in the same page.

So far so good. It is very similar to how human computers work. But there is something missing, right? A human computer knows the steps of the computation (like how to do long multiplication) and follows those steps to do the computation. How are we going to tell the computer machines the steps of the computation? Turing again had a simple solution to this. He imagined that his machine would contain a list of steps where each step had a single action describing what to do at that step. An action for a step would be in the following form: Read the digit on the current page and based on that do the following 1) decide what to write to the current page (or to leave it as it is), 2) decide either to go to the next page or the previous page or stay in the current page, and 3) decide which step to go to next.

That's it. That is the model Turing came up with. Let's recap. Turing's computing machine consisted of a set of steps (with associated actions) and a notebook. Each step identified what to write to the notebook's current page and which page to go to and what the next step would be. Seems pretty simple.

Some of the details of Turing's model can sound arbitrary. For example, why just write a single digit in each page? Why are we wasting all that paper? First, remember that this is an imaginary machine that Turing proposed for modelling computation, so we are not really going to implement it using a real notebook. But the key point is, Turing wanted to keep things as simple as possible while capturing the essence of computation. So, why keep a single digit in each page? Because it is just simpler to define it that way and it is enough to capture the essence of computation. Same goes for moving one page at a time. It is simpler to just assume that at any step of the computation you can go one page forward or backward. Any computation that can be done by moving multiple pages at a time can also be done by moving one page at a time.

Here is something you might find surprising: Any computation that our modern day computers can do can be modeled this way. Any computation can be modeled as a Turing machine (by the way, Turing did not use the term "Turing machine" in his paper, which could have sounded pretentious, the name was given later by others). Not just multiplying numbers or computing cubes or other mathematical computations, but searching the web, playing an mp3 file, editing a photo, playing angry birds, all of them. Any computation you do on your computer or on anybody else's computer can be modeled this way. Any computation anyone does on any modern day computer can be modeled this way!

I said that Turing's computing machine consisted of a set of steps and a notebook. So what do these correspond to in a modern day computer? The notebook is what we call memory nowadays. And what about the set of steps that describes a computation? We call that a program.

A key assumption in Turing's model was that the notebook used by his machines never run out of pages. What does this mean in modern terms? He assumed that his machines can use arbitrary amount of memory. This is a key feature that gives Turing's machines the power to model any computation that can be done on any computer.  

Here is something I skipped earlier. As you know, a computer can run multiple programs, not just a single program, and programmability is an essential quality of a computer. So, can a Turing machine run different programs? Well, it seems like we would need to change the set of steps that represent the computation since that is the part of a Turing machine that corresponds to a program. How do we do that? In his 1936 article Turing showed that there is a special type of Turing machine that is programmable.  This programmable Turing machine takes the set of steps describing the computation as an input written on its notebook and then executes that computation based on the given set of steps. This is exactly how modern day computers work, they take a program written to their memory as input and then execute the steps of the program. In fact, any modern computer, including any smart phone, any laptop or desktop or any super computer, corresponds to this special type of programmable Turing machine. So, in this sense, your smart phone and the most powerful supercomputer are equivalent. They are capable of doing the same things, the difference is one does it much faster than the other.

The title of this post was universality. This is the universality I was referring to. Alan Turing was able to come up with a universal model of computation that is powerful enough to capture all computation even before the electronic computers were invented. His universal model of computation gives computer scientists a very useful tool for studying computers. For example, even the most powerful super-duper computer in the world cannot solve any problem that cannot be solved by a Turing machine. So by studying Turing machines we can figure out the limits of computation. And this is exactly what Turing did at the end of his 1936 paper, but that is a topic for another time.

There is a universal essence to computation and Alan Turing was able to capture that essence in his 1936 article. This year computer scientists are celebrating centenary of Alan Turing's birthday. Now you know why.