Différences

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

--- nsi:terminales:calculabilite:machine_turing [2023/02/06 20:11] – goupillwiki
+++ nsi:terminales:calculabilite:machine_turing [2023/02/06 21:21] (Version actuelle) – goupillwiki
@@ Ligne 1: / Ligne 1: @@
 ======Machines de Turing======
-===== Dédidabilité =====
-<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.
-</WRAP>
-=== Exercice 1 ===
-  - Le problème de savoir si 442 est pair est-il décidable ?
-  - Le problème de savoir si 443 est premier est-il décidable ?
-<WRAP info>
-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.
-</WRAP>
-=== Exercice 2 ===
-  - L'ensemble des nombres pairs est-il décidable ?
-  - L'ensemble des nombres premiers est-il décidable ?
-<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.
-</WRAP>
-===== Calculabilité =====
-{{ :nsi:terminales:calculabilite:church.jpeg?nolink&200|Alonzo Church 1903 - 1995}}
-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 langages de programmation [[langages:lisp:start|Lisp]], [[langages:haskell:start|Haskell]], [[nsi:langages:ocaml:start|oCaml]] sont influencés par le $\lambda$-calcul.
-Church et son équipe étudient la **calculabilité**. Une fonction $f$ est calculable si le calcul de $f(x)$ se termine en un nombre fini d'étape.
-<WRAP box>
-==Calculabilité et décidabilité==
-La notion est liée à la **décidabilité**. En effet, soit $E$ un ensemble. On peut toujours définir la fonction $f_E$ telle que $f_E(x) = V \Leftrightarrow x \in E$. Si $f_E$ est calculable, alors on peut décider si $x \in E$ et alors $E$ est décidable.
-</WRAP>
-Les travaux de Church précèdent de peu ceux de Turing mais ils finiront par travailler ensemble.
-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.
 ===== Machine de Turing =====
@@ Ligne 79: / Ligne 40: @@
 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.
+<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.
+</WRAP>
 ===== Des exemples le machines de Turing =====
@@ Ligne 103: / Ligne 67: @@
   * 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 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.
+  - Concevez la machine qui, partant de l'écriture binaire d'un nombre $n$, termine avec l'écriture binaire de $2\cdot n$
+  - 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>
+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>
+=== Exercice 5 ===
+Concevez un programme qui commence avec un nombre binaire $u$ et qui termine avec $u$ écrit à l'envers.
+Par exemple ''11010'' termine avec ''01011''.
+===== Définition théorique =====
+<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.