Calculabilité
Introduction
La calculabilité, avec une vision simplifiée, est un domaine des mathématiques et de l’informatique qui cherche à identifier ce qui est calculable avec un algorithme. Le célèbre mathématicien, logicien, Allan Turing (1912, 1954) a consacré une partie de ses recherches à cette problématique ; dans les années 30, il conçoit une machine abstraite qui lui permet de démontrer que la plupart des nombres réels ne sont pas calculables. Une réalisation possible de la machine de Turing est présentée en annexe 1, vous allez l’utiliser pour écrire un algorithme qui interprète du code. On rappelle que l’interprétation du code consiste à traduire une par une les lignes de code d’un programme écrit dans un langage informatique (python par exemple) en langage machine exécutable sur le système informatique ciblé. La traduction en langage machine n’est possible que si les instructions à interpréter respectent la syntaxe du langage reconnu par l’interpréteur.
Problème posé
L’interpréteur est un algorithme qui reçoit en entrée une ligne de code qui pour lui est une donnée à traiter. Il évalue l’instruction et procède à la traduction ou interrompt le processus d’interprétation et affiche un message d’erreur. Dans cette activité, on va soumettre à interprétation la fonction print("……..") du langage Python à une machine de Turing. La fonction print(..) recevra en paramètre une chaîne de caractère à afficher. La machine de Turing remplace l’ordinateur, elle exécute le programme d’interprétation qui amène à l’affichage de la chaine de caractère passée en paramètre à la fonction print("……..") ou à l’affichage d’un message d’erreur.
Vous savez que la fonction print("……..") du langage python possède un grand nombre de formatages possibles, on simplifiera le travail en réduisant les possibilités de formatage.
L’Annexe 1 formalise les limites du programme interpréteur qui s’exécute sur notre machine de Turing.
Question 1 : prise en main
Après lecture de l’Annexe 1 qui vous propose une prise en main de la machine de Turing, copiez-collez le code de l’algorithme d’interprétation du fichier « print sans debug.txt » dans la zone Turing machine program de la machine de Turing, copiez l’instruction §print("bonjour à tous")§ dans la zone Initial Input à votre interpréteur, cochez la case Run at full speed, cliquez sur Reset puis sur Run et observez le résultat, conclure sur l’aptitude de la machine à interpréter cette instruction python.
Question 2
Soumettez à interprétation l’instruction §jrint("bonjour à tous")§ qui contient une erreur de syntaxe. Observez le résultat et conclure sur l’aptitude de la machine à détecter cette erreur de syntaxe.
Question 3
On cherche maintenant à soumettre à interprétation l’instruction §print ( "bonjour à tous")§. Cette ligne de code introduit un espace entre la parenthèse ouvrante et les apostrophes doubles placées avant le b. Cette syntaxe est parfaitement licite avec un interpréteur du langage python. Observez le résultat de l’interprétation avec la machine de Turing, conclure sur l’aptitude de l’interpréteur à traiter cette instruction python. Décochez la case Run at full speed , cliquez sur Reset puis sur Step, observez l’exécution du programme jusqu’à l’erreur. Proposez une modification qui solutionne le problème.
Question 4
Dessinez le diagramme état transition de l’état 5 de la machine avec votre modification (revoir l’annexe1 qui présente le diagramme état transition. Vous limiterez le dessin à l’état 5 qui sera l’état initial, aux transitions entre l’état 5 et les autres états, l’état 7 sera l’état d’acceptation).
Question 5
Soumettez à votre interpréteur l’instruction §pr int ( "bonjour à tous")§. Cette ligne de code introduit un espace entre le caractère r et le caractère i. Cette syntaxe n’est pas acceptée par un interpréteur python. Observez le résultat de l’interprétation avec votre machine de Turing, conclure sur l’aptitude de votre machine à détecter cette erreur. Proposez une modification qui solutionne le problème si nécessaire.
Question 6
Soumettez à votre interpréteur l’instruction §print ( "bonjour à tous")§. Cette ligne de code introduit un espace entre le caractère t de print et la parenthèse ouvrante. Cette syntaxe est acceptée par un interpréteur python. Observez le résultat de l’interprétation avec votre machine de Turing, modifiez éventuellement votre interpréteur si nécessaire. Vérifiez également la détection d’erreur de syntaxe dans les cas suivants §print "bonjour à tous")§, §print ( bonjour à tous")§ , §print ("bonjour à tous)§ , §print ("bonjour à tous"§, toutes ces instructions oublient une des deux parenthèses ou des deux apostrophes, modifiez éventuellement votre interpréteur si nécessaire.
Question 7
Une fois l’interpréteur estimé fonctionnel au niveau de l’analyse syntaxique du print("…") , vous allez vérifier ce qui se passe lorsque la chaîne à afficher contient un caractère qui n’appartient pas à l’alphabet de travail. Soumettez à votre interpréteur l’instruction § print ( "coucou") § , conclure sur la réaction de la machine, modifiez l’alphabet de travail de la machine pour que le programme accepte le caractère c.
Question 8
Si on veut inclure le caractère « " » comme caractère quelconque de la chaîne passée en argument à la fonction print(..), par exemple "bonjour " toi " un problème survient puisque ce caractère est réservé pour délimiter la chaîne à afficher, le langage python permet d’utiliser le caractère d’échappement \ qui indique à l’interpréteur que le caractère qui suit doit être ignoré. Vous pouvez voir ci-dessous l’affichage du caractère " « échappé » :
Sans le caractère d’échappement, une erreur de syntaxe est détectée :
Observez le traitement des espaces par l’interpréteur lors de l’interprétation de l’instruction ci-dessous en exécutant le programme en mode Step :
§print ( "cou cou")§
En vous inspirant du traitement des espaces, modifiez le code de l’interpréteur pour que l’instruction §print ( "coucou\" ")§ affiche :
Question 9
Pensez-vous que votre interpréteur soit désormais capable d’interpréter l’instruction print("…") limitée à l’affichage de chaînes de caractères qui appartiennent à son alphabet de travail ? Si oui, vous me certifiez que l’interpréteur atteint toujours son état final d’acceptation quelque soit les chaînes passées en paramètres.
Créé avec HelpNDoc Personal Edition: Éditeur de documentation CHM facile