Paper Review: Alan Turing and the Origins of Complexity

It's the first time I'm doing a post like this one. I don't really know how to approach this paper review or even if it should be considered a paper review. So, first here's the basic information about that paper.

Abstract:

The 75th anniversary of Turing's seminal paper and his centennial year anniversary occur in 2011 and 2012, respectively. It is natural to review and assess Turing's contributions in diverse fields in the light of new developments that his thoughts has triggered in many scientific communities. Here, the main idea is to discuss how the work of Turing allows us to change our views on the foundations of Mathematics, much like quantum mechanics changed our conception of the world of Physics. Basic notions like computability and universality are discussed in a broad context, making special emphasis on how the notion of complexity can be given a precise meaning after Turing, i.e., not just qualitative but also quantitative. Turing's work is given some historical perspective with respect to some of his precursors, contemporaries and mathematicians who took up his ideas farther.

Author:

Dr. Miguel Angel Martín-Delgado

Link:

Alan Turing and the Origins of Complexity

I decided to talk about that paper because it's about the work of a great man, Alan Turing, without whom, the world would be so different, at so many levels that it's hard to understand the impact he had. As mention in the abstract, he gave us a better understanding of complicated Mathematical concepts. In WWII, he helped breaking the naval Enigma machine used by Nazis to communicate.

But the main reason that I decided to write a post about this paper is that it covers subjects that most computer scientists should be aware of. It doesn't matter if the proofs are not understood, but it's very important to get the foundation of computer science and to know what are the limitations of computers. Even if you already know this material, it's always good to read it again. Particularly if it's been a while.

First, Alan Turing introduce what he called the "a-machine" for automatic machine. That machine is now called a Turing machine. To know what a Turing machine is, take a look at this video:

It might be hard to understand, but a machine like this can reproduce everything a computer can do. Here, we're not talking about speed, but the capacity to compute the same result. The most important Turing machine is a Universal Turing machine, i.e. a machine that can simulate any other Turing machine. Such a machine requires two inputs: a program and input data. Then the machine follow the instruction of the program, according to the input data, and produce an output.

This is exactly like a computer. You have the hardware (the machine), when it starts, it loads an operating system (the program) and you start typing on your keyboard, moving the mouse, receiving data from an internet connection (the input data). And in exchange, you get outputs in the form of images shown on your screen, data sent to a server or a document printed (an output).

Turing also showed the limitation of his machine. For example, that machine would not be able to compute the square root of two because the computation would never stop. If the machine cannot stop, it's considered non-computable. But, if we put a limit to the computation such as a maximum number of decimals, then it's computable because the machine will know when it's done.

Then, if something can be computed, how hard is it to compute it ? How much time and how much space ? Time, so given an input of size N, how much steps a Turing machine will need to solve it. Space, how much place on the tape (see the video above) is needed. On a Turing machine, the tape is considered as "infinite" but in practice, computers don't have infinite space and it takes time to do any operations. The paper covers the common complexity classes and problems related to these, specially the well know P vs. NP.

The paper also talk about the famous Halting Problem, i.e. there's no way to find whether a computer will eventually halt. A proof of the Halting Problem is given in the paper by using Cantor's diagonal method. That method can be used to show that even if there's an infinite number of natural numbers N, the cardinality (the size) of the set of real numbers R is greater than the cardinality of N. A concept that is weird the first time you read about it (I remember how surprised I was when I saw a proof for that) but very important to understand the foundation of Mathematics.

Have fun reading this paper!