Turing-complet

Le terme Turing-complet désigne en informatique un système formel ayant au moins le pouvoir des machines de Turing :

Un langage de programmation est dit Turing-complet s'il permet de représenter toutes les fonctions calculables au sens de Turing (nonobstant la finitude de la mémoire des ordinateurs actuels). La plupart des langages usuels de programmation (C, C++, Java, ...) sont Turing-complets. Le fait d'être Turing-complet est généralement un critère demandé d'un langage de programmation générique, par opposition à un langage dédié au traitement de problèmes spécifiques ; cependant, il s'agit d'une caractéristique qui peut être non souhaitable d'un langage de macro-définitions (le langage de templates du C++ est Turing-complet, sauf à appliquer une limitation de profondeur des instanciations).

Voir aussi

Programmation informatique Logique mathématique Calculabilité

Gourt Home::Gourt :: Turing-complet

Voir aussi