Last time, I men­tioned 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 accur­ately), 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 geni­us math­em­aticians. For sev­er­al gen­er­a­tions, this city had all the ones that were admired to us and to every single per­son who ever stud­ied maths, unan­im­ously. Here, Gauss, Riemann, Hilbert, Klein, or Von Neumann, among many oth­er math­em­aticians and also people of dif­fer­ent fields (Max Born, Max Planck, Heisenberg, Schopenhauer, or even Bismark), developed their careers here. It is remark­able to men­tion that once, my Algebra teach­er said that Hilbert was the last math­em­atician who knew everything about math­em­at­ics. Imagine the respect!

The Entscheidungsproblem

Hilbert, among many things, is fam­ous for the chal­lenges he gave to aca­demia. In the year of 1900, he pub­lished a list of 23 prob­lems for the next cen­tury, sev­er­al of which still today have no solu­tion and can be awar­ded with a mil­lion dol­lars if solved. Later, in 1928, Hilbert had an idea: to leave all math­em­aticians with no job. He wanted to know if math­em­at­ics are com­plete, con­sist­ent, and decid­able, and he was sure of all three. The third case came to be known as the Entscheidungsproblem, or the decision prob­lem, that is, giv­en a state­ment of a logic lan­guage as input, and pos­sibly a finite set of axioms, he wanted an algorithm that could answer if the giv­en state­ment is uni­ver­sally val­id. And this is pre­cisely what math­em­aticians do: prov­ing if a state­ment is val­id or not!

Gödel arrived with the first strike to Hilbert’s hopes: he proved in 1930 against the first hypo­thes­is with his fam­ous incom­plete­ness the­or­ems ¹. So after that, if there’s any chance the Entscheidungsproblem is not true, then we were really in need of a form­al defin­i­tion of an algorithm. Yes, an algorithm, that thing every­body knew of since the Greeks and al-Khwarizmi, the guy to whom we owe the word itself; but nobody ever defined it form­ally. Once Gödel said what he said, the race was on.

Six years later, three equi­val­ent but inde­pend­ent solu­tions came at once, by Church, Gödel, and Turing. Beautiful, isn’t it? ² But there will be plenty of oppor­tun­ity to praise Church, he’s my favour­ite, and Gödel’s recurs­ive func­tions are inter­est­ing in com­put­ab­il­ity the­ory but will also be a top­ic for later. In the near future, I want to rant about Von Neumann, so for that, I need to talk about the one who actu­ally made it far, Alan Turing. He said that an Algorithm is whatever a Turing Machine can com­pute.

One thing at a time

In his paper On Computable Numbers, with an applic­a­tion to the Entscheidungsproblem. Turing starts by defin­ing a com­put­ing machine, ana­log­ous to how a man thinks, a con­struct cap­able of a finite num­ber of con­di­tions, some­thing like the rules we can remem­ber to apply; that has a tape divided in squares, the­or­et­ic­ally infin­ite, where a sym­bol S_k might be writ­ten on each square; and it can only observe one square at a time, where it writes a new sym­bol (pos­sibly the empty one, that is, dele­tion), or moves left or right to the adja­cent squares. The sym­bol, togeth­er with the set of con­di­tions, determ­ine the con­fig­ur­a­tion of the machine: a con­fig­ur­a­tion gives determ­in­ist­ic­ally a trans­form­a­tion to the next con­fig­ur­a­tion. ³

Thus, a Turing machine, giv­en an ini­tial set of con­di­tions (the ini­tial set of axioms), and an input (the ini­tial set of sym­bols), com­putes step-at-a-time a sequence of sym­bols, which, without loss of gen­er­al­ity, might be of the set $latex \{0, 1, x, \emptyset\}$, in this way rep­res­ent­ing real num­bers in bin­ary form.

Note that a com­put­able sequence $latex \gamma$ is determ­ined by a descrip­tion of the ini­tial con­fig­ur­a­tion of a machine that com­putes it, but such a machine, hav­ing a finite num­ber of oper­a­tions (move right or left in the tape, print a sym­bol, or any finite com­bin­a­tion of them), can be encoded by an integer (using a tech­nique called Gödel num­ber­ing, which, by the way, is the same one that Gödel used to prove his incom­plete­ness the­or­ems), there­fore prov­ing that the set of Turing machines is count­able, hence, not all num­bers are com­put­able [§5]. And by an ana­log­ous tech­nique to Cantor’s diag­on­al­iz­a­tion [§8], we know that there are things that can be defined and can­not be com­puted ⁴.

