GoupillWiki

Outils pour utilisateurs

Outils du site

Piste :
nsi:terminales:calculabilite:machine_turing

Différences

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

Lien vers cette vue comparative

Les deux révisions précédentesRévision précédente
Prochaine révision		Révision précédente
nsi:terminales:calculabilite:machine_turing [2023/02/06 20:50] – goupillwikinsi:terminales:calculabilite:machine_turing [2023/02/06 21:21] (Version actuelle) – goupillwiki
Ligne 40: 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. 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 ===== ===== Des exemples le machines de Turing =====
Ligne 64: 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.   * 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> </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.
nsi/terminales/calculabilite/machine_turing.1675713011.txt.gz · Dernière modification : de goupillwiki