Date: Sun, 11 May 1997 16:44:56 +0200 From: Marc Daumas To: Secretariat DMI , Tous LIP , Profs MIM , Eleves MIM94 , Eleves MIM95 , Eleves MIM96 , Hughette Ortega Subject: Seminaire d'Informatique des Eleves [13/05] ATTENTION ATTENTION ATTENTION ATTENTION ATTENTION ATTENTION ATTENTION CHANGEMENTS CHANGEMENTS CHANGEMENTS CHANGEMENTS CHANGEMENTS CHANGEMENTS DEBUT DU SEMINAIRE A 14 HEURES --- THEOREME D'INCOMPLETUDE DE GOEDEL Bonjour, Pour le dernier seminaire d'informatique des eleves avant les revisions, puis les stages, et enfin les vacances, nous recevrons Vladimir Uspensky directeur du Department of Mathematical Logics and Theory of Algorithms de l'universite de Lomonosov a Moscou. Vladimir Uspensky est actuellement invite au LIP ou il collabore avec l'equipe Automates Cellulaires et Pavages. Nous aborderons, en anglais, un aspect particulier du bien celebre theoreme d'incompletude de Goedel. Comme la fois derniere, pour laisser un peu de temps aux etudiants qui voudraient aller au seminaire d'histoire de sciences, le seminaire d'informatique des eleves commencera a 14 heures. Nous restons dans l'amphi B. Titre ----- Gödel's incompleteness theorem: an algorithmic approach to a foundation problem Résumé ------ The celebrated Gödel incompleteness theorem says that for any reasonable formalisation of arithmetic there is a statement wich is true but unprovable in that formalisation. It is a fundation problem, and, of course, the notion of truth needs to be discussed (and the notion of provability too). The original proof of that theorem was presented by Gödel himself (and then reproduced in many books) based on the idea of self-reference, that is of ability of a language to express something about itself. But it can be noticed that the theorem can be also inferred from some basic facts of the general theory of algorithms. In the talk, the said connection between the Gödel theorem and algorithmic theory will be exposed. Références ---------- V. A. Uspensky, Goedel's Incompleteness Theorem. Theoretical Computer Science, vol. 130 (1994), no. 2, pp. 239--319 (aussi present en tant que livre a la bibliotheque d'info nouveaute). -- Marc Daumas - Marc.Daumas@ENS-Lyon.Fr - http://www.ens-lyon.fr/~daumas LIP - ENS Lyon - 46, allee d'Italie - 69364 Lyon Cedex 07 - FRANCE Ph : (+33) 4 72 72 82 29 - Fx : (+33) 4 72 72 80 80