Last time, I mentioned to have befriended Alan Turing. Who? You might fairly ask. Why? Those who already know him might add. Let me answer those questions.
Three years ago (pretty accurately), Leon and I were passing by Göttingen. It was our first bike trip, and along the road, we agreed this city was a must. Why? Because of all the genius mathematicians. For several generations, this city had all the ones that were admired to us and to every single person who ever studied maths, unanimously. Here, Gauss, Riemann, Hilbert, Klein, or Von Neumann, among many other mathematicians and also people of different fields (Max Born, Max Planck, Heisenberg, Schopenhauer, or even Bismark), developed their careers here. It is remarkable to mention that once, my Algebra teacher said that Hilbert was the last mathematician who knew everything about mathematics. Imagine the respect!
Hilbert, among many things, is famous for the challenges he gave to academia. In the year of 1900, he published a list of 23 problems for the next century, several of which still today have no solution and can be awarded with a million dollars if solved. Later, in 1928, Hilbert had an idea: to leave all mathematicians with no job. He wanted to know if mathematics are complete, consistent, and decidable, and he was sure of all three. The third case came to be known as the Entscheidungsproblem, or the decision problem, that is, given a statement of a logic language as input, and possibly a finite set of axioms, he wanted an algorithm that could answer if the given statement is universally valid. And this is precisely what mathematicians do: proving if a statement is valid or not!
Gödel arrived with the first strike to Hilbert’s hopes: he proved in 1930 against the first hypothesis with his famous incompleteness theorems 1. So after that, if there’s any chance the Entscheidungsproblem is not true, then we were really in need of a formal definition of an algorithm. Yes, an algorithm, that thing everybody knew of since the Greeks and al-Khwarizmi, the guy to whom we owe the word itself; but nobody ever defined it formally. Once Gödel said what he said, the race was on.
Six years later, three equivalent but independent solutions came at once, by Church, Gödel, and Turing. Beautiful, isn’t it? 2 But there will be plenty of opportunity to praise Church, he’s my favourite, and Gödel’s recursive functions are interesting in computability theory but will also be a topic for later. In the near future, I want to rant about Von Neumann, so for that, I need to talk about the one who actually made it far, Alan Turing. He said that an Algorithm is whatever a Turing Machine can compute.
One thing at a time
In his paper On Computable Numbers, with an application to the Entscheidungsproblem. Turing starts by defining a computing machine, analogous to how a man thinks, a construct capable of a finite number of conditions, something like the rules we can remember to apply; that has a tape divided in squares, theoretically infinite, where a symbol Sk might be written on each square; and it can only observe one square at a time, where it writes a new symbol (possibly the empty one, that is, deletion), or moves left or right to the adjacent squares. The symbol, together with the set of conditions, determine the configuration of the machine: a configuration gives deterministically a transformation to the next configuration. where is a finite set of states, is a Tape of Symbols, is the initial state, and is a deterministic transition function (much in relation to other kind of automatas).">3
Thus, a Turing machine, given an initial set of conditions (the initial set of axioms), and an input (the initial set of symbols), computes step-at-a-time a sequence of symbols, which, without loss of generality, might be of the set , in this way representing real numbers in binary form.
Note that a computable sequence is determined by a description of the initial configuration of a machine that computes it, but such a machine, having a finite number of operations (move right or left in the tape, print a symbol, or any finite combination of them), can be encoded by an integer (using a technique called Gödel numbering, which, by the way, is the same one that Gödel used to prove his incompleteness theorems), therefore proving that the set of Turing machines is countable, hence, not all numbers are computable [§5]. And by an analogous technique to Cantor’s diagonalization [§8], we know that there are things that can be defined and cannot be computed 4.
The brilliant conclusions
This definitions and basic results leads us to the important things that Turing proves in his brilliant paper:
The Universal Turing Machine, father of all computers
In §6 and §7, Turing affirms the existence of an almighty Universal Turing Machine, that is, a machine that can simulate every other machine, even those with bigger configuration or with multiple tapes and whatnot, and proves its existence by building such one 5. Given as an input the Standard Description (a transformation of the Gödel number) of a Turing Machine, followed by the arguments to this machine, it will compute exactly the same number than this previous machine. Note the transcendence of the idea: a UTM can be given as input a software (a Turing Machine), and the arguments to this software, and compute the whole program, and the constructions of this UTM are all equivalent. We are for the first time distinguishing Hardware from Software!
In §8, Turing elegantly proves that there cannot be any machine that, given the S.D. of any other machine, can decide if this machine is what he calls circular or circle-free, that is, if the machine can print its binary number ad infinitum (circle-free), or it gets stuck in a meaningless state (circular) 6. Immediately after, he proves that it’s actually worse: there cannot be a machine that can determine if another machine would even ever prints a given symbol 7.
Finally, in §11 (although it needed corrections a few months after), Turing goes on to prove that the Entscheidungsproblem has no solution, by showing that “Corresponding to each computing machine it we construct a formula and we show that, if there is a general method for determining whether is provable, then there is a general method for determining whether it ever prints 0″.
The Church-Turing thesis, or the “It’s all the same” thesis
At last, it must be remarked that in a further Appendix to the paper from a few months later, Turing gives one more important step: he proves the equivalence of his definition of computability with that of Church’s -definable, in what it came to be known later as the glorious Church-Turing thesis: together with later research from Church, Rosser, and others, they proved that all systems of computation developed where equivalent, and they hypothesised that any other system of computation will also be equivalent. Such thesis, although unproven, has so far stood the test of time, even in the advent of quantum computing. This is a topic you can truly expect me to come back to, it’s one of my favourites!
Next, Von Neumann will take over Turing’s papers, and design an architecture for a Turing complete machine, that is, a machine equivalent to the UTM, which is, a machine that can compute everything computable; i.e., essentially, a UTM.
- Listen to the observation that Philip Wadler gives on this fact :)
- This can be written in a formalized notation, as it is often done, for example as a 4-tuple where is a finite set of states, is a Tape of Symbols, is the initial state, and is a deterministic transition function (much in relation to other kind of automatas).
- Turing builds such one by giving the complete tables of configurations of his example, and many more have been build in literature afterwards, and I shall refer to them now in hope of keeping this post short.
- This is better known as the Halting Problem. Turing proves this by contradiction: if such a machine exists, then this machine can compute a self-referential paradox known to be incomputable.
- A generalisation of this was proven by Rice in 1951, saying that all non-trivial, semantic properties of programs are undecidable. Quite a big deal!