International Symposium | Madrid, October 23 – 24, 2012

**Fundación Areces/Real Academia de Ciencias Exactas, Físicas y Naturales**

# Program

## Coordinators:

**Manuel de León**

Real Academia de Ciencias Exactas, Físicas y Naturales

Consejo Superior de Investigaciones Científicas (CSIC)

**David Ríos Insúa**

Real Academia de Ciencias Exactas, Físicas y Naturales

**Jesús María Sanz Serna**

Real Academia de Ciencias Exactas, Físicas y Naturales

Universidad de Valladolid

# TUESDAY, 23

MORNING SESSION

**09:30
**

**Opening**
**Miguel Ángel Alario y Franco**

Presidente de la Real Academia de Ciencias Exactas, Físicas y Naturales

**Manuel de León
David Ríos Insúa
Jesús M. Sanz-Serna**

Coordinadores del Simposio

**Federico Mayor Zaragoza**

Presidente del Consejo Científico

Fundación Ramón Areces

**09:45
José Manuel Sánchez Ron**

Real Academia Española

Real Academia de Ciencias Exactas, Físicas y Naturales

Universidad Autónoma de Madrid

**Title:** **Alan Turing: “The Person of the 20th century"**

**Abstract:** In December 1999, “Time” magazine chose Albert Einstein as "The Person of the Century". This was an entirely reasonable choice but, as I will argue in this talk, there are good reasons for Turing to have received this honor, or at least to have been considered for it. One such reason is his purely scientific work, which stems from the greatest mathematical tradition. That work had a direct influence on the development of mathematics itself, and was finally also instrumental in shaping a new (technological) world, both in the calculation and handling of information as well as in giving rise a new manner of establishing social relations. An example on such more “applied”, or mundane, regard is in Turing’s contributions to the deciphering of secret codes during the Second World War, which in a somewhat (metaphorical) sense may be regarded as a new tool for undermining personal privacy, that essential civil right whose denial by British society finally ruined his life.

**10:45
Ramón López de Mántaras**

Recipient of the 2011 AAAI Robert S. Engelmore Award

Profesor de Investigación del CSIC

**Title:** **The AI Journey: The road traveled and the (long) road ahead**

**Abstract: **In this talk I will first briefly remind what Artificial Intelligence (AI) is about, distinguishing between strong and weak AI. Then I will summarize some of the many impressive results we have achieved in weak AI along the road traveled so far, including some specific results in robotics and music obtained at the IIIA-CSIC. Next I will describe some of the future challenges to be faced along the (long) road we still have ahead of us, with an emphasis on the so-called "integrated systems" incorporating perception, learning, reasoning, communication and action and why the Turing test is not suitable for such systems. Finally, I will comment on the importance of interdisciplinary research for building these integrated systems, which are a stepping stone towards strong AI, and give some examples of results in interdisciplinary research which are relevant for building humanoid robots with artificial skin, artificial muscles, and artificial cartilages.

**11:45
Break**

**12:00
Nigel P. Smart**

University of Bristol, United Kingdom

**Title:** **Provable Security**

**Abstract: **Turing's test is about whether a person at a remote location can determine whether they are communicating with a real person or a computer. A similar idea is used in cryptography: An adversary needs to determine whether it is interacting with a real system or a simulation. If he cannot tell the difference then the system is called "secure". In this talk I will provide an introduction to this modern approach to cryptography.

**12:45
Froilán Martínez Dopico**

Universidad Carlos III de Madrid

**Title:** **Alan Turing and the origins of modern Gaussian elimination**

**Abstract: **The solution of a system of linear equations is by far the most important problem in Applied Mathematics. It is important in itself and because it is an intermediate step in many other relevant problems. Gaussian elimination is nowadays the standard method for solving this problem numerically on a computer and it was the first numerical algorithm to be subjected to a rounding error analysis. In 1948, Alan Turing published a remarkable paper on this topic: ``Rounding-off errors in matrix processes’’ (Quart. J. Mech. Appl. Math. 1, 287-308). In this paper, Turing formulated Gaussian elimination as the matrix LU factorization and introduced the “condition number of a matrix”, both of them fundamental notions of modern Numerical Analysis. In addition, Turing presented an error analysis of Gaussian elimination that improved previous analyses and deeply influenced the definitive analysis developed by James Wilkinson in 1961. Alan Turing’s work on Gaussian elimination appears in a fascinating period for modern Numerical Analysis. Other giants of Mathematics, such as John Von Neumann, Herman Goldstine, and Harold Hotelling were also working in the mid-1940s on Gaussian elimination. The goal of these researchers was to find an efficient and reliable method to solve systems of linear equations in the recently invented “automatic computers”. At that time, it was not clear at all whether Gaussian elimination was a right choice or not. The purpose of this talk is to revise, at an introductory level, Alan Turing’s contribution to the analysis of Gaussian elimination, its historical context, and its influence on modern Numerical Analysis.

