Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:terminales:calculabilite:machine_turing [2023/02/06 19:35] – ↷ Nom de la page changé de nsi:terminales:calculabilite:informatique à nsi:terminales:calculabilite:machine_turing goupillwiki
+++ nsi:terminales:calculabilite:machine_turing [2023/02/06 21:21] (Version actuelle) – goupillwiki
@@ Ligne 1: / Ligne 1: @@
-====== Informatique et décidabilité ======
+======Machines de Turing======
-<WRAP info>
-**Problème décidable en informatique :** Il existe un algorithme de longueur finie et de temps d'exécution fini qui répond oui ou non à la question posée.
+===== Machine de Turing =====
+{{ :nsi:terminales:calculabilite:machine_turing.svg?600x400 | }}
+La machine est constituée :
+  * d'une liste de symboles autorisés,
+  * d'une bande potentiellement infinie\\ des symboles sont écrits sur la bande au début, mais sur une zone finie de la bande
+  * une tête de lecture/écriture qui permet de lire le symbole en cours et si on le souhaite d'en écrire un autre
+  * à chaque cycle, la machine est dans un certain état.\\ Il y a l'état initial, l'état final, et d'autres états, autant que l'on veut mais en nombre fini
+  * un programme, de taille finie
+{{ :nsi:terminales:calculabilite:turing.jpg?nolink&200|Alan Turing 1912 - 1954}}
+Le programme de la machine ci-dessus est constitué de 5 lignes :
+^ S:état ^ L:Lu   ^ E:écrire ^ M:mouvement ^ N:nouvel état ^
+| 0      | 1      | X        | >:droite    | 0             |
+| 0      | _:vide | *:rien   | <:gauche    | 1             |
+| 0      | *:tous | 0        | >           | 0             |
+| 1      | _      | *        | >           | H:halt        |
+| 1      | *      | *        | >           | 1             |
+La première ligne signifie : Si la machine est dans l'état 0 et qu'on lit le caractère 1, alors il faut écrire le caractère X puis aller à droite (la tête de lecture/écriture va à droite, donc la bande va à gauche...) et on reste dans l'état 0.
+{{ :nsi:terminales:calculabilite:exemple_machine.svg?600x650 |}}
+=== À quoi sert cette machine ? ===
+La machine de Turing fait penser à un ordinateur primitif. Mais **elle ne sert pas à fabriquer un ordinateur**. La machine de Turing est une **machine abstraite** que l'on n'essaie même pas de fabriquer. Elle sert seulement à réfléchir sur les algorithmes, à dire ce qui est possible et ce qui ne l'est pas.
+<WRAP important>
+Tout algorithme, peut trouver un équivalent sous forme d'une machine de Turing. Cette machine est peut-être énorme, chère, pas efficace... ou encore trop grosse pour être réalisée avec ce dont on dispose sur Terre. Mais l'important est qu'elle soit **théoriquement** réalisable.
+Si un problème n'est pas faisable avec une machine de Turing, alors aucun algorithme fini n'en viendra à bout, quelque soit la technologie utilisée.
 </WRAP>
-=== Exercice 1 ===
+La machine permet de donner une nouvelle définition de la calculabilité : Un fonction est calculable s'il est possible de réaliser une machine de Turing exécutant cette fonction.
-  - Le problème de savoir si 442 est pair est-il décidable ?
+<WRAP tip>**Turing - complet :** un langage est dit ou une machine est dit Turing - complet s'il permet de réaliser la même chose qu'une machine de Turing. Un ordinateur moderne est Turing complet.
-  - Le problème de savoir si 443 est premier est-il décidable ?
+</WRAP>
-<WRAP info>
+===== Des exemples le machines de Turing =====
-On parle aussi d'**ensemble décidable**. Un ensemble est décidable quand la question de savoir si tel élément appartient à l'ensemble est un problème décidable.
+=== Exercice 3 ===
+^ État en cours ^ Symbole lu ^ Écrire ^ Mouvement ^ État suivant ^
+| init          | 1          | 0      | droite    | init         |
+| init          | 0          | 1      | droite    | init         |
+| init          | _          | _      | gauche    | retour       |
+| retour        | 1          | 1      | gauche    | retour       |
+| retour        | 0          | 0      | gauche    | retour       |
+| retour        | _          | _      | droite    | fin          |
+Supposons que sur la bande magnétique, on ait écrit ''%%[1]10010010%%''.
+''%%[]%%'' représente la position de la tête de lecture.
+  - Qu'est-il écrit sur la bande à la fin de l'exécution ?
+  - Simuler l'exécution sur le site [[http://morphett.info/turing/]]
+<WRAP tip>
+  * On utilise le symbole ''*'' pour dire, dans la colonne lecture, //n'importe quel caractère// et, dans la colonne écriture, //ne rien changer//
+  * En général, on fait commencer la machine au début du mot écrit sur la bande et on fait en sorte que la machine revienne à la même position quand elle s'arrête.
 </WRAP>
