Faire tourner une machine de Turing — exercice corrigé d'enseignement scientifique (terminale) (chapitre 11)

Faire tourner une machine de Turing

De la machine de Turing à l'intelligence artificielle · niveau 2

Énoncé

On reprend la table du cours : en état $q_{1}$ , lire $1$ donne « écrire $0$ , aller à gauche, rester en $q_{1}$ » ; lire $0$ donne « écrire $1$ , aller à gauche, passer en $q_{f}$ » ; lire $⊔$ donne « écrire $1$ , aller à gauche, passer en $q_{f}$ ». Le ruban porte $⊔ 111 ⊔$ , la tête est sur le dernier $1$ , l'état est $q_{1}$ . 1. Dérouler l'exécution étape par étape. 2. Vérifier le résultat en décimal. 3. Pourquoi la troisième ligne de la table est-elle indispensable ? 4. Cette machine pourrait-elle multiplier par deux ?

Corrigé

1. Étape $1$ : lit $1$ , écrit $0$ , va à gauche, reste $q_{1}$ . Ruban $⊔ 110 ⊔$ . Étape $2$ : lit $1$ , écrit $0$ , gauche, $q_{1}$ . Ruban $⊔ 100 ⊔$ . Étape $3$ : lit $1$ , écrit $0$ , gauche, $q_{1}$ . Ruban $⊔ 000 ⊔$ . Étape $4$ : la tête est maintenant sur la case vide à gauche ; elle lit $⊔$ , écrit $1$ , va à gauche et passe en $q_{f}$ . Ruban $1000$ . Arrêt.

2. $11 1_{2} = 4 + 2 + 1 = 7$ et $100 0_{2} = 8$ . La machine a bien ajouté $1$ .

3. Sans elle, la machine s'arrêterait sur la case vide sans avoir écrit la retenue, et donnerait $000$ au lieu de $1000$ . Cette ligne traite le cas où la retenue se propage au-delà du nombre, c'est-à-dire exactement le cas où le nombre est formé uniquement de $1$ . C'est un cas particulier — et l'on retrouve la leçon de la section sur les bogues : les fautes se logent dans les cas limites.

4. Non, pas avec cette table : une machine de Turing est définie par sa table, et celle-ci ne décrit que l'ajout de $1$ . Il faudrait une autre table. En revanche, une machine universelle pourrait exécuter l'une ou l'autre, puisqu'elle prend la table elle-même comme donnée. C'est toute la différence entre une machine spécialisée et un ordinateur.