Accueil |

Calculabilité

   

REDIRECT

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" si il ne finit pas. En lambda-calcul il y a le terme (λx.xx)(λx.xx) qui n'est pas normalisable (donc pas calculable).