La machine universelle de Turing

Les possibilités d'une cMachine

Sur le ruban d'une cMachine, Turing garde toujours une case entre chaque chiffre (0 ou 1) du nombre calculé en binaire. Il appelle F, (pour "Figure", « chiffre » en français) les cases du nombre et E (pour Effaçable), les cases intermédiaires. Un symbole dans une case E est une marque concernant le chiffre à sa gauche. Ces cases E servent de mémoire pour prendre des notes et savoir où la machine en est dans son déroulement.

La section "3. Examples of computing machines"  de l'article de Turing montre des exemples de tables de cMachines pour en expliquer les possibilités.

Lorsque les m-configurations sont désignées par un seul symbole, ce qui n'est pas obligatoire, on peut représenter le déroulement complet d'une cMachine de la façon suivante : à chaque exécution d'une configuration de la machine, on écrit le contenu du ruban et on insère la m-configuration de l'étape à suivre à gauche de la case qui est dans la machine. Ainsi, on a la configuration complète de la machine à chaque étape de son déroulement ainsi que sa configuration pour l'étape suivante comme dans la table qui décrit la cMachine. Un 2-points (:) est placé entre chaque étape.

Turing donne l'exemple d'une cMachine1 qui écrit le nombre : 0010110111011110 ... où il y a un 1 de plus après le 0 suivant et ce, à l'infini. Au départ, il n'y a rien sur le ruban et la cMachine est dans la m-configuration b.

   Configuration             Comportement

m-config. symbole     opérations        m-config.

     b     vide    Pə,R,Pə,R,P0,R,R,P0,L,L  o

     o       1     R,Px,L,L,L               o

     o       0                              q

     q     0ou1    R,R                      q

     q     vide    P1,L                     p

     p       x     E,R                      q

     p       ə     R                        f

     p     vide    L,L                      p

     f     0ou1    R,R                      f

     f     vide    P0,L,L                   o

Le souligné (_) représentant une case vide, les premières étapes du déroulement sont donc représentées comme suit :

b:əəo0_0:əəq0_0:əə0_q0:əə0_0_q:əə0_0p1: etc.2

Turing utilise la lettre ə (schwa en hébreu et utilisée en phonétique) pour marquer le début du nombre calculé. On voit que cette représentation peut être écrite sur un ruban de cMachine qu'elle contient le nombre généré à mesure de son calcul.

Cette façon de représenter le déroulement d'une cMachine est fondamentale pour la UMachine qui a la description de la cMachine à exécuter notée sur son ruban et qui doit écrire le nombre calculé sur ce même ruban ...

La section "4. Abbreviated tables" de l'article de Turing décrit comment on peut raccourcir les tables des cMachines et ainsi les rendre plus faciles à comprendre et plus génériques en les abrégeant (abbreviate en anglais). Les configurations qu'il y décrit sont nécessaires à la UMachine.

Il arrive souvent (comme à tout programmeur en informatique) qu'une cMachine ait des m-configurations très semblables qu'on pourrait remplacer par une seule3. Voici par exemple, 2 m-configurations (Il pourrait y en avoir plus.) qui seraient réparties dans une table plutôt complexe :

m-config.  symbole   opérations  m-config.

...

     x      @             R        c

     x      sinon         L        x

...

     t      @             R        b

     t      sinon         L        t

...

On peut voir que ces 2 m-configurations font presque la même chose. Turing les remplace par une seule m-configuration en utilisant une variable comme on le fait en algèbre et ainsi abréger la table en remplaçant les 2 m-configurations par cette seule :

   f(A)      @             R        A

   f(A)      sinon         L       f(A)

La lettre majuscule A est la variable dont les valeurs possibles doivent être des m-configurations de la machine. Il faut donc fournir la valeur de A pour que la machine puisse passer dans la m-configuration f. Conséquemment, lorsque les opérations d'une m-configuration quelconque se termine en mettant la machine dans cette m-configuration f, il faut mettre une m-configuration à la place du A comme suit par exemple :

Si la cMachine avait cette rangée dans sa table :

     j       1ou0          L,L     f(c)

elle exécuterait les configurations suivantes :

     f       @             R       c

     f       sinon         L       f

Attention : La m-configuration f(A) n'est pas exécutable comme telle par la machine. Elle représente autant de m-configurations qui la remplaceront qu'il y aura de m-configurations qui seront les valeurs de A. (Ci-haut, A = c.) Cette utilisation des variables ne sert qu'à abréger la table de la cMachine.

Turing utilise aussi les lettres minuscules du grec comme variables à être remplacées par un symbole pouvant être écrit sur le ruban. Pour les lettres majuscules qui représentent des m-configurations, il utilise la police de caractères gothique. Il appelle "squeleton tables" (« tables squelettes » en français) ces parties de table qui décrivent les m-fonctions.

