De quelles trois parties se compose une machine de Turing ?

La machine de Turing se compose de trois parties : 1. Une bande divisée en plusieurs carrés, dans lesquels les symboles peuvent être écrits ou lus 2. Une tête de lecture-écriture mobile, qui peut lire les symboles de la bande ; Ou écrivez des symboles sur la bande ; 3. Un ensemble de règles qui indiquent à la tête de lecture-écriture ce qu'elle doit faire ensuite.

La machine de Turing se compose de trois parties :

1. La bande est divisée en plusieurs carrés (ou " adresses" » dans lesquelles des symboles peuvent être écrits ou lus. Les bretelles sont infiniment longues aux deux extrémités.

2. Une tête de lecture-écriture mobile qui peut lire ou écrire des symboles sur la bande. À tout moment, la tête de lecture-écriture se trouve dans l’un d’un ensemble d’états.

3. Un ensemble de règles qui indiquent à la tête de lecture/écriture ce qu'elle doit faire ensuite.

La tête de lecture et d'écriture démarre dans un état de démarrage spécifique et s'arrête sur une grille spécifique.

A chaque étape, la tête de lecture-écriture lit les symboles dans la grille courante. La tête de lecture-écriture agit ensuite selon les règles basées sur le symbole de lecture et l'état actuel de la tête de lecture-écriture.

Les règles déterminent quel symbole la tête de lecture-écriture écrit dans la grille actuelle (en remplacement du symbole actuel) ; si la tête de lecture-écriture se déplace vers la droite ou la gauche ou s'arrête et quel est le nouvel état de la ; la tête de lecture-écriture est . Si la tête de lecture/écriture entre dans l'état d'arrêt, la machine s'arrêtera.

L'entrée de la machine de Turing est l'ensemble des symboles écrits sur la bande avant le démarrage de la machine. Le résultat est l'ensemble des symboles laissés sur la bande après l'arrêt.

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!