Vendredi 27 octobre 2017 de 14h00 à 15h30
Amphi Bacchus, Bât M 5 avenue Paul Langevin, Cité scientifique à Villeneuve d’Ascq
Ce colloquium est joint avec le département de philosophie.
What is the concept of computation ?
Abstract: The Church-Turing Thesis asserts that particular mathematical notions are adequate to represent informal notions of effective culculability or mechanical decidability. I first sketch contexts that called for such adequate mathematicla notions, namely, problems in mathematics (e.g, Hilbert’s 10th problem), decision problems in logic (e;g, the Entscheidungsproblem for first-order logic), and the precise characterization of formality (for the general formulation of Göde’s incompleteness theorems).
The classical approach to the effective calculability of number theoretic functions led, through Gödel and Church, to a notion of computability in logical calculi and metamathematical absoluteness theorems. The classical approach to the mechanical decidability of problems concerning syntactic configurations led, through Turing and Post, to a notion of computability in formal caculi (canonical systems) and metamathematical representation theorems.
Particular featurs of formal calculi motivate the formulation of an abstract concept of a computable dynamical system. this concept articulates finiteness and localituy conditions that are satisfied by the standard concerte notions of computation. A representation theorem can be established : Turing machines can simulate the computations of any concrete system falling under the abstract concept. I sketch a generalization of this approach to obtain computableparallel dynamical systems. Some applications will conclude my discussion.
√ Bio : His research in mathematical logic is broadly concerned with the Foundations of Mathematics and focuses in particular on proof theoretic investigations. It is complemented by work in the History of Modern Logic & Mathematics and in the Philosophy of Mathematics. The historical research has led to participation in editorial projects, which have helped to shed a new and distinctive light on the development of logic in the first half of the 20th century; these projects concern Paul Bernays, David Hilbert and Kurt Gödel.
He studied mathematics, physics and logic at universities in Germany (Berlin and Münster). After completing his graduate studies at Stanford University, he taught in the Department of Philosophy at Columbia University. Since 1985, he has been on the faculty at Carnegie Mellon University. He was co-founder of the interdisciplinary program in Pure and Applied Logic that is joint with Computer Science and Mathematics. From 1994 to 2005, he was Head of the Philosophy Department. In 1996, he founded the Laboratory for Symbolic & Educational Computing (LSEC) and have been directing it since that time, first with Richard Scheines as co-director and since 2005 with Teddy Seidenfeld as co-director.