Dédidabilité et calculabilité
Problème décidable en informatique : Il existe un algorithme de longueur finie et de temps d'exécution fini qui répond oui ou non à la question posée.
Exercice 1
- Le problème de savoir si 442 est pair est-il décidable ?
- Le problème de savoir si 443 est premier est-il décidable ?
On parle aussi d'ensemble décidable. Un ensemble est décidable quand la question de savoir si tel élément appartient à l'ensemble est un problème décidable.
Exercice 2
- L'ensemble des nombres pairs est-il décidable ?
- L'ensemble des nombres premiers est-il décidable ?
On utilise parfois le terme ensemble récursif au lieu de ensemble décidable. Dans ce sens, récursif n'a absolument rien à voir avec l'idée de fonction récursive qui s'appelle elle-même. Ces termes sont très utilisés dans la théorie des langages informatiques qui est à la base de notions importantes comme les expressions régulières ou encore la conception de langages de programmation.
Calculabilité
Dans les années 1930, Alonzo Church (1903 - 1995) invente le $\lambda$-calcul. C'est un langage informatique théorique ou tout est fonction. Les langages de programmation Lisp, Haskell, oCaml sont influencés par le $\lambda$-calcul.
Church et son équipe étudient la calculabilité. Une fonction $f$ est calculable si le calcul de $f(x)$ se termine en un nombre fini d'étape.
Calculabilité et décidabilité
La notion est liée à la décidabilité. En effet, soit $E$ un ensemble. On peut toujours définir la fonction $f_E$ telle que $f_E(x) = V \Leftrightarrow x \in E$. Si $f_E$ est calculable, alors on peut décider si $x \in E$ et alors $E$ est décidable.
Les travaux de Church précèdent de peu ceux de Turing mais ils finiront par travailler ensemble.
Nous allons poursuivre avec les machines de Turing bien que historiquement, les résultats qui nous intéressent ont d'abord été formulés dans le cadre du $\lambda$-calcul de Church. Les deux approches sont équivalentes.