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

La machine de Turing est un modèle mathématique d'une machine1 à calculer théorique. Elle fut définie par le mathématicien britannique Alan Turing (1912-1954) dans un article qu'il écrit en 1936 alors qu'il est encore étudiant en premier cycle au King's College de l'université de Cambridge.

Nous allons découvrir cet article2 et pourquoi il l'a écrit, et expliquer en détails cette machine et son fonctionnement. Puis, nous allons montrer comment elle a engendré nos ordinateurs3, tablettes, calculettes, etc.

Turing est considéré comme le père de l'informatique théorique et de l'intelligence artificielle. D'ailleurs, la plus haute distinction en informatique s'appelle le prix Turing. Il est remis à chaque année par l'ACM, la plus importante association d'informaticiens. On l'appelle le « prix Nobel » de l'informatique.

Le talent de Turing fut reconnu alors qu'il est encore étudiant au 1er cycle en recevant le titre de Fellow qui lui apportait certains privilèges dont des bourses. Avant même de graduer, il avait réussi à démontrer le fameux théorème de la limite centrale en théorie des probabilité qui cependant, l'avait déjà été.

Son article s'intitule « Sur les nombres calculables4 avec une application au problème de la décision ». Turing y définit comme étant calculable, tout nombre pouvant être généré par sa machine. Celle-ci lui permet de répondre ensuite au problème dit de la décision qui fut posé par le mathématicien David Hilbert.

1. Cette machine est très simple ; c'est ce qui fait sa puissance. Elle est décrite au début de la section "Une cMachine de Turing". La lecture des sections précédentes n'est pas nécessaire pour la comprendre.
Attention : La machine qui a rendu Turing célèbre dans la population en général et dont il est question dans le film "The Imitation Game" n'est pas celle dont il est question ici. Dans ce film, il s'agit d'une machine électronique développée par Turing appelée "BOMBE" qui décrypte les messages produits par la machine Enigma utilisée par les allemands lors de la 2ème guerre mondiale. De plus, le titre du film réfère au « Test de Turing » qui décrit comment vérifier si une machine est intelligente, ce qui est encore autre chose.

2. Une copie (en anglais) de l'article en format .pdf se trouve à cette adresse ICI.

3. Un ordinateur est une machine à calculer numérique électronique programmable. Par programmable, on entent qu'on peut changer le calcul que la machine réalisera. Au lieu d'être numériques, certaines machines à calculer furent analogiques et au lieu d'être électroniques, furent mécaniques ou électro-mécaniques. Il est à noter qu'un ordinateur ne peut produire que des nombres calculables au sens de Turing.

4. Le titre original est : "On computable numbers with an application to the entscheidungsproblem". Pour « calculable », Turing a utilisé le mot anglais "computable" d’où le nom "computer" pour désigner ce qu'on appelle en français un ordinateur. (En anglais, les mots "compute" et "calculate" sont synonymes.)

Version du 27 sept. 2022

Les chiffres en exposant réfèrent aux notes à la fin de chaque section.

Les termes soulignés en gras renvoient aux articles de Wikipédia en français.

Pour la machine universelle, voir la sous-page UMachine.

Sommaire

Le contexte historique de l'article de Turing
Le problème de la décision de Hilbert
Le théorème d'incomplétude de Gödel
L'article de Turing
Une cMachine de Turing
La machine universelle
Le développement des ordinateurs

Le contexte historique de l'article de Turing

• Au Vème siècle av. J.-C.,

le pythagoricien grec Hippase de Métaponte (530-450 BC) démontre que l'hypoténuse d'un carré de côtés 1 (qui est la racine carrée de 2) n'est pas un nombre commensurable qu'on appelle aujourd'hui rationnels. Pour les pythagoriciens, c'était hérétique car ils croyaient que tous les nombres possibles de la Nature étaient soient des nombres entiers soient des rapports de nombres entiers qu'ils appelaient commensurables. Depuis, on a découvert d'autres sortes de nombres comme les imaginaires et défini les nombres algébriques, transcendants et autres.

• 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 est utilisée en mathématiques jusqu'au XIXème siècle au moment où on mathématise les règles de logique. 

• 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 qui sont déduits des axiomes en appliquant des règles de déduction logique. Cette approche formelle appelée axiomatique est encore utilisée en mathématiques modernes.

