Qu'est-ce qui est calculable?

Au début du vingtième siècle, Hilbert a énoncé une série de problèmes dont le dixième est de trouver un algorithme déterminant si une équation diophantienne a des solutions. Cependant, à cette époque, il n'y avait pas de véritable définition d'algorithme. Il était donc très difficile de résoudre un tel problème. Ce n'est que vers les années trente que la notion d'algorithme a été formalisée, avec entre autre la définition de machine de Turing. Dans cet exposé, nous nous intéresserons à ces machines et aux fonctions qu'elles permettent de calculer. Nous aborderons certains problèmes pour lesquels il n'existe pas de solution. Cet exposé se veut une petite introduction à l'informatique théorique.

par Isabelle Ascah-Coallier (Université de Montréal)