Turing-complet
Un article de Wikipédia, l'encyclopédie libre.
L'adjectif Turing-complet[1] s'applique en informatique et en logique à un système formel ayant le pouvoir des machines de Turing, c'est-à-dire un système dans lequel on peut coder les machines de Turing. Si de plus, ce système peut-être codé par celui des machines de Turing, on dit qu'il est équivalent aux machines de Turing.
Ainsi un langage de programmation est dit Turing-complet s'il permet de représenter toutes les fonctions calculables au sens de Turing et Church (nonobstant la finitude de la mémoire des ordinateurs). La plupart des langages usuels de programmation (C, C++, Java, ...) sont Turing-complets. Le fait d'être Turing-complet est généralement requis pour un langage de programmation générique. En revanche, ce n'est pas le cas pour un langage dédié au traitement de problèmes spécifiques.
[modifier] Voir aussi
[modifier] Note
- ↑ En toute rigueur on devrait dire complet au sens de Turing, mais c'est la traduction littérale (et le calque syntaxique aussi) de l'expression anglo-saxonne Turing complete qui a prévalu.