Il appelle m-functions les m-configurations comportant des variables. On peut même utiliser plusieurs variables pour une m-fonction comme la suivante qui cherche un symbole particulier, ici α,  qui doit être à gauche du ə :

  f(C,B,α)   ə             L       f1(C,B,α)

  f(C,B,α)   sinon         L       f(C,B,α)

  f1(C,B,α)  α                     C

  f1(C,B,α)  pas α         R       f1(C,B,α)

  f1(C,B,α)  vide          R       f2(C,B,α)

  f2(C,B,α)  α                     C

  f2(C,B,α)  pas α         R       f1(C,B,α)

  f2(C,B,α)  vide          R       B

Nous laissons le lecteur transcrire ces 8 rangées qui résulteraient d'une rangée se terminant par (qui auraient à exécuter) f(z,y,x) ...4

Turing a appelé cette m-fonction f pour "find" soit « trouver ». Elle est utilisée par la UMachine.

Étant donné qu'une m-fonction est une m-configuration, une variable peut aussi avoir une m-fonction comme valeur. Turing utilise régulièrement cette imbrication de m-fonctions (une m-fonction dont une variable est remplacée par une m-fonction) pour sa UMachine. Il indique que par exemple, si on avait la m-fonction p(C) et la m-configuration q, on pourrait avoir p(q) comme m-configuration à suivre. Comme p(q) est une m-configuration, on pourrait donc avoir p(q) comme valeur de C et ainsi faire exécuter p(p(q)) et donc aussi p(p(p(q))), p(...p(q)...) à l'infini5.

Une autre configuration dont Turing a besoin pour sa UMachine efface n'importe quel symbole puis passe à n'importe quelle m-configuration. Il utilise une imbrication de m-fonctions et la lettre e pour "erase". Elle appelle d'abord la m-fonction f pour trouver le premier α puis effacer le symbole voulu et aller à C ou aller à B s'il ne le trouve pas.

  e(C,B,α)                         f(e1(C,B,α),B,α)

  e1(C,B,α)                E       C

On voit ici que "e1(C,B,α)" est la valeur du C de la m-fonction "f(C,B,α)".

Il utilise aussi une autre version de la m-fonction e, celle-ci à 2 variables qui boucle pour effacer tous les α puis aller à B au lieu de C :

  e(B,α)                           e(e(B,α),B,α)

Avec ces 2 m-fonctions précédentes, Turing utilise aussi :

  e(b,x)                           e(e(b,x),b,x)

et

  q                                e(q,b,x)

Il y a donc 2 m-fonctions du même nom mais avec un nombre différent de variables. C'est encore très utilisé aujourd'hui et ça s'appelle le polymorphisme (plusieurs formes).

Turing poursuit avec les autres tables squelettes qu'exécute la UMachine. Elles sont présentées dans la sous-page : Les tables de la UMachine.

Notes :

1. Cette machine a 5 m-configurations : b, o, q, p et f. Même si p est répété 3 fois, c'est une seule et même m-configuration.

2. On peut s'amuser à trouver les configurations complètes suivantes et ainsi pratiquer notre lecture des tables de Turing ...

3. Les programmes d'ordinateur, comme tout algorithme, ont souvent à refaire certaines mêmes étapes. En informatique, on appelle ces étapes « sous-routines » ou « fonctions ». Dans un programme, on écrit la fonction une seule fois et on l'appelle chaque fois qu'on a besoin de l'exécuter.

4. La 3ème rangée serait :

m-config.  symbole   opérations  m-config.

  f1         x                     q

5. On se rappelle qu'une machine ne doit pas avoir une infinité de m-configurations à cause de l'exigence de Hibert.

L'encodage d'une cMachine

La section "5. Enumeration of computable sequences" de l'article de Turing décrit comment traduire n'importe quelle cMachine en une séquence unique de symboles qu'on pourra inscrire sur le ruban de la UMachine.

En utilisant beaucoup plus de m-configurations et aucune m-fonction1, pour chaque rangée de toute table d'une cMachine, la colonne opérations peut ne contenir qu'une seule des 9 opérations élémentaires suivantes : E - Pα - R - L - E, R - E, L - Pα, R - Pα, L - rien2. Les noms des m-configurations n'ayant aucune signification pour la cMachine, on peut tout simplement les numéroter q1, q2, ... , qR . De même pour les symboles sur le ruban, on peut les numéroter S0, S1, S2, S3, etc. où S0 signifie vide, S1 = 0, S2 = 1, S3 et les suivants, les autres symboles utilisés.

Ainsi, la première rangée de la table qui écrit le nombre : 0010110111011110 ...

m-config. symbole     opérations        m-config.

     b     vide    Pə,R,Pə,R,P0,R,R,P0,L,L  o

peut s'écrire :

     q1     S0     PS3                      q2

     q2     S0     R                        q3

     q3     S0     PS1                      q4

et ainsi de suite (S3 représentant ə).

On remarque que les 2 colonnes m-config. n'ont que des symboles de la forme qi et que la colonne symbole n'a que des Sj.

Comme on peut remplacer l'opération E (effacer) par PS0 (écrire vide) et remplacer R et L par PSj,R et PSj,L où PSj réécrit le symbole lu Sj, toute table de cMachine peut s'écrire qu'avec seulement 3 formes de rangées puisqu'on a plus besoin que de 3 formes d'opération soient : PSk,L - PSk,R - PSk soient :

