Une machine de Turing est-elle un ordinateur ?

Une machine de Turing est-elle un ordinateur ?

La machine de Turing n'est pas un ordinateur, la machine de Turing n'est qu'un modèle informatique théorique.

La machine dite de Turing fait référence à une machine abstraite. Elle possède une bande de papier infiniment longue. La bande de papier est divisée en petits carrés, chaque carré a une couleur différente. Il y a une tête de machine qui se déplace sur la bande de papier. La tête de la machine possède un ensemble d'états internes, ainsi que des procédures fixes. À chaque instant, la tête de la machine doit lire un carré d'informations sur la bande de papier actuelle, puis rechercher dans la table du programme en fonction de son propre état interne, sortir les informations sur le carré de bande de papier en fonction du programme et convertir son propre état interne. , puis Faites un geste.

En 1936, le mathématicien britannique Alan Matheson Turing (1912-1954) a proposé un modèle informatique abstrait : la machine de Turing. La machine de Turing, également connue sous le nom d'ordinateur de Turing, résume le processus par lequel les personnes utilisent du papier et un crayon pour effectuer des opérations mathématiques et remplace les humains par des opérations mathématiques par une machine virtuelle.

Idée de base

L'idée de base de Turing est d'utiliser des machines pour simuler le processus des personnes utilisant du papier et un stylo pour effectuer des opérations mathématiques. Il considérait ces processus comme les deux suivants. types Actions simples :

1. Écrivez ou effacez un certain symbole sur le papier

2. Déplacez votre attention d'une position sur le papier à une autre.

À chaque étape, la personne doit décider de l'action suivante, qui dépend (1) du symbole à une certaine position sur le papier auquel la personne prête actuellement attention et (2) de l'état actuel de la personne. de penser.

Afin de simuler ce processus de calcul humain, Turing a construit une machine imaginaire composée des parties suivantes :

1. Une bande de papier infiniment longue. La bande de papier est divisée en petites grilles les unes après les autres, chaque grille contient un symbole d'un alphabet limité et il y a un symbole spécial dans l'alphabet pour représenter l'espace blanc. Les grilles du ruban de papier sont numérotées 0, 1, 2,... de gauche à droite, et l'extrémité droite du ruban de papier peut être étendue à l'infini.

2. Une tête de lecture-écriture HEAD. La tête de lecture-écriture peut se déplacer à gauche et à droite sur la bande de papier. Elle peut lire les symboles sur la grille actuellement pointée et modifier les symboles sur la grille actuelle.

3. Un ensemble de règles de contrôle TABLEAU. Il détermine la prochaine action de la tête de lecture-écriture en fonction de l'état actuel de la machine et du symbole sur la grille pointé par la tête de lecture-écriture actuelle, et modifie la valeur du registre d'état pour faire entrer la machine dans un nouvel état. .

4. Un registre de statut. Il est utilisé pour sauvegarder l’état actuel de la machine de Turing. Le nombre de tous les états possibles d’une machine de Turing est fini et il existe un état spécial appelé état d’arrêt. Voir problème d'arrêt.

Notez que chaque partie de cette machine est finie, mais elle a une longueur potentiellement infinie de ruban de papier, cette machine n'est donc qu'un appareil idéal. Turing pensait qu'une telle machine pourrait simuler n'importe quel processus informatique que les humains peuvent effectuer.

Sur certains modèles, la tête de lecture/écriture se déplace le long d'un ruban de papier fixe. La commande à exécuter (q1) est affichée dans la tête de lecture/écriture. La bande « vierge » dans ce modèle est entièrement composée de zéros. Les carrés ombrés, y compris les blancs numérisés par la tête de lecture-écriture, les carrés marqués 1, 1, B et le symbole de la tête de lecture-écriture, constituent l'état du système. (Dessin de Minsky (1967) p.121).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!