Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Calculabilité

La théorie de la calculabilité a été initiée par Alan Turing avec sa fameuse Machine de Turing. Un autre modèle a été élaboré par Alonzo Church : le lambda-calcul.

Cette théorie permet de chercher ce que peut calculer et ce que ne peut pas calculer une machine. L'exemple le plus courant est le problème de l'arrêt : il n'existe pas de programme qui prenne un programme en argument et qui renvoit « oui » si le programme en argument finit et « non » s'il ne finit pas. En lambda-calcul il y a le terme (λx.xx)(λx.xx) qui n'est pas normalisable (donc pas calculable).