La machine de Turing :
La genèse de l’informatique

Sommaire

Bref rappels mathématiques
Le problème de la décision de Hilbert
L'article de Turing
Une cMachine de Turing
La machine universelle
Le développement de l'informatique

Brefs rappels mathématiques

• Les sortes de nombres :

Au Vème siècle av. J.-C., le pythagoricien grec (disciple de Pythagore) Hippase de Métaponte (530-450 BC) démontre que la longueur de l'hypoténuse d'un carré de côté 1 qui est la racine carrée de 2 (√2) selon le théorème de Pythagore, n'est pas un nombre commensurable qu'on appelle aujourd'hui rationnel. Pour les pythagoriciens, ceci était hérétique car ils croyaient que tous les nombres possibles de la Nature étaient commensurables, c'est à dire soit des nombres entiers soit des quotients (ratio, d'où rationnel) de nombres entiers. Depuis, on a découvert plein d'autres sortes de nombres comme les imaginaires (racine carrée d'un nombre négatif).

Pour son article, Turing a défini les nombres qui peuvent être produits par une machine et qu'il a appelé calculables.

• La logique mathématique :

Au IVème siècle av. J.-C., le philosophe grec Aristote (384-322 BC) met au point une technique de déduction logique appelée syllogisme qui permet de déduire les vérités de la Nature. Cette approche de logique fut utilisée en mathématiques jusqu'au XIXème siècle au moment où on mathématise les règles de logique. L'application de cette nouvelle logique mathématique est imposée aujourd'hui pour prouver tout théorème. C'est l'intérêt qu'avait Turing pour la logique qui l'a amené à écrire son article.

• L'axiomatique :

Vers l'an 300 av. J.-C., le mathématicien grec Euclide (vers 325-265 av. J.-C.) rassemble les connaissances grecques en mathématiques dans un célèbre ouvrage intitulé « Éléments ». Pour la rédaction de son ouvrage, Euclide développe ses sujets, dont le principal est la géométrie, en utilisant 3 types d'énoncés1 : des axiomes, des définitions et des théorèmes, ces derniers étant déduits des axiomes en appliquant des règles de déduction logique. C'est cette approche appelée axiomatique qui est utilisée pour toutes les mathématiques d'aujourd'hui.

L'article de Turing va démontrer que cette approche ne permet pas d'établir si un énoncé mathématique peut être prouvé ou pas.

• Les algorithmes :

Au moyen âge, les arabes reprennent les travaux des grecs et continuent à faire avancer les sciences. Ils nous ont apportés les noms en « al » comme algèbre et algorithme, l'étoile Altaïr, nos chiffres 0, 1, 2, etc. A cette époque, le mathématicien perse Al-Kwârizmî (vers 780-850) développe toute une collection2 de procédés de résolution de problèmes mathématiques à la portée de tous qu'on appelle algorithmes du nom de son auteur. Les procédés qu'on a appris à l'école pour additionner, multiplier, diviser, extraire la racine carrée des nombres sont des exemples d'algorithmes.

Les machines de Turing n'exécutent que des algorithmes et mais on peut toujours définir une machine de Turing qui va exécuter un algorithme qu'un humain peut effectuer avec papier et crayon, quelque soit le problème.

• La mécanisation de l'écriture des mathématiques

A la Renaissance, les européens s'intéressent aux connaissances des grecs et des arabes et les Galilée, Copernic et autres scientifiques reprennent le développement des sciences. Avec les nombreuses langues utilisées et les sciences qui évoluent, on a besoin de grammaires faites de règles strictes d’écriture pour être sûr qu’on se comprenne bien et que tout écrit soit vérifiable. C’est ainsi qu’on mécanise les langues et l'écriture des théories scientifiques, dont les mathématiques, comme si tout devait pouvoir être écrit par des machines dont celles de Turing.

• L'axiomatique pour toutes les mathématiques :

A partir de la Renaissance, les mathématiques et les approches pour en faire se diversifient beaucoup : des nouvelles théories sont continuellement développées pour répondre aux besoins des nouvelles découvertes en sciences, en technologies, en économique, etc. Les mathématiciens vont vouloir définir une approche unique applicables à toutes les mathématiques à partir de l'axiomatique.

• L'algèbre de Boole :

Au XIXème siècle, alors que l'arithmétique n'étudiait que les nombres représentant des quantités ou des proportions, le mathématicien britannique George Boole (1815-1864) arithmétise la logique utilisée en mathématiques en développant une algèbre (l'algèbre de Boole) qui définit les opérations3 de logique telles que «si-alors », « et », « ou », etc. sur les valeurs « vrai » et  « faux » qui ne sont pas des nombres, supprimant ainsi toute ambiguïté dans les déductions que font les mathématiciens. Les machines à calculer pourront ainsi faire des déductions logiques.

 Charles Sanders Peirce et Gottlob Frege vont compléter cette algèbre en y intégrant le calcul des prédicats : « Quel que soit » (ou Pour tous) et « Il existe » (ou Certains) afin de fournir une grammaire précise des énoncés mathématiques4.

• La machine de Babbage :
En 1837, le mathématicien britannique Charles Babbage (1791-1871) définit une machine à calculer programmable par cartes perforées qui est l’ancêtre mécanique des ordinateurs. De telles cartes étaient encore utilisées par les ordinateurs IBM des entreprises dans les années 1980. Sa machine est tellement complexe qu'elle n’a pas encore été construite en date d'aujourd'hui. C’est pour programmer cette machine qu'Ada Lovelace (1815-1852) conçoit des algorithmes faisant officiellement d’elle le premier programmeur de l’histoire. Le langage de programmation de la Défense des États-Unis porte d'ailleurs son nom.

• D'autres machines à calculer :
En 1866, l'économiste et logicien britannique William Stanley Jevons (1835-1882) construit une machine mécanique qu'on a appelée le « piano logique » et qui effectue les opérations de l'algèbre de Boole. En 1887, le professeur de logique de Princeton, Allan Marquand (1853-1924) en développe une autre mécanique mais un peu plus complète que celle de Jevons qu'on a appelée la « machine logique » puis conçoit les circuits électriques pour une autre.

• David Hilbert et la géométrie d'Euclide :
A cette époque, on savait qu'Euclide avait posé des hypothèses qui n'étaient pas déduites des axiomes étant donné qu'il se fiait à ce que le lecteur savait ce qu'était un point et une une droite. Ceci a fait que ses axiomes et les déductions qu'il en faisait n'étaient pas complètes ni complètement cohérentes. Le mathématicien allemand David Hilbert (1862-1943) a donc repris toute la géométrie d'Euclide pour les éliminer.
C'est en partie par son intérêt pour les travaux de Hilbert que Turing va écrire son article.

• Le fondement des mathématiques :

A l'aube du XXème siècle, un petit groupe de mathématiciens dont Hilbert va se poser de sérieuses questions sur le fondement des mathématiques car, depuis la théorie des ensembles développée dans les années 1870 par le mathématicien allemand Georg Cantor (1845-1918) et avec la diversification des théories mathématiques, les approches traditionnelles n'arrivent pas à résoudre les paradoxes5 générés par ces nouvelles théories.

• Principia Mathematica :
Pour répondre à ces problèmes, ces mathématiciens vont favoriser l'approche axiomatique d'Euclide et l'utilisation d'une logique mathématique plus rigoureuse comme celle de Boole, pour démontrer les théorèmes. Parmi eux, le philosophe et mathématicien britannique Bertrand Russell (1872-1970) publie avec Alfred N. Whitehead « Principia Mathematica » qui propose, dans les années 1910, un fondement plus rigoureux de l'ensemble des théories mathématiques en modernisant l'axiomatique ainsi que la logique basée sur l'approche de Gottlob Frege.
C'est aussi en partie par son intérêt pour les travaux de Russell que Turing va écrire son article.

• Le théorème d'incomplétude de Gödel :
En 1931, le mathématicien autrichien Kurt Gödel (1906-1978) fut rendu célèbre pour son théorème d’incomplétude6 qui démontre que n’importe quelle théorie qui inclut l'arithmétique et qui est cohérente (dont les théorèmes ne se contredisent pas), va toujours comporter au moins un énoncé qui est vrai sans qu'on puisse le déduire des axiomes de cette théorie. Pour y arriver, Gödel a défini un procédé qui assigne un nombre naturel unique à tout énoncé mathématique en utilisant les nombres premiers. Turing va utiliser cette approche pour pour son article.

Notes :

1. Un axiome (qu'Euclide appelait postulat) est un énoncé qu'on considère vrai par évidence et dont on n'apporte pas la preuve. Par exemple : « Par deux points, passe seulement une droite. »
Une définition donne la signification d'un terme qu'on utilise en particulier. Par exemple : « Un cercle est l'ensemble des points situés à une égale distance d'un point central. »
Un théorème est un énoncé dont la véracité est prouvée en appliquant les règles de déduction logique à partir des axiomes et des théorèmes déjà prouvés. Par exemple : « Si un triangle possède 2 angles égaux alors les côtés opposés sont aussi égaux ».

2. Cette collection fut publiée dans un livre intitulé "Abrégé du calcul par la restauration et la comparaison" dont le titre en arable contient "al-jabr" qui donna son nom à l'algèbre dont il est l'origine. Dans ce livre, Al Kwârizmî utilise la notation décimale proposée par des savants indiens et qui est faites des chiffres 0 à 9 qu'on qu'on qualifie d'arabe !

3. Cette algèbre n'utilise que 2 valeurs : 1 qui représente « vrai » et 0 qui représente « faux ». Les « si-alors », « et », « ou », etc. sont des opérations arithmétiques semblables aux additions, multiplications, etc. Par exemple : « 0 et 1 = 0 »,  « 1 ou 1 = 1 », « si 1 alors 0 = 0 », etc.

4. Le syllogisme suivant est bien connu : « Tous les hommes sont mortels, or Socrate est un homme, donc Socrate est mortel. »
En calcul des prédicats on écrit : Si (Pour tous les hommes, un homme est mortel.) et (Il existe Socrate qui est un homme.) alors (Socrate est mortel.)
Chacun de ces 3 énoncés est soit vrai soit faux (soit 1 soit 0). Avec l'algèbre de Boole, si les 3 énoncés sont vrais on obtient : « 1 et 1 alors 1 = 1 ». Le calcul des prédicats est donc programmable.

5. Le paradoxe du barbier : « Le barbier du village rase tous les hommes du village qui ne se rasent pas eux-mêmes. » est utilisé pour illustrer les paradoxes engendrés par la théorie des ensembles.

6. « Quand j'ai fait mes études universitaires en mathématiques à la fin des années '70, Gödel était la grande vedette mathématique du XXè siècle grâce à ce théorème. »

Le problème de la décision de Hilbert

Dans les années 1920, c'est Hilbert qui mène la modernisation des mathématiques et ce, depuis au moins 1900, année où il présente ses problèmes à résoudre au XXème siècle. Il veut refonder toutes les mathématiques sur une approche axiomatique qui est  différente de celle de Russell. Il présente son « programme » en 1920 auquel adhèrent les plus imminents mathématiciens et ceux-ci veulent que ça réussisse. Ils considèrent que toutes les mathématiques doivent être un langage unique avec sa grammaire.

Pour que cette approche soit le fondement recherché par son programme, Hilbert considère qu'elle doit inclure certaines caractéristiques dont :

• Cohérence : on ne doit pas pouvoir déduire des théorèmes qui se contredisent.

• Complétude : tout énoncé vrai doit être déductible des axiomes.

• Décidabilité1 : on doit avoir une procédure2 qui peut décider si un énoncé3 peut être prouvé ou pas.

Par son théorème d'incomplétude, Gödel venait de porter un coup dur au programme de Hilbert : toute théorie mathématique restera incomplète. Les  mathématiciens auront du boulot pour longtemps !

Le problème de la décision (entscheidungsproblem) consiste à trouver si la procédure de décidabilité existe et Hilbert est convaincu qu'elle existe4. Il indique que la procédure doit finir par s'arrêter sinon on n'obtient jamais la décision. Il ne spécifie rien d'autre sur la nature de cette procédure considérant que les mathématiques consistent à faire des calculs dont les procédures sont essentiellement des algorithmes. Cependant, le mathématicien britannique G. H. Hardy est convaincu que la procédure attendue n'existe pas. De plus, il faut déterminer clairement ce qu'on entend par « procédure ».

En 1936, le mathématicien américain Alonzo Church (1903-1995) est reconnu pour son langage mathématique qu'il appelle  « lambda-calcul » (λ-calcul) par lequel il démontre que la décidabilité du programme de Hilbert n'a pas solution mais ce, juste avant que Turing présente son article. Church venait de porter le coup fatal aux caractéristiques souhaitées par Hilbert.

Notes :

1. C'est avec le mathématicien allemand Wilhelm Ackermann qu'Hilbert a ajouté le décidabilité en 1928. Elle est complémentaire à la complétude, les deux étant souvent confondues à tort.

2. Une procédure est typiquement une séquence d'actions visant à obtenir un résultat attendu. Des parties de la séquence peuvent être répétables ou être réalisées sous condition. Les algorithmes sont des procédures.

3. Par énoncé, on entend une affirmation précise concernant un sujet mathématique qui est soit vraie soit fausse. « Il y a un nombre infini de nombres premiers. » est un exemple d'énoncé.

4. Tellement convaincu, qu'on a inscrit sa célèbre citation concernant la décidabilité sur sa pierre tombale : « Wir müssen wissen. Wir werden wissen. » qui signifie : « Nous devons savoir. Nous allons savoir. ».

L'article de Turing

C’est en suivant le cours sur les « Fondements des mathématiques » de Max Newman (1897-1984) au King's College au printemps 1935 que Turing s'intéresse aux travaux de Russell, au programme de Hilbert et au théorème de Gödel présentés dans ce cours. Étant donné que c'est un sujet récent, le problème de la décision le motive à écrire un article par lequel il veut démontrer qu'aucune procédure ne peut faire ce qui est attendu par Hilbert et que Hardy avait raison.

Cependant, il ne sait pas que Church1 l'a devancé de quelques mois dans la démonstration que ce problème n'a pas de solution. Au moment où Turing présente son article pour le publier, Max Newman prend connaissance de celui de Church. Grâce au soutien de son professeur, Turing publie son article dans la revue "Proceedings of the London Mathematical Society" le 12 novembre 1936 en y ajoutant une mention de l'article de Church. Par la suite, Turing écrira sa thèse de doctorat sous la direction de Church ...

Pour son article, Turing doit définir clairement ce que signifie « calculer » et ce que doit faire la procédure attendue par Hilbert. Il commence donc par définir ce qu'il qualifie de calculable2. Il y explique qu’un nombre est calculable s’il peut être produit par une machine puis il décrit sa sorte de machine en détail dans l’article. Cette sorte de machine doit être suffisamment simple pour pouvoir faire tout ce que n'importe quel algorithme3 peut faire.

Turing a l'idée originale de faire en sorte que toute machine puisse être décrite par un nombre unique (une séquence de chiffres) comme Gödel l'avait fait pour les énoncés. Ainsi, tout algorithme peut être représenté par un nombre unique. Il indique aussi qu'on peut définir qu'une fonction ou toute autre transformation mathématique est calculable si son résultat peut être obtenu par sa machine.

Dans l'esprit de Turing, être calculable veut dire être réalisable par un être humain suivant un nombre fini d'étapes considérant qu'il a une mémoire limitée. Turing perçoit déjà les êtres vivants, animaux et plantes comme des machines4 qu’on peut décrire mathématiquement. Ses observations l'amène à décrire le processus mental d'un être humain en une séquence d'étapes simples qu'il décrit par une sorte de machine théorique. Il a d'ailleurs fait des travaux reconnus sur ce sujet.

En 1936, aucune machine (de celle de Pascal5 à celle de Babbage) n’avait été conçue pour faire ce qu’il fallait pour que Turing l'utilise pour répondre au problème de la décision. Ada Lovelace avait compris que pour achever la machine de Babbage, il fallait définir clairement ce qu'elle pouvait faire. C'est finalement la définition claire de ce qui est calculable ainsi que la simplicité d'une Machine de Turing qui déclenche le développement et permet la construction des premiers ordinateurs électroniques numériques programmables. Jusqu'à ce moment-là, la grande majorité des machines à calculer n'étaient pas programmables car elles ne réalisaient qu'un seul algorithme.

Pour qu'un nombre ou une fonction soit calculable, Turing a définit que l'algorithme qui produit le résultat doit être fait d'un nombre fini d'étapes. Comme les étapes de la procédure peuvent être répétées, l'exécution de l'algorithme peut ne jamais s'arrêter. Par exemple, Π (3,14159...) est un nombre calculable mais l'algorithme qui le produit s'exécutera à l'infini étant donné que Π a un nombre infini de décimales. Cependant, on se rappelle qu'Hilbert exige que la procédure de décision doit finir par s'arrêter.

La 1ère partie (sections 1. à 5.) de l'article de Turing décrit ce qu'il appelle les "Computing Machines" (machines à calculer ou cMachines) pour définir clairement les procédures possibles. Une cMachine est la description d'un algorithme spécifique suivant un tout petit nombre de règles très simples. Une cMachine calcule un nombre qui n'est fait que des chiffres 0 et 16.

La 2ème partie (sections 6. à 9.) de l'article décrit ce qu'il appelle la Machine Universelle (UTM pour Universal Turing Machine ou UMachine). La UMachine peut faire tout ce que n'importe quelle cMachine peut faire en lui fournissant la description de la cMachine qu'on veut exécuter. Turing a défini la manière de décrire toute cMachine par un simple nombre entier comme l'avait fait Gödel pour les énoncés mathématiques.

La 3ème partie (sections 10. et 11.) de l'article démontre que le problème de la décision ne peut être résolu et ce, en utilisant la Machine Universelle. Avec cette UMachine, Turing démontre d'abord que le « problème de l'arrêt »7 n'a pas de solution. Ce problème cherche s'il existe une cMachine qui peut déterminer si n'importe quel algorithme va finir par s'arrêter pour aboutir au résultat. De cette réponse, il déduit qu'il n'existe aucune procédure qui peut décider si un énoncé mathématique peut être prouvé ou pas, ce qui démontre la non-décidabilité du programme de Hilbert.

On a ainsi la preuve qu'aucune machine ne pourra déduire toutes les mathématiques dont on a besoin par l'approche axiomatique souhaitée par Hilbert: Les limites des machines de Turing nous montrent les limites de l'intelligence artificielle et qu'il restera toujours des problèmes mathématiques et des questions qui ne peuvent être résolus ou répondues par un algorithme donc par une machine.

Notes :

1. Juste avant la publication de l'article de Turing, Max Newman l'informe de celui de Church. Il met les 2 hommes en contact et l'année suivante, Turing écrit sa thèse de doctorat sous la direction de Church à l'université Princeton aux USA. Les deux ont écrit une thèse (dite de Church-Turing) qui démontre qu'une fonction est calculable par un humain qui effectue un algorithme si elle est calculable par une machine de Turing et vice versa.

2. Aujourd'hui, on dit qu'un nombre ou une fonction est calculable s'il/elle peut être obtenue par un algorithme ayant un nombre fini d'étapes. Calculer ne veut pas seulement dire faire des opérations arithmétiques sur les nombres comme 4x3=12 mais aussi faire des déductions logiques sur les valeurs « vrai » et « faux » comme : « si vrai alors faux = faux » avec l'algèbre de Boole. Calculer n'est donc pas seulement compter mais aussi de déduire si un énoncé mathématique bien formulé, comme un théorème par exemple, est vrai ou faux. Les nombres calculables sont une catégorie de nombres au même titre que les nombres entiers, réels, complexes, etc.

3. Un algorithme est une procédure mathématique exprimée dans un langage précis.
Un programme d'ordinateur est un algorithme dont les actions sont réalisables par un ordinateur. Les actions, qu'on appelle instructions du programme, ne traitent que des nombres dont certains représentent "vrai" et "faux" (en remplaçant "vrai" par 1 et "faux" par 0). Ces nombres sont ensuite transformés en images, sons, etc. par des appareils intégrés aux ordinateurs comme les écrans et les hauts-parleurs. Ces appareils utilisent les nombres stockés à des endroits spécifiques dans la mémoire de l'ordinateur.
On appelle matériel (hardware en anglais) l'ensemble de ces appareils. On appelle logiciel (software en anglais) l'ensemble des programmes.
Ce qu'on appelle application (même mot en anglais) et son diminutif appli, est un ensemble de programmes qu'on utilise pour effectuer une activité particulière comme un jeu vidéo, un traitement de texte, etc. On qualifie de de base le logiciel qui fait fonctionner les appareils comme afficher à l'écran, lire ou écrire sur un disque, etc. On appelle utilisateur une personne qui utilise une application. On appelle informaticien une personne qui conçoit et/ou écrit du logiciel. Un utilisateur ne fait donc pas d'informatique !

4. Enfant, Turing a comme livre de chevet Les merveilles de la nature que tout enfant devrait connaître. Ce livre présente les organismes vivants comme des machines et Turing en restera fasciné.

5. Pour aider son père qui doit assurer la comptabilité publique de la province de Haute-Normandie, le philosophe et mathématicien français Blaise Pascal (1623-1662) alors âgé de 19 ans conçoit puis fabrique la première machine à calculer. C'est une petite machine mécanique qu’on appelle Pascaline pouvant additionner et soustraire directement des nombres de 6 chiffres et faire des multiplications et des divisions par répétitions. Il en construit une vingtaine dont 8 sont au Musée des Arts et Métiers à Paris.

6. On peut écrire n'importe quel nombre avec les 2 seuls chiffres 0 et 1. C'est le système binaire. Par exemple, 9 en binaire s'écrit 1001 et 3,5 s'écrit 11,1. 

7. Le problème de l'arrêt est un cas particulier du problème de la décision. Les deux étant souvent confondus à tort.

Une cMachine de Turing

Les sections "1. Computing machines" et "2. Definitions" de l'article de Turing définissent ce qu'est une machine à calculer de Turing, une cMachine.

Il commence par définir ce qu'il appelle une machine automatique ("automatic Machine" ou "aMachine") :

• Une aMachine a un ensemble fini (exigé pour la décidabilité) de « m-configurations » (machine-configurations) qui sont les états possibles de la machine et qui servent de mémoire.

• Elle est alimentée d'un ruban infini (sans début ni fin) divisé en cases chacune pouvant contenir un seul symbole1. Il n'y a qu'une seule case à la fois dans la machine. Elle ne peut utiliser qu'un nombre fini de symboles.

• Ce que la machine effectue est déterminé par sa m-configuration et le symbole de la case dans la machine (On dit : du symbole « lu ».). Turing appelle « configuration » tout court, la combinaison des deux.

La machine ne peut effectuer que les 4 opérations suivantes :

• Écrire un symbole dans une case vide,

• Effacer le symbole lu,

• Déplacer le ruban d'une seule case à la fois vers la gauche ou la droite et

• Changer de m-configuration.

La machine effectue donc une séquence d'opérations pour chaque configuration puis se met dans une autre m-configuration ou reste dans la même.  Les opérations indiquent ce que fait la machine selon la configuration.

Turing appelle "computing machine" ou cMachine (machine à calculer) une aMachine qui ne produit que des nombres binaires.

Turing fournit l'exemple d'une cMachine qui écrit le nombre binaire 0101010101... soit une infinité de 01 consécutifs :

La machine a 4 m-configurations ; b, c, e et f2. Elle peut écrire soit 0 soit 1.

R signifie que la machine va à la prochaine case sur la droite (Right).

L pour aller sur la gauche (Left), E pour effacer le symbole, Px pour écrire (Print) un symbole (représenté ici par x).

La table suivante décrit la machine3. Les m-configurations à droite des opérations indiquent dans quelle m-configuration la machine se met après avoir effectué les opérations. Pour les m-configurations, Turing utilise une police de caractères gothique et met les noms des opérations en italique.

   Configuration          Comportement

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

     b      aucun         P0, R       c

     c      aucun           R         e

     e      aucun         P1, R       f

     f      aucun           R         b

Une cMachine peut donc être représentée par une table4 à 4 colonnes et autant de rangées qu'il y a de configurations à considérer. Les 2 colonnes de gauche donnent la configuration qui effectue le comportement particulier. Le symbole est celui de la case du ruban qui est dans la machine. Les 2 colonnes de droite qu'on appelle « comportement », donnent la séquence des opérations effectuées suivie de la m-configuration dans laquelle la machine se met après les opérations.

Au démarrage de la machine, il peut y avoir ou pas des symboles sur le ruban. Elle est dans une m-configuration « de départ » et positionnée sur une case en particulier. Cette configuration donnée est normalement dans la 1ère rangée du tableau5.

Aussi surprenant que ça puisse paraître, une cMachine peut être définie pour calculer un grand nombre de fonctions mathématiques complexes.

Notes :

1. Certains symboles sont les chiffres du nombre qui est calculé qui peuvent n'être que des 0 et des 1. Les cases de ces symboles ne peuvent pas être modifiées. Turing appelle ces cases : 'F' (pour "figure" en anglais, "chiffre" en français). Les autres symboles sont des notes qui assistent la mémoire et qui peuvent être effacées. Il appelle leurs cases : 'E' (pour effaçable, "erasable" en anglais). Une case E sert à marquer le chiffre à sa gauche. Avec suffisamment de symboles différents, une seule case suffit pour marquer un chiffre et avoir la mémorisation qu'il faut.

2. Turing utilise une seule lettre minuscule en police gothique pour distinguer les m-configurations des symboles sur le ruban. Cependant, les m-configurations peuvent être désignées par des expressions plus complexes comme f1(C,B,α) par exemple permettant d'abréger les machines complexes.

3. On peut remarquer que Turing laisse une case vide après chaque chiffre (2 R consécutifs) car la machine universelle en aura besoin.

4. On s'attend habituellement à ce que les machines de Turing effectuent des opérations arithmétiques comme extraire une racine carrée ou simplement multiplier 2 nombres. Pour donner un exemple ultra simple, la table suivante représente une cMachine qui additionne 2 nombres binaires de 2 chiffres chacun :
Les 4 chiffres des 2 nombres sont côte à côte sur le ruban sans espace entre les deux.
Au démarrage, la machine est positionnée sur le chiffre de gauche du 1er nombre.
Les m-configurations sont à 2 chiffres :
    Celui de gauche représente le rang du chiffre sur lequel la machine est positionnée allant du 1er au 4è.
    Celui de droite représente le total atteint au moment où la machine arrive à ce chiffre.
La machine écrit le résultat à droite des 2 nombres en laissant d'abord un espace.
Les nombres binaires à 2 chiffres ne peuvent être que 00, 01, 10 et 11 soient 0, 1, 2 et 3.
Les sommes possibles vont donc de 0 à 6 (0 à 110) soit 7 possibilités de 1 à 3 chiffres binaires.

m-conf symb opérat  m-conf

10      0     R      20

10      1     R      22

20      0     R      30

20      1     R      31

22      0     R      32

22      1     R      33

30      0     R      40

30      1     R      42

31      0     R      41

31      1     R      43

32      0     R      42

32      1     R      44

33      0     R      43

33      1     R      45

40      0   RRP0
40      1   RRP1

...

45      0   RRP1P0P1

45      1   RRP1P1P0

5. Depuis quelques décennies, on a pris l'habitude de spécifier une cMachine par un diagramme plutôt qu'une table comme on le voit dans l'article de Wikipédia. Les m-configurations sont représentées par les disques. Les flèches représentent le passage d'une m-config. à la suivante. Sur les flèches, on a 2 éléments : à gauche du ":" on a le symbole du ruban et à droite, les opérations effectuées. On déduit que la flèche qui n'a pas de source indique la m-config. de départ.

Le diagramme suivant spécifie la même cMachine que l'exemple de Turing :

La machine universelle

La machine universelle de Turing1 est une cMachine dont le ruban contient la définition d'une cMachine que la UMachine va exécuter. Cette définition est le codage de la cMachine en une séquence de symboles n'utilisant que 6 lettres majuscules A,C,D,L,R,N et le ';'. La UMachine commence par décoder la cMachine pour ensuite l'exécuter.

Il faut donc programmer la UMachine en inscrivant le code qui définit la cMachine sur le ruban de la UMachine. Turing a décrit l'algorithme pour effectuer ce codage ainsi que la table de la UMachine. 

C'est encore de cette manière qu'on programme les ordinateurs aujourd'hui. On écrit le programme qui représente l'algorithme (la cMachine) que doit exécuter l'ordinateur (la UMachine) dans un langage qu'il connait, on l'enregistre dans sa mémoire puis on le fait exécuter. Turing appelle même "instructions" le code qui représente les configurations de la cMachine dans la UMachine.

Turing mentionne qu'on pourrait utiliser les 7 chiffres 1, 2, 3, 4, 5, 6 à la place des lettres et 7 pour le ';'.  Ceci ferait que toute cMachine peut être représentée par un nombre naturel décimal unique2. Il appelle ce nombre "description number" ou D.N. Turing identifie par "M(n)", une cMachine dont le nombre n est son D.N.

Pour faire sa preuve de la non-décidabilité du programme de Hilbert, Turing démontre qu'il n'existe aucune cMachine qui peut déterminer si un nombre naturel quelconque est le D.N. d'une cMachine qui n'est jamais bloquée à une étape où elle ne peut plus écrire de chiffres dans les cases F. C'est par la non existence d'une telle cMachine que Turing démontre mathématiquement que la procédure attendue par Hilbert n'existe pas.

C'est en affectant un nombre naturel unique à tout énoncé mathématique possible que Gödel avait put faire sa preuve de la non complétude du programme de Hilbert. Turing a utilisé cette idée de chiffrage pour toute cMachine lui permettant de prouver la non décidabilité du programme de Hilbert.

Notes :

1. Pour une description plus complète, voir la sous-page de la UMachine.

2. Chacun de ces 7 chiffres peut être écrit en 3 chiffres binaires de 001 à 111.

Le développement de l'informatique

Concernant les ordinateurs :

En 1937, à partir de sa thèse de maîtrise au MIT, l'ingénieur et mathématicien américain Claude Shannon (1916-2001) conçoit des circuits électroniques qui peuvent réaliser toutes les opérations de l'algèbre de Boole. Ils font partie des circuits intégrés dans les processeurs de nos ordinateurs.

En 1945, le mathématicien hongrois John von Neumann (1903-1957), reconnu pour son développement de la théorie des jeux et plusieurs autres travaux scientifiques, définit l’architecture des ordinateurs électroniques numériques et ce, à partir de la Machine Universelle de Turing. Cette architecture de von Neumann inclut le mécanisme d'enregistrement des programmes dans l'ordinateur comme le fait la UMachine qui peut contenir la définition de toute cMachine. Elle demeure celle de nos ordinateurs actuels.

Comme l'a fait Gödel pour n'importe quel énoncé mathématique, toute image, son, vidéo, etc. peut être représenté par un nombre naturel. Les ordinateurs vont soit encoder une vidéo lue en des nombres naturels soit en générer une à partir de nombres naturels.

Tout ce qui peut être produit par le processeur d'un ordinateur, aussi moderne soit-il, peut l'être par une machine de Turing.

Concernant les mathématiques :

Dans les années '50, les mathématiciens développent la Théorie des automates, un automate étant une sorte de aMachine de Turing. Le principal concept de cette théorie est l'Automate fini qui s'appelle « Finite-State Machine » en anglais (« Machine à états finis »).

Un automate fini est une machine de Turing qui peut être dans un nombre fini d'états mais un seul à la fois, la configuration d'une machine de Turing étant un exemple d'état. Il peut passer d'un état à un autre, cette transition étant déclenchée par un événement ou une condition.

Sources

Les génies de la science N° 29, TURING Et l'informatique fut, revue Pour la science, nov. 2006 - jan. 2007

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

(Il explique en détails tout l'article de Turing)

Chris Bernhardt, Turing's Vision, The Birth of Computer Science, The MIT Press, 2016

Collection Génies des mathématiques, éditions RBA Coleccionables S. A. U., 2018

(Al Kwarizmi, Boole, Cantor, Euclide, Gödel, Hilbert, Pascal, Turing et von Neumann)

Collection Le monde est mathématique, N° 9, Le rêve de la raison - La logique mathématique et ses paradoxes, éditions RBA Coleccionables S. A. U., 2019

Rachid Guerraoui et Lê Nguyên Hoang, Turing à la plage, l'intelligence artificielle dans un transat, Dunod, 2020

Wikipédia en français et en anglais

(Les articles en anglais sur le sujet sont de bien meilleure qualité !)