Définition - Que signifie Turing Machine?
Une machine de Turing est une machine théorique qui manipule des symboles sur une bande de ruban, sur la base d'un tableau de règles. Même si la machine de Turing est simple, elle peut être adaptée pour reproduire la logique associée à tout algorithme informatique. Il est également particulièrement utile pour décrire les fonctions du processeur dans un ordinateur.
Alan Turing a inventé la machine de Turing en 1936, et il l'a appelée une "machine a" ou machine automatique.
Definir Tech explique Turing Machine
La machine de Turing n'est pas destinée à être une technologie informatique fonctionnelle; au lieu de cela, il est conçu comme une machine hypothétique qui représente une machine informatique. La machine de Turing peut aider les informaticiens à comprendre les limites du calcul mécanique.
Les machines de Turing modélisent mathématiquement un appareil qui fonctionne mécaniquement à l'aide d'une bande. Cette bande comprend des symboles que la machine peut écrire et lire les uns après les autres à l'aide d'une tête de bande.
Plus précisément, une machine de Turing comprend les éléments suivants:
- Bande: Une bande qui est divisée en cellules, l'une à côté de l'autre. Chaque cellule comprend un symbole d'un certain alphabet fini. L'alphabet comprend un symbole vierge unique ainsi qu'un ou plusieurs autres symboles. Le volume de bande requis pour le calcul est toujours inclus dans la machine de Turing.
- Tête: Une tête capable d'écrire et de lire des symboles sur la bande. Dans certains modèles, la tête bouge tandis que la bande est fixée.
- Registre d'état: un registre d'état pour stocker l'état de la machine de Turing. Il existe un état de démarrage spécial par lequel le registre d'état est initialisé.
- Table finie: une table finie (parfois appelée fonction de transition ou table d'action) d'instructions, qui sont généralement des quintuples, mais parfois quadruples.