• 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, les chiffres 0, 1, 2, etc. A cette époque, le mathématicien perse Al-Kwârizmî (vers 780-850) développe la technique de résolution de problème qu'on appelle algorithme du nom de son auteur. Les procédures qu'on a appris à l'école pour additionner, multiplier, diviser, extraire la racine carrée des nombres en sont des exemples.

• A la Renaissance,

les européens s'intéressent aux connaissances des grecs et des arabes et les Galilée, Copernic et autres 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.

• 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.

• 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érations2 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 pourraient 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).

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.

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 calcule les tables de vérité des 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.

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. Ça 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. Pour ce faire, il a utilisé des axiomes dont les termes n'ont pas de signification et ne définissent que des relations entre ces termes. Les mathématiques devenaient très abstraites car on pouvait remplacer les termes point, droite et cercle par n'importe quel autre mot comme cheval, justice et carnaval.

• 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 paradoxes générés par ces nouvelles théories.

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 Frege.

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 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.

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édure qui peut décider si un énoncé peut être prouvé ou pas.

Le problème de la décision consiste à trouver si une telle procédure existe et Hilbert est convaincu qu'elle existe2. 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.

Notes :

1. Hilbert a ajouté le décidabilité en 1928. Elle est complémentaire à la complétude, les deux étant souvent confondues à tort.

2. 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. ».

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étude qui démontre que n’importe quelle théorie qui inclut l'arithmétique et qui est cohérente, va toujours comporter au moins un énoncé qui est vrai sans qu'on puisse le déduire des axiomes de cette théorie. La complétude du programme de Hilbert est donc impossible. Gödel venait de porter un coup dur au programme de Hilbert : toute théorie mathématique restera incomplète ce qui assure du boulot aux mathématiciens pour longtemps !

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. 

En 1936, le mathématicien américain Alonzo Church (1903-1995) est reconnu pour son langage mathématique qu'il appelle  « lambda 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 au programme de Hilbert.

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 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'aucun algorithme ne peut faire ce qui est attendu par Hilbert.

Cependant, il ne sait pas que Church1 l'a devancé de quelques mois dans la démonstration que le 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 peut faire un algorithme. 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 machine en détail dans l’article. Cette machine doit être suffisamment simple pour pouvoir faire ce que n'importe quel algorithme peut faire. Il indique qu'on peut aussi définir qu'une fonction ou toute autre transformation mathématique est calculable si son résultat peut être obtenu par sa machine.

En 1936, aucune machine (de celle de Pascal3 à 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é de la 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'algorithme4 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, pi (3,14159...) est un nombre calculable mais l'algorithme qui le produit s'exécutera à l'infini étant donné que pi a un nombre infini de décimales. Cependant, on se rappelle qu'Hilbert exige que la procédure de décision doit s'exécuter en un nombre fini d'étapes.

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 considère déjà les êtres vivants, animaux et plantes comme des machines qu’on peut décrire mathématiquement. Il a d'ailleurs fait des travaux reconnus sur ce sujet.

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). Une cMachine est la description d'un algorithme spécifique suivant un tout petit nombre de règles très simples5. Une cMachine calcule un nombre qui n'est fait que des chiffres 0 et 1.

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, sur son ruban, la description codée de la cMachine comme pour l'approche de Gödel.

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êt6 » 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 ordinateurs ne sont pas prêts de remplacer les mathématiciens ...

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 (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. 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.

4. Une procédure est une séquence d'actions aboutissant à un résultat attendu. Des parties de la séquence peuvent être répétables ou être réalisées sous condition.

Un algorithme est une procédure mathématique exprimée dans un langage précis. La manière d'extraire une racine carrée par une personne qui écrit sur papier est un exemple d'algorithme.

Un programme est un algorithme dont les actions sont réalisables par un ordinateur. Les actions 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.

5. 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.

6. 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 (cMachine).

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

Certains symboles sont les chiffres du nombre qui est calculé. 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.

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 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 f1. Elle peut écrire 0 et 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).

Le tableau suivant décrit la machine2. 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 se décrire à l'aide d'un tableau à 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 tableau.

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. 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.

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

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 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 unique. 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 indique qu'il n'existe pas de procédure qui peut déterminer si un nombre naturel quelconque est le D.N. d'une cMachine qui soit "circle-free" i.e. qui n'est jamais bloquée à une étape où elle ne peut plus écrire de chiffres dans les cases F.

Notes :

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

Le développement des 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 puces 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 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.

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)

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

Wikipédia en français et en anglais

(Les articles en anglais sont de bien meilleure qualité.)