Alan Turing es conocido sobre todo por sus contribuciones a las ciencias de la computación y a la criptografía, pero el impacto de su trabajo en la teoría general de las funciones computables (teoría de la recursión) y en los fundamentos de la matemática es de igual importancia. En este artículo damos una breve introducción a algunas de las ideas y problemas matemáticos surgidos de la obra de Turing en estas áreas, como el análisis de la estructura de los grados de Turing y el desarrollo de las lógicas ordinales.

While Alan Turing is best known for his work on computer science and cryptography, his impact on the general theory of computable functions (recursion theory) and the foundations of mathematics is of equal importance. In this article we give a brief introduction to some of the ideas and problems arising from Turing’s work in these areas, such as the analysis of the structure of Turing degrees and the development of ordinal logics.

*This is the written version of the talk with the same title delivered at the “International Symposium: The Legacy of Alan Turing”, held at the Fundación Ramón Areces, Madrid, on 23-24 October 2012.

David Hilbert (1862-1943), one of the most prominent mathematicians of his time, developed in the 1920's an ambitious programme for laying the foundations of mathematics

The need for formalization and strict derivation of mathematical statements according to explicitly stated logical rules was the only way, according to Hilbert, to be able to reason about

A

An

A finite set of

The formal system is not arbitrary, for it is intended to model mathematics in the following sense (Hilbert,

In a famous passage from his

Thus, it appears that Hilbert was convinced that his proposed system for the foundation of mathematics, or perhaps some extension of it, could be

Further, as an essential requirement for the legitimacy of any formal system strong enough for the foundation of mathematics (hence involving ideal elements), Hilbert wanted a proof of consistency, a proof that should be obtained by purely finitary means (i.e., not involving ideal elements), for he believed that only finitary statements are firmly grounded. Thus, the system should be provably

And the proof should be finitistic (hence arithmetical).

As Hilbert (

He, however, does not give any argument of why this is so. Yet he seemed to believe that, in addition to being complete and consistent, some formal system based on first-order logic and strong enough to encompass all ordinary mathematics could be

The existence of such an effective method (for any given formal system) is known as the

In the autumn of 1930, in his retirement address to the Society of German Scientists and Physicians, in Königsberg, and in response to the Latin maxim:

Thus, Hilbert was still holding onto the belief that every mathematical problem could be solved, presumably by deriving it from a complete formal system. Ironically, just the day before, during the Conference on Epistemology held jointly with the Society meetings, Kurt Gödel had informally announced his incompleteness result, which represented a fatal blow to Hilbert’s program, at least in the form outlined above. Gödel’s First Incompleteness Theorem asserts that

The amount of arithmetic needed is indeed a very small fragment of Peano’s Arithmetic. For instance, Robinson’s finitely-axiomatizable theory

The second incompleteness theorem is even more dramatic.

that expresses the consistency of the system is not provable in the system itself. Formally,

In this case, the finitely-axiomatizable fragment of Peano’s Arithmetic known as Σ_{1}-Induction suffices. Thus, no reasonable formal system for mathematics (not even for a basic fragment of arithmetic) can be both consistent and complete.

But how about the

In the 1930’s, Princeton University was the centre of mathematical logic in the United States. The Institute for Advanced Studies (IAS), created in 1930 and housed in the same building as the Department of Mathematics, the old Fine Hall, attracted first-rate mathematicians such as Oswald Veblen and John von Neumann, as well as Albert Einstein. Kurt Gödel visited the IAS on several occasions, giving a series of lectures in 1934 on his incompleteness results, and becoming a permanent member in 1940. In Princeton, Alonzo Church (1903-1995) was the leading figure in Logic. Together with his bright students John Barkley Rosser and Stephen Kleene, Church developed the

In the meantime, Gödel had introduced his class of computable functions, known as the Gödel-Herbrand

There is a notion of

As a consequence, Church obtains the following:

That is, there is no effectively computable function on formulas

But is this really a solution to the Entscheidunsproblem? Church’s solution relies on Church’s Thesis, which identifies computable and recursive (as well as

Alan Matthison Turing (1912-1954)

The analysis of an (idealized)

The description of a machine analogue of the human computer: the automatic machines, or a-machines, now known as

As is well-known, a Turing Machine (TM) is a device consisting of a

When set in motion starting from a blank tape, a TM produces a sequence of binary numbers. If the sequence is infinite, the machine is called

A proof of the existence of a

A Universal Turing Machine (UTM) is a TM that can be used to compute any computable sequence. That is, if the UTM

A proof of the non-computability of the

The Halting Problem is the problem of determining whether an arbitrary TM is circle-free or not. Turing proves that there is no circle-free TM that will compute the sequence of all codes of circle-free TM’s. Should such a TM exist, there would be a TM _{n}_{n}_{m}(m)_{m}(m)

Turing also proves that there is no TM that, given the code of a TM

. A “proof” that the

Of course, a real (i.e., mathematical) proof of this assertion is not possible, and so the arguments given by Turing are of three kinds:

(a) A direct appeal to intuition.

(b) A proof of the equivalence between computable (i.e., computable by a TM) and effectively calculable (or recursive).

(c) Giving examples of a large class of functions which are computable.

.
A negative solution to the

For each TM

It is hard to overestimate the importance of Turing’s paper, both for the foundations of mathematics and the theory of computation. With regards to foundations, it is worth noticing Gödel’s enthusiastic reaction (see Gödel,

Thus, while Turing (and Chuch, independently) had given a negative solution to the Hilbert-Ackermann version of the Entscheidungsproblem, hence yet a further blow to Hilbert’s Program, he had given for the first time, according to Gödel, a precise definition of the concept of formal system, thus opening the door to a possible revision of the Program.

On the recommendation of Max Newman, Turing got accepted as a graduate student at Princeton. In a letter to Church, Newman writes:

Turing completed his doctoral dissertation in two years. His thesis, presented in 1938, was entitled

_{1}_{2}_{1}_{ω}_{1}, L_{2}_{α}

The following is an example of the formal systems (ordinal logics) studied in his thesis. Let _{0}_{k}_{k+1}_{k} + _{k}_{ω}_{k<ω} _{k}_{ω+1}_{ω}_{ω}_{α+1}_{α}_{α}_{α}

^{a} is a notation for the successor of |^{e} is a notation for the supremum of the sequence |_{n}_{n}

Observe that the set _{O}

The system _{a}_{aєo}_{a}_{a}_{a}_{1}^{0}, that is, of the form ∀_{1}^{0} statement could be decided by some _{a}_{1}^{0} statements:

_{1}^{0} sentence φ, there exists _{a}

The proof of the Theorem is quite ingenious (see Feferman, _{1}^{0} sentence _{a}

In section 3 of the Thesis, Turing goes on to consider what he calls _{2}^{0}), namely, those of the form ∀_{2}^{0} statements; not surprisingly, for S. Feferman showed in 1962 that this is impossible (Feferman, _{2}^{0}, Turing introduces the notion of computation relative to an

_{2}^{0}] problems; a kind of oracle as it were. [...] With the help of the oracle we could form a new kind of machine (call them o-machines), having as one of its fundamental processes that of solving a given number-theoretic problem. (Turing,

Turing then defines precisely the notion of _{2}^{0} statement is easily seen to be equivalent to one of the form “M is a circle-free TM”, if _{2}^{0} formula, then it follows that the Halting Problem for _{2}^{0}.

Although the notion of

The theory of computability relative to an oracle, was developed by Emil Post (1897-1984) and Kleene into the theory of degrees of unsolvability, also known as

A set of natural numbers _{T} B.

Two sets of natural numbers _{T} B_{T} B_{T} A

A _{T}_{T}

The analysis of the structure of ^{ℵ0}-many degrees; each degree has only countably-many predecessors; ^{ℵ0}-many incomparable degrees; every two degrees have a least upper bound, but they need not have a greatest lower bound; etc.

The structure of

In section 11 of the Thesis, entitled “The purpose of ordinal logics”, Turing singles out two faculties of mathematical reasoning he calls

Whereas

By the introduction of formal logic, the need for intuition is

But since it is not possible to find a formal logic that would eliminate the use of intuition completely, because of Gödel’s incompleteness, one is naturally forced to consider “non-constructive” systems of logic, such as ordinal logics. With an ordinal logic we are in a position to prove theorems by the intuitive steps of recognizing a number as a notation for an ordinal, and the mechanical (yet requiring ingenuity) steps of applying the logical rules.

Further study of ordinal logics, rechristened as

The work was partially supported by the Spanish Ministry of Science and Innovation under grant MTM2011-25229, and by the

In the 1920’s, many other people collaborated either jointly with Hilbert or independently in the development of what is now known as

Address delivered in München on 4 June 1925 at a meeting organized by the Westphalian Mathematical Society to honor Weierstrass.

A language having only two unary predicate symbols, or just one binary relation symbol suffices.

We refer to A. Hodges’ excellent biography (Hodges,

A unary relation, or predicate, i.e., a set of natural numbers, is computable if and only if its characteristic function is computable.