Calculabilité PDF
Dans différentes branches de la science, il y a des résultats a la vue desquels nous pouvons tout de suite conclure que certaines prétendues inventions sont impossibles : • un moteur qui ne consomme pas d’énergie base sur le principe du mouvement perpétuel (en contradiction avec les lois fondamentales de la physique); • un chauffage révolutionnaire fournissant de la chaleur et qui ne consomme pas d’énergie. En est-il de même pour certains projets en informatique. Y a-t-il des limites `a ce que nous pouvons faire avec un ordinateur, des limites `a ce que nous pouvons calculer ? C’est en effet, le cas : tout n’est pas calculable ! Dans ce cours, nous allons essayer de comprendre les limites de l’informatique : • nous verrons qu’il existe, en effet, des problèmes qui n’ont pas une solution algorithmique. • nous verrons également que certains problèmes n’ont pas de solutions satisfaisantes en terme d’efficacité. Quand un informaticien tente résoudre un problème et qu’il ne parvient pas a résoudre ce problème, il adopte généralement deux attitudes : • (version optimiste) il se dit : “je pense que je suis proche de réussir, je vais corriger quelques détails et ajouter les derniers cas que mon algorithme ne considère pas”; • (version plus réaliste) il se dit : “je suis parti sur de mauvaises bases, je vais recommencer a zéro...”
Cours: