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

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

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

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

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

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

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

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

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é.