turing100.nl


De Nederlandse Vereniging voor Logica &
Wijsbegeerte der Exacte Wetenschappen


Openbare Bibliotheek Amsterdam
Amsterdam, 5 October 2012

Organizers. Benedikt Löwe (Amsterdam & Hamburg) & Rineke Verbrugge (Groningen)
Antonina Kolokolova (St. John's, Canada):
How hard is proving hardness? A logic approach to barriers in complexity

In spite of much work over the years, the main questions in complexity theory such as P vs. NP remain unresolved. Is this question solvable at all? Is P vs. NP independent of some logical theory? Indeed, on a meta-level, there are several results that state that certain classes of techniques, including Turing's celebrated diagonalization, cannot be used to resolve these questions. Such results we call the "barriers" of complexity theory.

In this talk, we will survey some of the main such barriers (Relativization, Natural Proofs, Algebrization), and talk about how knowledge of such barriers helps evaluate (and, so far, discard) proposed proofs of P vs. NP. We will talk about the logic basis for such barriers, where a barrier means an independence of a logic theory.

Jan van Leeuwen (Utrecht, The Netherlands):
Turing's impact on understanding computation

In 1936 Alan Turing developed a formal notion of computability that would determine the future course of computer science. His understanding of universal machines was a basis for the design of general-purpose computers. In the 1950's Turing's model of computation and oracles proved crucial in understanding computational complexity, a notion that now underlies all our thinking of feasible algorithmics. His computational views were a beginning of the algorithmic lens that is transforming science today. The very development also led to models that may be more efficacious than Turing's for certain features of computation. Is there anything beyond Turing's machines?

Liesbeth De Mol (Gent, Belgium):
The mathematics of Homo Sapiens and its limitations: Emil Post's views on symbolic logic and computation

In 1936 Alonzo Church, Emil Post and Alan Turing published a paper in which they each proposed a thesis which is now known as the Church-Turing thesis. This talk will focus on Post's contributions in this context. It is shown how his method of "generalization through simplification" in the early 20s resulted in devices that are less intuitively appealing than Turing machines but nonetheless convinced him of the absoluteness of the unsolvability of certain decision problems and how it was this work that resulted in his criticism of Church's "definition" and the publication of his 1936 formulation 1. Some attention will be given to a program of generalizations of Post's thesis he announces in his 1936 paper and how this resulted in his modifications of the Turing machine concept as described in some letters to Church.

Andrew Hodges (Oxford, U.K.):
Alan Turing: Not only a beautiful mind

Alan Turing is often presented as the pure mathematical theorist, whose definition of computability gave rise to the idea of the modern electronic computer and to the vision of Artificial Intelligence. But his life and work was also full of application and action. He was always interested in the practical application of his ideas, and found enormous scope for his ambition first in the codebreaking work of the Second World War and then in the planning of his own computer project after 1945. His life involved drama and conflict, not least in the events at the end of his short life in 1954. These stories are brought together in the play 'Breaking the Code', to be performed later in the day, and I will explain the historical basis of the material presented on the stage.

Bennie Mols (Amsterdam, The Netherlands):
From Turing's Test to Turing's Tango

The Turing Test is centered around the question when it is fair to say that computers think. I argue that the Turing Test is outdated because it is too much based on imitating human intelligence. Imitating human intelligence has for a long time been the dominating aim in the field of artificial intelligence. On the basis of the fundamental differences between the (biological) human brain and the (electronic) computer brain I argue that the new challenge is to answer the question how artificial intelligence can best help mankind: what is the best tango pair of man and machine? Actually, my view goes back to the one of the American computer scientist Joseph Licklider, who, already in 1960, pioneered the thinking about what he called man-computer symbiosis. In our modern society man-computer symbiosis has become the dominant reality whereas artificial humanlike intelligence, as imagined by Turing and many others, is still nothing more than a dream.