Remerciez-le!

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

Bloc 1 T.D n°1 : Les machines de TURING 1ère – NSI Lycée PMF Machines de Turing

Bloc 1 T.D n°1 : Les machines de TURING 1ère – NSI Lycée PMF Machines de Turing Dans chacun des exercices suivants, donne une table de transition permettant d'exécuter un algorithme afin de réaliser la tâche demandée. Puis construis le diagramme associé Exercice 1 : Ajoute un 1 à droite d’une séquence, la tête étant sous le chiffre de gauche. 0 1 1 0 1 0 Exercice 2 : Remplace, dans une séquence, tous les 1 par des 0 et tous les 0 par des 1. La tête de lecture est à gauche de la séquence. 0 1 1 0 1 0 0 1 Exercice 3 : Fais une addition de deux entiers écrits en unaire. On suppose que les deux nombres sont séparés par une case vide et que la tête de lecture est initialement sur la case la plus à gauche contenant un 1. Écrire un nombre en unaire revient à écrire autant de 1 que la valeur du nombre, exemple 5 s’écrit 11111. Indications : la tête de lecture va parcourir le premier nombre, arrivée sur le blanc, elle va écrire un 1 , puis elle va parcourir le deuxième nombre, arrivée au blanc elle va reculer d’une case et va terminer en mettant à blanc le 1 le plus à droite. Pour aller plus loin : Doubler le nombre d'éléments écrits initialement sur un ruban. Pour cela on suppose qu'on une suite de 1 qui est écrite sur le ruban, la tête de lecture/écriture est située sous le 1 le plus à droite. La machine doit doubler le nombre de 1 déjà écrits. Indications : Quand la machine va lire un 1 à gauche, elle va le remplacer par un 0 et elle va se déplacer à droite pour écrire un autre 0 . Elle va continuer ainsi jusqu’à ce qu’il n’y ait plus de 1 à gauche. A ce moment, il y aura sur le ruban un nombre de 0 qui sera le double du nombre initial de 1. La dernière étape consiste simplement à remplacer tous ces 0 par des 1. __________ uploads/Litterature/ 2-td1-machines-turing.pdf