Ceci est une ancienne révision du document !
Informatique et décidabilité
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.
lambda - calcul
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 travaux de Church précèdent de peu ceux de Turing mais ils finiront par travailler ensemble.
Les langages de programmation Lisp, Haskell, oCaml sont influencés par le $\lambda$-calcul.
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.