**13:30
Break**

# EVENING SESSION

**16:00
Leslie Valiant**

Nevanlinna Prize 1986, Knuth Prize 1997, Turing Award 2010

Harvard University, USA

**Title:** **Biological Evolution as a Form of Learning**

**Abstract: ***Living organisms function according to protein circuits. Darwin's theory of evolution suggests that these circuits have evolved through variation guided by natural selection. However, the question of which circuits can so evolve in realistic population sizes and within realistic numbers of generations has remained essentially unaddressed. We suggest that computational learning theory offers the framework for investigating this question, of how circuits can come into being adaptively from experience, without a designer. We formulate evolution as a form of learning from examples. The targets of the learning process are the functions of highest fitness. The examples are the experiences. The learning process is constrained so that the feedback from the experiences is Darwinian. We formulate a notion of evolvability that distinguishes function classes that are evolvable with polynomially bounded resources from those that are not. The dilemma is that if the function class, say for the expression levels of proteins in terms of each other, is too restrictive, then it will not support biology, while if it is too expressive then no evolution
algorithm will exist to navigate it. We shall review current work in this area.*

**17:00
Miguel Ángel Martín Delgado**

Universidad Complutense de Madrid

**Title: Alan Turing and the Limits of Computation**

**Abstract:***Computability studies which problems can be computed and which cannot be computed. This goes to the very limits of what is knowable. Turing developed the theory of computability by finding mechanical procedures to compute things, and also devised appropriate definitions of what algorithms are. This is the way Mathematics must be understood at a fundamental level with axioms. Eventually, this leads to the very notion of mathematical creativity. Turing showed what things we can compute in a very precise and universal way, but he also proved that there are things that we cannot compute. After explaining the limits of computability, including examples, the natural question is: can we go beyond? This depends on what is called the Turing barrier. Some alternatives to Turing computation are discussed, including quantum computation. Turing's work is given some historical perspective with respect to some of his precursors, contemporaries and mathematicians who developed his ideas farther.*

**17:45
Break**

**18:00
Miguel Ángel Herrero**

Universidad Complutense de Madrid

**Title**: **Mathematics and biology: a difficult relation**

* Abstract*:

*In 1952 Alan Turing authored an article on the chemical basis or morphogenesis (The chemical basis of morphogenesis. Phil. Trans. Roy. Soc. London B 37-72.237), his only published work related with Biology. His opening words tersely describe his approach as follows: It is suggested that a system of chemical substances, called morphogens, reacting together and diffusing through a tissue, is adequate to account for the main phenomena of morphogenesis. Such a system, although it may originally be quite homogeneous, may later develop a pattern or structure due to an instability of the homogeneous equilibrium, which is triggered off by random disturbances. Turing was not the first to use mathematical methods to deal with biological problems. Moreover, his approach remained unnoticed, or was plainly rejected by many biologists at that time, and rapidly fell into oblivion. His proposals were independently rediscovered about twenty years later, only to meet with a hostile reception among leading developmental biologists. An argument often used in the resulting exchanges is that Life is too complex to be reduced to a mathematical formulation. However, such misgivings have not prevented Ecology and Mathematics from mutually benefiting from their respective discoveries during the XX century. In this lecture, I will briefly describe some striking aspects of the exciting, if difficult, relation between Mathematics and Biology throughout history. Particular attention will be paid to developments that have taken place during the last half century, and which can be related, at least in part, to Turing´s work.*

**18:45**

**Josep Díaz**

Premio Nacional de Informática 2011

Universitat Politecnica de Catalunya

**Title:** **Alan Turing: the link from Leibniz to Gödel**

**Abstract:***The talk is split into two parts. In the first part, we survey the quest for a universal procedure to solve problems. In the second, starting from the letter from Gödel to von Neumann, we survey the meaning of unfeasibility through the truncated Entscheidungsproblem, and give examples of problems from different fields where it seems difficult to obtain efficient procedures.*

# WEDNESDAY, 24

MORNING SESSION

**9:30
Gerald E. Sacks**

Harvard University, USA

**Title:**** Two Lemmas Of Infinitary Logic**

**Abstract:***Applications of Goedel's condensation method to infinitary logic.*

**10:30
Ignacio Luengo**

Universidad Complutense de Madrid

**Title:** **Turing and Enigma**

