Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Machine de turing Exemple La machine de Turing qui suit possède un alphabet ? ? ? ? ? ? étant le blanc ? On suppose que le ruban contient une série de ? ? et que la tête de lecture écriture se trouve initialement au-dessus du ? ? le plus à gauche Cette ma

Exemple La machine de Turing qui suit possède un alphabet ? ? ? ? ? ? étant le blanc ? On suppose que le ruban contient une série de ? ? et que la tête de lecture écriture se trouve initialement au-dessus du ? ? le plus à gauche Cette machine a pour e ?et de doubler le nombre de ? ? en intercalant un ? ? entre les deux séries Par exemple ? devient ? L ? ensemble d ? états possibles de la machine est e e e e e et l ? état initial est e La table d ? actions est la suivante Exemple de table de transition Ancien état Symbole lu Symbole écrit Mouvement Nouvel état e Arrêt Droite e e Droite e Droite e e Droite e Gauche e e Gauche e Gauche e e Gauche e Droite e L ? exécution de cette machine pour une série de deux ' ' serait la position de la tête de lecture écriture sur le ruban est inscrite en caractères gras et rouges Exécution Exécution Exécution Exécution CÉtape État Ruban Étape État Ruban Étape État Ruban Étape État Ruban e e e e e e e e e e e e e e e Arrêt Le comportement de cette machine peut être décrit comme une boucle Elle démarre son exécution dans l ? état e remplace le premier par un Puis elle utilise l ? état e pour se déplacer vers la droite en sautant les un seul dans cet exemple jusqu'à rencontrer un ou un blanc et passer dans l'état e L ? état e est alors utilisé pour sauter la séquence suivante de initialement aucun et remplacer le premier rencontré par un L'état e permet de revenir vers la gauche jusqu ? à trouver un et passer dans l ? état e L'état e permet ensuite à nouveau de se déplacer vers la gauche jusqu ? à trouver un écrit au départ par l ? état e La machine remplace alors ce par un se déplace d ? une case vers la droite et passe à nouveau dans l ? état e pour une nouvelle itération de la boucle Ce processus se répète jusqu ? à ce que e tombe sur un c ? est le du milieu entre les deux séquences de à ce moment la machine s ? arrête Dans l'exemple qui suit la machine de Turing possède un ruban vide et permet de créer le nombre Exemple de table in ?nie Ancien état Symbole écrit Mouvement Nouvel état a Droite b b Droite a L ? exécution de cette machine serait la position de la tête de lecture écriture sur le ruban est inscrite en caractères gras et magenta CExécution de la Machine in ?nie Etape Etat Ruban a b a b a b a b Le comportement de cette machine peut être décrit comme une boucle in ?nie Elle démarre son exécution dans l ? état a ajoute un et