Théorie de la calculabilité

Carte Peu commune · n° 142974

La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique qui vise à identifier les limites de ce qui peut être calculé par un algorithme. Cette théorie s'est développée dans les années 1930 lorsqu'ont été proposées pour la première fois des définitions formelles d'un algorithme, ainsi que des méthodes pour montrer que certains problèmes ne peuvent pas être résolus algorithmiquement. La calculabilité ne se préoccupe pas de l'efficacité des algorithmes, qui est l'objet de la théorie de la complexité, mais seulement de l'existence ou de la non-existence d'un algorithme qui résout un problème donné, sur un ordinateur idéalisé tel qu'une machine de Turing, démontrée équivalente en possibilités à tous les ordinateurs existants. La notion la plus centrale de la calculabilité est celle de fonction calculable. Son intérêt est justifié par la thèse de Church, qui affirme que les fonctions calculables avec...

Lire sur Wikipédia