Turing Complete
La complétude de Turing signifie qu'un système de calcul peut simuler une machine de Turing et calculer toute fonction calculable — la référence de la puissance de calcul général.
Objectif
Juger le plafond de puissance de calcul d'un langage/système et comprendre les limites de la calculabilité.
Mécanisme
Exige : branchement conditionnel + boucles/récursion arbitraires + mémoire en lecture-écriture. La plupart des langages sont Turing-complets. HTML+CSS (contesté), SQL (CTE récursifs) et regex (références arrière) sont à la frontière. Le problème de l'arrêt est indécidable.
Cas d’usage
- Théorie du calcul
- Puissance des langages
- Calculabilité