Quelle est l’idée de base de la machine de Turing ?

L'idée de base d'une machine de Turing est d'utiliser une machine pour simuler le processus de personnes effectuant des opérations mathématiques avec un stylo et du papier. Ce processus peut être vu comme deux actions simples : 1. écrire ou effacer un certain symbole sur le papier 2. déplacer l'attention d'une position sur le papier à une autre ;

L'environnement d'exploitation de cet article : système Windows 7, ordinateur Dell G3.

Machine de Turing fait référence à une machine abstraite. Elle possède un ruban de papier infiniment long. Le ruban de papier est divisé 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.

L'idée de base de Turing est d'utiliser des machines pour simuler le processus de personnes effectuant des opérations mathématiques avec du papier et un stylo. Il considérait un tel processus comme les deux actions simples suivantes :

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.

Si vous souhaitez en savoir plus sur la programmation, faites attention à la rubrique

Formation php !

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!