qiSjSkLqm - qiSjSkRqm - qiSjSkNqm

N pour "no move" i.e. pas déplacer. Pas besoin du P car tout Sk est à être écrit. Ce qui fait que toutes les rangées d'une table ont exactement les mêmes 5 éléments.

Pour le codage d'une table, Turing remplace les qx (q1, q2, etc. pour qi et qm)  par D suivi de x fois la lettre A, les Sy (Sj et Sk) aussi remplacés par D mais suivi de y fois C. On n'a donc besoin que des 6 lettres A, C, D, L, R et N et d'un ';' pour encoder toute rangée de la table d'une cMachine. Par exemple, q5 se code DAAAAA et S3, DCCC. Ce sont donc les lettres A et C qui indiquent si D représente une m-configuration q ou un symbole S. Il appelle "standard description" ou S.D., le résultat de ce codage.

La première ligne de la table ci-haut devient donc : 'q1S0S3Nq2' et sa S.D. est donc 'DADDCCCNDAA'. En remplaçant les lettres ACDLRN et le ; par les chiffres 123456 et 7, le D.N. serait '31332225311', un nombre naturel.3

C'est ce type de codage qu'a fait Gödel en utilisant les nombres premiers pour remplacer tout énoncé mathématique par un nombre naturel. C'est aussi ce qu'on utilise aujourd'hui avec les nombres en binaire pour tout ce que peut faire un ordinateur.

Notes :

1. On n'a pas à se préoccuper des m-fonctions avec leurs variables parce qu'elles doivent être transcrite en m-configurations simples pour créer la cMachine.

2. Ici, α est une variable car elle représente n'importe quel symbole.

3. Nous laissons au lecteur le soin de coder en S.D. puis en D.N. les 2 autres rangées de la table. On peut imaginer la longueur extrême que peut avoir le D.N. avec de très longues séquences de A (imaginons q47) d'une cMachine complexe.

La Machine universelle de Turing

La section "6. The universal computing machine" de l'article de Turing décrit le comportement de base de la UMachine qu'il désigne par U.

Lorsque le début du ruban de U contient la description standard (S.D.) d'une cMachine (que Turing désigne par M), U va calculer le même nombre que M mais attention, U ne produit pas le nombre de la même façon que M le fait. Nous voyons ici comment U procède.

Turing indique d'abord qu'on peut créer une cMachine, qu'il désigne par M', qui produit la séquence des configurations complètes d'une M sur les cases F de son ruban tel qu'expliqué à la section 3. Par contre, au lieu d'utiliser les lettres des m-configurations et les symboles du ruban, M' utilise l'encodage en S.D. de la section 5. Pour produire cette séquence, M' lit la S.D. de M qui est sur son ruban, cette S.D. indiquant exactement ce que M fait à chaque étape.

Finalement, pour que M' représente ce que peut faire U, M' insère les chiffres du nombre calculé produits par M entre chaque configuration complète.

La section "7. Detailed description of the universal machine" de l'article de Turing décrit la table de la UMachine.

Pour trouver le début de la S.D. de la cMachine à exécuter, un symbole 'ə' se trouve sur une case-F suivi d'un autre 'ə' sur la case-E juste à sa droite puis un ';' sur la case-F suivante, ce qui donne : 'əə;'. La S.D. de la cMachine à exécuter se trouve sur les cases-F à droite de ce 'əə;', laissant les cases-E vides entre chaque lettre et se termine par '::' qui est un seul symbole.

Pour la cMachine de l'exemple précédent, le début du ruban de U contiendrait :

əə; D A D D C C C N D A A ; ... ::   > les '::' étant un seul symbole.

Étant donné que U écrit les configurations complètes de M, U va écrire les symboles A, C, D, 0, 1, u, v, w, x, y et z. 0 et 1 composent le nombre calculé et les 6 lettres minuscules sont les notes prises dans les cases-E.

Les 4 premières rangées de la table de U sont :
    b                         f(b1,b1,::)

    b1  R,R,P:,R,R,PD,R,R,PA  anf

   anf                        q(anf1,:)

   anf1                       con(tom,y)

La table complète de U avec les tables squelettes dont elle se sert se trouvent à la sous-page  Les tables de la UMachine.

La UMachine commence par trouver le '::' à la fin de la S.D. de M puis écrit ':' suivi de D suivi de A sur les cases-F suivantes car la première m-configuration de toute cMachine est q1. Le ':' placé devant sépare aussi chaque configuration complète de M.

Ensuite, la m-configuration anf marque les lettres écrites par des 'y'. Après le '::', le ruban de U contiendra : ': DyAy'

Par les m-configurations suivantes et les tables squelettes qu'elles appellent, U va générer la séquence des configurations complètes de M.

Notes :

1. xxx

Sources

Charles Petzhold, The Annotated Turing, éditions Wiley, 2008

Wikipédia en français et en anglais