La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la
logique mathématique et de l'
informatique théorique. Alors que la notion intuitive de fonction calculable est aussi vieille que les mathématiques (voir l'article
Histoire des mathématiques), la formalisation de ces notions a commencé dans la décennie 1930 afin de répondre à des problèmes fondamentaux de logique mathématique, dont celui énoncé par
David Hilbert et appelé Entscheidung Problem ou
Problème de la décision. La calculabilité cherche d'une part à identifier la classe des
fonctions qui peuvent être calculées à l'aide d'un
algorithme et d'autre part à appliquer ces concepts à des questions fondamentales des mathématiques. Une bonne appréhension de ce qui est calculable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs.
Pour la suite, voir Wikipédia.org…
Free Download Now!
