Le Collège Belgique / Programme des leçons futures / Toutes les leçons / L'indécidabilité: conséquences dans les mathématiques et l'informatique

 

L'indécidabilité: conséquences dans les mathématiques et l'informatique

Mercredi 21/04/2010 – 17h00

Les ordinateurs sont présents dans notre vie quotidienne, et sont utilisés pour réaliser un nombre toujours plus important de tâches différentes. Il semblerait donc que les domaines d'application de l'informatique soient illimités, et que les ordinateurs ont une capacité sans borne à résoudre des problèmes. Pourtant, il est bien connu depuis les travaux d'Alan Turing (années 1920, donc bien avant la construction des premiers ordinateurs) que l'informatique est confrontée à une limite théorique intrinsèque, appelée indécidabilité. Cette notion stipule qu'il existe des problèmes que les ordinateurs ne peuvent pas résoudre. Ce cours-conférence a pour but de donner une introduction vulgarisée à ces notions théoriques fondamentales, et de montrer leur influence considérable sur tous les domaines de la recherche en informatique.

On commencera par étudier la notion de problème (comment la définir de manière rigoureuse), et la notion d'algorithme, c'est-à-dire de solution informatique à un problème donné. Cette introduction sera placée dans son contexte historique (on verra notamment les rapports avec la logique et le célèbre programme du mathématicien David Hilbert), et couvrira les travaux fondateurs d'Alan Turing et d'Alonzo Church.

Ensuite, on démontrera qu'il existe des problèmes indécidables, c'est-à-dire des problèmes pour lesquels aucune solution algorithmique ne peut exister.

Enfin, on présentera certaines conséquences de ce résultat fondamental, en brossant un panorama de la recherche actuelle en informatique, et plus particulièrement du domaine très actif de la vérification assistée par ordinateur – qui se propose d'étudier les méthodes permettant de prouver automatiquement qu'un programme est correct.

Accès gratuit et sans inscription préalable


Responsables

Nom & prénom

   

Fonction

Francis Buekenhout

   

Responsable académique

   

Jean-François Raskin

   

Coordinateur

   

Samuel Fiorini

   

Conférencier

   

Gilles Geeraerts

   

Conférencier

   

Matière

Matière

Sciences et technologies

Cours-conférence

Les limites théoriques de l'informatique: les problèmes indécidables


Programme

Heure

   

Leçon

   

Conférenciers

17h00 - 19h00

   

L'indécidabilité: conséquences dans les mathématiques et l'informatique

   

Samuel Fiorini
Gilles Geeraerts

     

Lieu

Site

Palais des Académies

Immeuble

Palais

Local

Salle Albert

Adresse

Rue Ducale 1, 1000 Bruxelles


Galerie


Top