Le système Turing-complet, explications

Un Turing-complet se définit comme un système formel disposant d’une puissance de calcul  plus ou moins équivalente  à la puissance des machines de Turing.

turing-complet.jpg

En informatique ou en logique, le système permet de programmer toute machine de Turing aussi bien que n’importe quel contenu d’une machine Turing.

Qu’est-ce que la machine de Turing ?

La machine Turing est une notion abstraite, c’est un objet mathématique et non un matériel manuel et physique.  Quoi qu’il en soit, il s’agit de simuler qu’une machine Turing  est composée d’un ruban, d’une tête de lecture, d’un registre  d’état, d’une table d’action. Le fonctionnement de ces éléments peut être similaire à une machine à écrire ou à un PC.

machine-turing.jpg

Plusieurs sont  les termes et expressions pour définir   une machine de Turing, mais il n’y pas de grande différence entre eux. La plus courante définition s’affiche comme suit : « Une machine de Turing est un septuplet (Q, T, B, ∑, q0, β, F) ». A noter que la notion de machine de Turing  a précédé l’invention de l’ordinateur, et lors de la conception elle devait symboliser une personne virtuelle qui réalise une procédure préétablie en changeant le contenu des cellules.

Le système Turing-complet en logique informatique

En informatique ou en logique, Turing complet peut être traduit chaque calcul ou traitement de données  pouvant être programmé dans le système. C’est une traduction littérale. Mais pratiquement, il faut noter que l’informatique est un domaine d’activité concernant le traitement automatique de l’information qui touche le domaine scientifique, industriel et technique  d’une entreprise. Pratiquement, pour confirmer qu’une machine  répond conformément aux caractéristiques d’un ordinateur, il s’agit de signifier si elle est Turing complet. C’est-à-dire, il s’agit de savoir si la machine dispose de toutes les capacités pour réaliser tous les calculs possibles, sinon  il faut douter que c’est Turing Complet. S’il est vérifié que le dispositif peut exécuter tout programme de calcul et de traitement d’informations,  alors la machine est Turing Complet. La logique et la performance mathématique est la base du Turing Complet d’une machine utilisé en informatique.

Author: Yoann Le gall

Share This Post On