Théorie de la calculabilité
La théorie de la calculabilité étudie quels problèmes peuvent en principe être résolus par un algorithme et classe les problèmes insolubles selon leur degré de difficulté.
Definition
La théorie de la calculabilité, également appelée théorie de la récursivité, est la branche de la logique mathématique qui précise la notion de fonction effectivement calculable, étudie les ensembles et les fonctions que les algorithmes peuvent ou ne peuvent pas calculer, et mesure la difficulté relative des problèmes insolubles.
Scope
Ce domaine couvre les modèles formels de calcul et la thèse de Church-Turing, les ensembles calculables et récursivement énumérables, les problèmes indécidables tels que le problème de l'arrêt, les réductibilités et les degrés de Turing qui mesurent l'insolvabilité relative, ainsi que la hiérarchie arithmétique qui stratifie la définissabilité par la complexité des quantificateurs.
Sub-topics
Core questions
- Que signifie pour une fonction ou un ensemble d'être calculable ?
- Quels problèmes naturels sont algorithmiquement indécidables ?
- Comment la difficulté des problèmes insolubles peut-elle être comparée et classée ?
- Comment la complexité logique correspond-elle aux niveaux de calculabilité ?
Key theories
- Thèse de Church-Turing
- La notion intuitive de calculabilité effective coïncide avec la calculabilité par machine de Turing, équivalemment avec les fonctions récursives et les fonctions lambda-définissables, établissant ainsi une définition mathématique robuste de l'algorithme.
- Insolvabilité du problème de l'arrêt
- Aucun algorithme ne peut décider, pour chaque programme et chaque entrée, si le programme s'arrête, offrant ainsi le premier exemple prototypique d'un problème indécidable.
- Degrés de Turing
- La réductibilité de Turing classe les ensembles par calculabilité relative, et les degrés induits forment un ordre partiel riche dont la structure, y compris l'existence de degrés intermédiaires, est un objet d'étude central.
Clinical relevance
La théorie de la calculabilité délimite la frontière absolue de la résolvabilité algorithmique, sous-tendant l'informatique théorique et fournissant les résultats d'indécidabilité, tels que l'insolvabilité des problèmes de l'arrêt et du mot, qui se retrouvent dans l'ensemble des mathématiques et éclairent la théorie de la complexité computationnelle.
History
La théorie de la calculabilité est apparue dans les années 1930 lorsque Church, Turing, Kleene et Post ont formalisé indépendamment la notion de procédure effective à travers le lambda-calcul, les machines de Turing, les fonctions récursives et les systèmes combinatoires, tous prouvés équivalents. Post et Kleene ont développé la théorie des degrés et la hiérarchie arithmétique, et la méthode de priorité introduite dans les années 1950 a stimulé l'étude structurelle approfondie des degrés récursivement énumérables.
Key figures
- Alan Turing
- Alonzo Church
- Stephen Cole Kleene
- Emil Post
Related topics
Seminal works
- soare1987
- rogers1987
- cutland1980
Frequently asked questions
- La théorie de la calculabilité est-elle la même chose que la théorie de la complexité ?
- Non. La théorie de la calculabilité se demande si un problème peut être résolu par un algorithme, quelles que soient les ressources, tandis que la théorie de la complexité se demande combien de temps ou de mémoire un problème soluble nécessite. La calculabilité trace la ligne entre le soluble et l'insoluble ; la complexité gradue le côté soluble.
- Pourquoi la thèse de Church-Turing n'est-elle pas un théorème ?
- Elle assimile une notion informelle, la calculabilité effective, à une notion mathématique précise, elle ne peut donc pas être prouvée formellement. Son acceptation repose sur la convergence de nombreuses formalisations indépendantes vers la même classe de fonctions, ce qui constitue une preuve solide plutôt qu'une démonstration.