##  [Complétude de Turing](/fr/node/57652) 

 Définition

Propriété d'un système computationnel indiquant qu'il peut simuler n'importe quelle machine programmable générale et donc réaliser tout calcul qu'une telle machine idéale peut effectuer, à condition de disposer de temps et de mémoire non bornés.

 

 

 

 

 

 





## Principe

Principe

Universalité par simulation : si un système peut émuler les transitions d'état d'une machine programmable idéale, il atteint la même classe de comportements calculables sous ressources idéalisées.

 

 

 

 

 





## Démonstration

Démonstration

Un langage impératif minimal avec branchement conditionnel et stockage d'entiers non borné peut simuler une machine universelle et est donc Turing-complet ; l'automate cellulaire Règle 110 est un exemple constructif standard.

 

 

 

 

## Mauvaise application

Mauvaise application

Confondre complétude de Turing avec utilité pratique, efficacité, décidabilité ou terminaison garantie est incorrect ; la complétude concerne seulement l'universalité de représentation sous ressources idéalisées.

 

 

 

 

 





## Conséquence

Conséquence

Quand un système est Turing-complet, on peut y encoder n'importe quelle procédure algorithmique, mais les résultats classiques d'indécidabilité et de non-terminaison s'appliquent alors aussi aux programmes de ce système.

 

 

 

 

## Inversion

Inversion

Un système non Turing-complet n'a pas la capacité de simuler des calculs universels arbitraires et ne peut donc pas exprimer tous les processus algorithmiques, bien qu'il puisse être décidables ou plus prévisible.

 

 

 

 

 





## Limite

Limite

Dépend d'idéalisations telles qu'une mémoire non bornée et un contrôle d'état précis ; les modèles à mémoire finie, au flux de contrôle restreint ou aux primitives non programmables ne possèdent pas cette propriété.

 

 

 

 

 





## Tension sémantique

Tension sémantique

Diffère des notions informelles d'expressivité ou de commodité : un langage peut être expressif pour les utilisateurs sans être Turing-complet, et inversement ; la complétude est une propriété formelle de simulation, pas une métrique d'utilisabilité.

 

 

 

 

 





## Synthèse

Synthèse

La complétude de Turing classe les systèmes selon leur capacité à émuler une machine programmable universelle sous ressources idéalisées, impliquant à la fois un pouvoir de représentation maximal et l'héritage de phénomènes d'indécidabilité.