À retenir
- Définit la limite absolue de ce qu'une machine peut résoudre logiquement.
- Repose sur l'existence d'un algorithme fini.
- Si un problème n'est pas Turing-calculable, aucun futur superordinateur ne pourra jamais le résoudre.
Qualifie un problème ou une fonction mathématique qui peut être résolu par un ordinateur en suivant une suite d'instructions précises (un algorithme). Si une machine de Turing — un modèle théorique d'ordinateur — est capable de trouver le résultat en un temps fini, alors le problème est dit Turing-calculable. C’est un peu comme une recette de cuisine : si les étapes sont assez claires pour être exécutées mécaniquement, le résultat est garanti.
Étymologie
Ce terme rend hommage à Alan Turing, mathématicien britannique considéré comme le père de l'informatique moderne. En 1936, il a défini le concept de "machine de Turing" pour délimiter mathématiquement ce qui est mécaniquement calculable de ce qui ne l'est pas.
Exemples d'usage
- L'addition de deux nombres entiers (on peut écrire un programme simple pour cela).
- Le tri d'une liste de noms par ordre alphabétique.
- La recherche du plus court chemin entre deux villes sur une carte.
Cas d'usage
Ce concept intervient principalement en informatique théorique et en logique. Il sert à définir les limites fondamentales de l'informatique : il permet de distinguer les problèmes qu'un logiciel peut techniquement résoudre de ceux qui sont logiquement impossibles à traiter pour une machine.
Bonnes pratiques
Il est crucial de ne pas confondre la calculabilité (est-ce qu'une solution existe ?) avec la complexité (combien de temps et de mémoire cela prend-il ?). Un problème peut être Turing-calculable mais demander des milliards d'années pour être résolu en pratique.
Synonymes
Antonymes
Conseil
Pour bien comprendre ce concept, visualisez la machine de Turing comme l'ancêtre théorique universel. Si vous pouvez écrire un script (même très long) pour résoudre un problème, alors ce problème est Turing-calculable.
Questions fréquentes
Est-ce que tous les problèmes sont Turing-calculables ?
Non, il existe des problèmes dits 'indécidables', comme le problème de l'arrêt, qu'aucune machine ne pourra jamais résoudre, peu importe sa puissance.
Un PC moderne est-il plus puissant qu'une machine de Turing ?
En termes de capacité logique, non. Tout ce qu'un ordinateur actuel exécute est, par définition, Turing-calculable.