-=== Exercice 2 ===
+=== Exercice 4 ===
+Les symboles écrits sur la bande forment un **mot**. Ce mot peut être compris comme un nombre. Par exemple ''110010'' est l'écriture binaire de 50.
-  - L'ensemble des nombres pairs est-il décidable ?
+  - Concevez la machine qui, partant de l'écriture binaire d'un nombre $n$, termine avec l'écriture binaire de $2\cdot n$
-  - L'ensemble des nombres premiers est-il décidable ?
+  - Concevez la machine qui, partant de l'écriture binaire d'un nombre $n$, termine avec l'écriture binaire de $2\cdot n + 1$
+  - Concevez la machine qui, partant de l'écriture binaire d'un nombre $n$, termine avec l'écriture binaire de $n + 1$. //C'est plus difficile !//
 <WRAP tip>
-On utilise parfois le terme **ensemble récursif** au lieu de ensemble décidable. Dans ce sens, récursif n'a absolument rien à voir avec l'idée de fonction récursive qui s'appelle elle-même. Ces termes sont très utilisés dans la théorie des langages informatiques qui est à la base de notions importantes comme les expressions régulières ou encore la conception de langages de programmation.
+Les machines évoquées ci-dessus semblent n'avoir besoin que des symboles 0 et 1. Toutefois, on a le droit d'insérer des symboles en plus, dans le déroulement de l'exécution. Par exemple, il est courant d'utiliser le symbole #. Dans le déroulement, # est écrit. Avant la fin, il est effacé.
 </WRAP>
-===== lambda - calcul =====
+=== Exercice 5 ===
-{{ :nsi:terminales:calculabilite:church.jpeg?nolink&200|}}
+Concevez un programme qui commence avec un nombre binaire $u$ et qui termine avec $u$ écrit à l'envers.
-Dans les années 1930, Alonzo Church (1903 - 1995) invente le $\lambda$-calcul. C'est un langage informatique théorique ou tout est fonction. Les travaux de Church précèdent de peu ceux de Turing mais ils finiront par travailler ensemble.
+Par exemple ''11010'' termine avec ''01011''.
-Les langages de programmation [[langages:lisp:start|Lisp]], [[langages:haskell:start|Haskell]], [[nsi:langages:ocaml:start|oCaml]] sont influencés par le $\lambda$-calcul.
+===== Définition théorique =====
-Nous allons poursuivre avec les **machines de Turing** bien que historiquement, les résultats qui nous intéressent ont d'abord été formulés dans le cadre du $\lambda$-calcul de Church. Les deux approches sont équivalentes.
+<wrap important>Ce qui est dit là sort largement du programme de NSI</wrap>
+Comme on l'a dit, les machines de Turing sont des concepts abstraits. Quand on veut les utiliser pour prouver des choses, on a besoin d'une formalisation très rigoureuse qui a tout d'une formalisation mathématique. Ainsi, on définira une machine par :
+  * un ensemble fini $\Sigma$ contenant les symboles nécessaires pour représenter les données traitées par la machine //0 et 1 dans les exemples précédents// ;
+  * un ensemble fini $\Gamma$, l'alphabet de ruban, qui contient $\Sigma$ et d'autres symboles dont au moins le symbole vide ''_'' ;
+  * un ensemble fini $Q$, les états ;
+  * un élément $i \in Q$, l’état initial ;
+  * un élément $f \in Q$, l’état final ;
+  * une fonction $\delta : (Q \setminus \lbrace f \rbrace) \times \Gamma \to \Gamma \times \{-1, 0, +1\} \times Q$, la table de transition.