Symposium on 75 Years of Turing Machine and Lambda-Calculus

Karlsruhe, Germany, October 20-21, 2011

Keynote speakers

Henk Barendregt, Radboud University Nijmegen, The Netherlands

TITLE: The impact of the lambda calculus
ABSTRACT: The lambda calculus was conceived by Alonzo Church as a foundation for mathematics based on functions. The first formulation of the theory turned out to be inconsistent. Restricting to the computational part of mathematics the system became consistent. Church, helped by his student Kleene, made plausible that any computable function could be represented in lambda calculus. Using this, the first non-computable, but fully specified function could be defined. Alan Turing showed that lambda calculus calculations can be performed by a Turing machine and vice versa. Haskell Curry provided types for combinators, which was generalized by Church to a typing system for for lambda terms. Finally Dick de Bruijn used lambda terms to represent proofs. All this has led to the technology of functional programing and automated proof-verification. Functional programs are powerful, as one can use arbitrarily complex notions having a clear meaning with economic notation and interface. Machine verified mathematics brings the precision of the subject a quantum leap ahead. Examples of both will be given.

Christof Teuscher, Portland State University, USA

TITLE: A Modern Perspective on Turing's Unorganized Machines
ABSTRACT: Turing proposed unorganized machines and evolutionary search in a 1948 National Physical Laboratory (NPL) report entitled "Intelligent Machinery." These machines have very similar properties to what is today known as random Boolean networks, which have been used as models for genetic regulatory networks. In addition, the concept of (self-) assembling simple compute nodes that are interconnected in unstructured ways has gained significance with the advent of nano- and molecular electronics over the last decade. In this talk I will first present Turing's various original unorganized machines, extensions to them, and then relate the work to contemporary random Boolean networks, nano- and molecular electronics, and computing theory. I will illustrate that many of Turing's original ideas are more than ever current, influential, and deeply fascinating.

Wolfgang Thomas, RWTH Aachen University, Germany

TITLE: Computability in 1936: Pioneering Papers and Perspectives
ABSTRACT: In the first (and main) part of this talk, we review the emergence of a comprehensive concept of algorithm that preceeded (and culminated in) the pioneering work of Church, Turing, Kleene and Post: This remarkable ``confluence of ideas in 1936'' (R. Gandy) is based on integrated understanding of ``computation'', starting with Leibniz, where arithmetic and symbolic derivations of logic are merged. In the final part of the talk we discuss selected more recent developments that arose in computer science (but are also rooted in work of Church and Turing), in particular ideas of infinite and reactive computations.