Turing-complet

Un article de Wikipédia, l'encyclopédie libre.

Pour les articles homonymes, voir Turing (homonymie).

L'adjectif Turing-complet[1] s'applique en informatique et en logique à un système formel ayant le pouvoir des 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

  1. ↑ 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.