**Abstract: ***Turing’s work was vital for deciphering the messages sent by the German Navy’s Enigma machine in the Second World War. His decisive contribution together with the rest of the work carried out at Bletchley Park, were kept secret by the British Government until the mid-1970s. We reconsider Turing’s work on Enigma from an historical cryptographic point of view.*

**11:15
Break**

**11:30
Pedro Bernal Gutiérrez**

Teniente General del Ejército del Aire

Ex-director del Centro Superior de Estudios de la Defensa Nacional (CESEDEN)

**Title: ****Turing and Cryptography in the Second World War**

**Abstract: ***Communications acquired a crucial importance during the Second World War. In order to protect their flow of information from the allied powers, Germany developed highly complex encryption equipment and procedures, such as the ENIGMA machine. The allies themselves, and Great Britain in particular, took up an undercover cryptological battle that was to prove decisive for the outcome of the war. Turing played a key role in this struggle with his contribution of original ideas in the field of mathematical logic and computation.*

**12:30
David Pearce**

Universidad Politécnica de Madrid

**Title:**** Logic, Computation, Knowledge Representation and Problem Solving**

**Abstract:***Alan Turing laid the foundation for the beginning of a long standing partnership between logic and the science of computation. Since the 1970s this partnership has expanded, deepened and diversified in many new directions. Logic became an inspiration for designing programming languages, a tool for specification and semantics, and an instrument for verifying the correctness of software. It has also provided languages for reconstructing human knowledge and for modeling and automating many human reasoning tasks. In this talk I discuss some of the current work in artificial intelligence that involves the use of logic for programming, problem solving, knowledge reconstruction and the analysis of artificial societies.*

**13:15
Break**

# EVENING SESSION

**16:00
Bruce Wilcox**

Loebner Prize 2010 y 2011

Telltale Games, USA

**Title**: **Making it real: Loebner-winning chatbot design**

**Abstract: **For the last three years, chatbots of my wife and I have participated in the Loebner Prize in Artificial Intelligence, coming in 1st twice and 2nd once, with a different persona each year. One of them even fooled a human judge. A world-class chatbot should tell the story of its life, have a consistent personality, and respond emotionally. It takes a lot of script. And it takes a powerful engine designed to support natural language processing in a variety of ways and make it relatively easy to author all that script. This talk discusses ChatScript, the open-source Natural Language scripting language and engine running our bots. And it looks at how we construct chatbot personalities and what we have learned over time.

**17:00
Luis M. Laíta**

Catedrático Emérito de la Universidad Politécnica de Madrid (UPM), Profesor Emérito de la

Universidades Cardenal Cisneros y CEU, Madrid.

Real Academia de Ciencias Exactas, Físicas y Naturales

**Title: **

**George Boole, a precursor of today’s Computer Algebra based Demonstrations**

**Abstract:***In the monograph “The Genesis of Boole´s Logic, its History and a Computer Exploration” (L. M. Laita, Memories of the Royal Academy of Sciences of Madrid, Mathematics, Volume XXXIII (2005), I studied the historical, philosophical and scientific influences led by the great English mathematician and logician George Boole. The question is: why in this short talk are Alan Turing (born 1912, died 1954) and George Boole (born 1815, died 1864) linked? In outline, the answer to the question “why” is that their works can be considered as intimately related to what today is known as “Symbolic Computation”. The computation model provided by Turing Machines, as well as their more modern computation models, proved to be equivalent in some crucial ways to universal Turing machines, and can be considered Symbolic Computation, as they are based on strict programs and strict concepts of the word “algorithm”. The link with George Boole is established on our claim that his algebraic logic demonstrations, based on a methodology called “the method of Separation of Symbols”, first used in France by, among others, Lagrange, Laplace and Arbogast, was later used in Great Britain (by, for instance, the Scottish mathematician Duncan F. Gregory) and was subsequently developed fully and in-depth by Boole. More importantly, as we will try to show in our exposition, Boole’s use of the method of separation of symbols can be extended to what now is known as “Symbolic Computation”; in particular, but not exclusively, dealings with symbolic logic proofs based on Buchberger´s Gröbner bases. As we will illustrate, this can be used in what in Artificial Intelligence are known as “expert systems”. As far as we know, neither Boole nor Turing ever referred to “Artificial Intelligence”, but we believe that some of their thoughts were directly related with this topic.*

**17:45
Break**

**18:00
Joan Bagaria i Pigrau**

ICREA Research Professor, Universitat de Barcelona

**Title:** **On Turing's legacy in mathematical logic and the foundations of mathematics**

**Abstract: ***While 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 my talk I will focus on some of the ideas and problems arising from his work in these areas, such as the analysis of the structure of Turing degrees and the development of ordinal logics, which have been of continuous interest up to the present day and which still present formidable mathematical challenges.*

**19:00
Closing of the symposium**