Remerciez-le!

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

Aaa14058 APMEP no Programmer avec une machine de Turing Apprenez à programmer avec une machine de Turing Marc Raynaud Descriptifs techniques diagrammes et vidéos sur le site www machinedeturing org Nous présentons dans cet article un prototype de la machi

APMEP no Programmer avec une machine de Turing Apprenez à programmer avec une machine de Turing Marc Raynaud Descriptifs techniques diagrammes et vidéos sur le site www machinedeturing org Nous présentons dans cet article un prototype de la machine imaginée par Alan Turing pour modéliser le concept d ? algorithme et donner une réponse négative au problème de la décision en logique du premier ordre posé quelques années auparavant par Hilbert et Ackermann Pour simpli ?er est-il possible de trouver une méthode e ?ectivement calculable ? pour décider si une proposition est démontrable ou non Si ce problème mathématique est di ?cile le fonctionnement de sa machine est abordable par un large public et vous trouverez ci-dessous de nombreux exemples à proposer à vos élèves Alan Turing - est un mathématicien britannique Il obtient sa licence en au King ? s Collège de Cambridge Il passe ensuite sa thèse à Princeton aux États-Unis Le prototype présenté ici est directement issu de la description qu ? il a donnée dans son article publié en et intitulé On Computable Numbers with an Application to the Entscheidungsproblem problème de la décision Vous trouverez le texte initial sur le site www machinedeturing org onglet machine de Turing Alan Turing n ? a jamais construit cette machine J ? ai simplement ajouté un lecteur de feuilles perforées qui permet de le programmer facilement L ? intérêt de ce prototype est qu ? il permet de mettre en ?uvre un très professeur de mathématiques à la retraite C Pour chercher et approfondir APMEP no grand nombre d ? algorithmes dont on peut immédiatement visualiser le fonctionnement C ? est aussi une belle illustration du génie de ce grand mathématicien Description théorique de la machine Un ruban in ?ni comporte des cases qui peuvent contenir des symboles une tête d ? écriture et de lecture peut se déplacer sur ce ruban La tête peut lire le symbole déjà écrit en écrire un autre et se déplacer d ? une case à gauche ou d ? une case à droite Les actions à exécuter écriture déplacement et choix d ? un état sont inscrites dans ce qu ? on appelle les états L ? ensemble des états possibles est regroupé dans la table des transitions Exemple détaillé Trouver une séquence et en remplacer les par des Une séquence de et de est écrite sur le ruban et la tête est à gauche de cette séquence Pour cet algorithme on utilise deux états À l ? état ? la tête devra se déplacer à droite tant qu ? elle lira un blanc dès qu ? elle trouve un ou un elle passe à l ? état À l ? état ? si elle lit un elle écrit et se déplace à droite ? si elle lit un elle n ? écrit rien et se déplace à droite ? en ?n si elle lit un blanc c ? est qu ? elle a ?ni de parcourir la séquence elle passe