Théorie de la calculabilité
domaine de la logique mathématique et de l’informatique théorique étudiant les fonctions calculables et les degrés Turing / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Calculabilité?
Résumez cet article pour un enfant de 10 ans
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, et 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 que 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 la définition formelle correspondent exactement aux fonctions qui peuvent être calculées par un humain ou une machine, dans le monde physique.
Cependant, la calculabilité ne se limite pas à séparer les fonctions calculables des fonctions non-calculables, mais cherche aussi à comparer les fonctions non-calculables entre elles, en s'appuyant sur la notion de réduction pour affirmer (informellement) que certaines fonctions sont « plus incalculables » que d'autres. Les niveaux d'incalculabilité sont appelés degrés de Turing, et une partie de la calculabilité consiste à étudier leur structure.