The brilliant conclusions

This defin­i­tions and basic res­ults leads us to the import­ant things that Turing proves in his bril­liant paper:

The Universal Turing Machine, father of all computers

In §6 and §7, Turing affirms the exist­ence of an almighty Universal Turing Machine, that is, a machine that can sim­u­late every oth­er machine, even those with big­ger con­fig­ur­a­tion or with mul­tiple tapes and what­not, and proves its exist­ence by build­ing such one ⁵. Given as an input the Standard Description (a trans­form­a­tion of the Gödel num­ber) of a Turing Machine, fol­lowed by the argu­ments to this machine, it will com­pute exactly the same num­ber than this pre­vi­ous machine. Note the tran­scend­ence of the idea: a UTM can be giv­en as input a soft­ware (a Turing Machine), and the argu­ments to this soft­ware, and com­pute the whole pro­gram, and the con­struc­tions of this UTM are all equi­val­ent. We are for the first time dis­tin­guish­ing Hardware from Software!

Entscheidungsproblem revisited

In §8, Turing eleg­antly proves that there can­not be any machine that, giv­en the S.D. of any oth­er machine, can decide if this machine is what he calls cir­cu­lar or circle-free, that is, if the machine can print its bin­ary num­ber ad infin­itum (circle-free), or it gets stuck in a mean­ing­less state (cir­cu­lar) ⁶. Immediately after, he proves that it’s actu­ally worse: there can­not be a machine that can determ­ine if anoth­er machine would even ever prints a giv­en sym­bol ⁷.

Finally, in §11 (although it needed cor­rec­tions a few months after), Turing goes on to prove that the Entscheidungsproblem has no solu­tion, by show­ing that “Corresponding to each com­put­ing machine $latex \mathcal{M}$ it we con­struct a for­mula $latex Un(\mathcal{M})$ and we show that, if there is a gen­er­al meth­od for determ­in­ing wheth­er $latex Un(\mathcal{M})$ is prov­able, then there is a gen­er­al meth­od for determ­in­ing wheth­er 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 fur­ther Appendix to the paper from a few months later, Turing gives one more import­ant step: he proves the equi­val­ence of his defin­i­tion of com­put­ab­il­ity with that of Church’s $latex \lambda$-definable, in what it came to be known later as the glor­i­ous Church-Turing thes­is: togeth­er with later research from Church, Rosser, and oth­ers, they proved that all sys­tems of com­pu­ta­tion developed where equi­val­ent, and they hypo­thes­ised that any oth­er sys­tem of com­pu­ta­tion will also be equi­val­ent. Such thes­is, although unproven, has so far stood the test of time, even in the advent of quantum com­put­ing. This is a top­ic you can truly expect me to come back to, it’s one of my favourites!

Coming soon

Next, Von Neumann will take over Turing’s papers, and design an archi­tec­ture for a Turing com­plete machine, that is, a machine equi­val­ent to the UTM, which is, a machine that can com­pute everything com­put­able; i.e., essen­tially, a UTM.

---

1. https://www.ii.uni.wroc.pl/~kosciels/pi/canon00-goedel.pdf
2. Listen to the obser­va­tion that Philip Wadler gives on this fact :)
3. This can be writ­ten in a form­al­ized nota­tion, as it is often done, for example as a 4‑tuple $latex M_T = \langle S, \Sigma, q_0, \delta \rangle$ where $latex S$ is a finite set of states, $latex \Sigma$ is a Tape of Symbols, $latex q_0$ is the ini­tial state, and $latex \delta$ is a determ­in­ist­ic trans­ition func­tion $latex \delta : S \mathbin{x} \Sigma \righ­tar­row ( S \cup \textit{halt}) \mathbin{x} (\Sigma \cup \{L, R\})$  (much in rela­tion to oth­er kind of automatas).
4. https://en.wikipedia.org/wiki/Georg_Cantor%27s_first_set_theory_article
5. Turing builds such one by giv­ing the com­plete tables of con­fig­ur­a­tions of his example, and many more have been build in lit­er­at­ure after­wards, and I shall refer to them now in hope of keep­ing this post short.
6. This is bet­ter known as the Halting Problem. Turing proves this by con­tra­dic­tion: if such a machine exists, then this machine can com­pute a self-ref­er­en­tial para­dox known to be incomputable.
7. A gen­er­al­isa­tion of this was proven by Rice in 1951, say­ing that all non-trivi­al, semant­ic prop­er­ties of pro­grams are unde­cid­able. Quite a big deal!