1NSI : Histoire des Ordinateurs : Turing & ses machines

Machines de Turing, \(1936\)

Biographie d'Alan Turing, , \(1912-1954\)

Alan Turing, vers $16$ ans

Un Prototype de Machine Universelle de Turing

En \(1936\), à \(24\) ans, un jeune mathématicien anglais de génie, Alan Turing, publie un article fondateur « On Computable Numbers, with an Application to the Entscheidungsproblem () » / « Sur les nombres Calculables, avec une application au problème de la Décision » , dans lequel il invente une expérience de pensée que l'on nommera par la suite une machine de Turing. Une machine de Turing est une sorte de modèle (de calcul) abstrait de machine, se voulant universelle au sens où la machine peut calculer tout ce qui est calculable... (dans un certain sens qu'il définit/invente au passage), en particulier les mêmes choses que les programmes/algorithmes d'un ordinateur moderne. Au passage: * Il donne une définition de ce qu'est un nombre réel calculable : c'est un réel pour lequel il existe un algorithme ou une machine de Turing permettant d'énumérer la suite de ses chiffres (éventuellement infinie), ou plus généralement des symboles de son écriture sous forme de chaîne de caractères. De manière plus générale, et équivalente, un nombre réel est calculable si on peut en calculer une approximation aussi précise que l'on veut, avec une précision connue. * il invente au passage toute la théorie de la Calculabilité, indépendamment et simultanément qu'Alonzo Church * il démontre que le problème de l'arrêt pour une machine de Turing ne peut pas être résolu par un algorithme, autrement dit le problème de l'arrêt n'est pas 987 : ble/indécidable : il n’est pas possible de décider avec un algorithme (c’est-à-dire avec une machine de Turing) si une machine de Turing donnée s’arrêtera (sur une entrée donnée), ou pas * il résout le problème fondamental de la Décidabilité en arithmétique, indépendamment et simultanément qu'Alonzo Church : Pour tout problème \(P\), existe-t-il toujours un algorithme qui résout ce problème ? La réponse est NON... * il donne un sens plus précis à la notion de programme et de programmation.

Dès Septembre \(1938\), Alan Turing travaille pour la GC&CS (Governement Code & Cypher School), l'ancêtre de l'actuel GCHQ - Governement Communications HeadQuarters (Service Gouvernemental du Royaume-Uni responsable du Renseignement d'origine Électromagnétique et de la sécurité des Systèmes d'Information)

Condamnation pour Homosexualité & Mort

De Cambridge à Bletchley Park, Turing ne faisait aucun mystère de son orientation sexuelle, ouvertement homosexuel, il ne cachait pas ses aventures. Il était d'ailleurs loin d'être le seul. En \(1952\), sa maison de Manchester est cambriolée. Turing porte plainte. Arrêté, le cambrioleur dénonce le complice qui lui avait indiqué l'affaire, un ex-amant occasionnel de Turing. Celui-ci ne nie pas cette ancienne relation. Tous deux sont inculpés d'« indécence manifeste et de perversion sexuelle » d'après le Criminal Law Amendment Act (\(1885\)). Quelques années plus tôt, ce n'aurait été qu'un fait divers (?). Mais, au début des années \(1950\), une affaire retentissante d'espionnage scientifique au profit de l'Union soviétique où sont impliqués des intellectuels anglais homosexuels surnommés les Cinq de Cambridge a rendu les services de contre-espionnage britanniques et américains sensibles à un profil comme celui de Turing.

Le procès est médiatisé. Hugh Alexander fait de son confrère un brillant portrait, mais il est empêché de citer ses titres de guerre par le Secret Act. Turing est mis en demeure de choisir : incarcération ou castration chimique réduisant sa libido. Il choisit le traitement, d'une durée d'un an, avec des effets secondaires temporaires (le coureur à pied svelte qu'il était devient gros, impuissant, ses seins grossissent comme ceux d'une femme), et surtout des effets psychiques profondément démoralisants. Alors qu'il a été consacré, en \(1951\), en devenant membre de la Royal Society, à partir de \(1952\) il est écarté des plus grands projets scientifiques. Toutefois, en avril \(1953\), la « cure » se termine, ses effets s'estompent et Turing recommence à faire des projets de recherche, de voyages en France et en Méditerranée.

Le \(8\) juin \(1954\), dans l'après-midi, Turing est retrouvé mort dans son lit par sa gouvernante, avec une pomme croquée sur sa table de nuit. L'autopsie conclut à un suicide par empoisonnement au cyanure, même si sa mère tenta d'écarter cette thèse. Le moyen d'ingestion du poison aurait été cette pomme qu'il aurait partiellement mangée : une légende tenace et démentie y voit l'origine du logo de la firme Apple.

Machines de Turing

Introduction

Introduction aux Machines de Turing ($10$ min $24$)

Le machine de Turing est un modèle (de calcul) abstrait/virtuel de machine, donc ce n'est pas à proprement parler une vraie machine concrète/mécanique, mais plutôt un concept mathématique abstrait, imaginé par le jeune mathématicien anglais de génie Alan Turing en \(1936\) : * initialement et historiquement, pour répondre à une question mathématique posée \(8\) ans plus tôt par le mathématicien allemand David Hilbert . Il s'agit du problème de la Décidabilité, (en allemand Entscheidungsproblem ) que l'on pourrait formuler sous la forme : Existe-t-il un algorithme qui décide (toujours) si une proposition (quelconque) énoncée dans un système logique est valide ou non ? * Au passage, il donne un sens plus détaillé de la notion de "procédure mécanique" et que l'on appellera plus tardivement un programme/algorithme.

Son fonctionnement peut sembler (très/trop?) simpliste à première vue, mais il est en fait totalement révolutionnaire parmi les appareils mécaniques de calculs existants de l'époque, à tel point que la machine se rapproche théoriquement d'un ordinateur moderne :

Introduction : Qu'est-ce qu'une Machine de Turing ? Une machine de Turing est un modèle (de calcul) abstrait composé de : * un certain matériel virtuel: * un ruban infini (à gauche et à droite), composé de cases contenant * des lettres d'un alphabet de travail \(\Gamma\) (Exemple: l'alphabet binaire : des \(0\) et des \(1\)), et un caractère spécial appelé VIDE * une tête de lecture * certaines opérations virtuelles, appelées actions/transitions \(\delta\) correspondant à un certain "calcul" (dans un sens un peu plus large et différent que d'habitude) * la tête de lecture/écriture peut : * lire/écrire une lettre de l'alphabet dans une case * effacer le contenu d'une case (\(\Leftrightarrow\) écrire le caractère vide) * se déplacer à gauche ou à droite d'une case

**Une partie seulement** du Ruban infini, avec une **entrée** $m=100101$, et une **tête de lecture/écriture** signalée en rouge

Introduction : Exécution d'une machine de Turing * La machine part d'un état initial, qui est caractérisé par : * un mot \(m\) donné en entrée (\(m=100101\) dans l'exemple ci-dessous), * une tête de lecture/écriture positionnée dans une case initiale * la machine passe ensuite par un nombre fini d'états intermédiaires, en exécutant, selon une certaine logique propre à la machine, des actions/transitions/instructions élémentaires précises, dans un certain ordre, qui font passer d'un état à un autre : * un état (intermédiaire) précis est caractérisé par : * la valeur des cases à un instant donné * la position de la tête de lecture/écriture à un instant donné * son nom (en général : \(e_0\), \(e_1\), \(e_2\), etc.. quelquefois \(q_0\), \(q_1\), \(q_2\), etc. ) * Logique d'Exécution C'est la connaissance de la valeur \(x\) de la case courante ET du nom \(e_1\) de l'état courant qui provoque l'exécution d'une certaine action/transition \(\delta\) associée à ce couple (\(e_1\), \(x\)) * Une action/transition \(\delta\) fait correspondre au couple (\(e_1\), \(x\)) la donnée des \(3\) informations suivantes (sous forme de tuple) : * la valeur \(y\) à écrire dans la case courante * le déplacement du ruban ( \(\leftarrow\) ou \(\rightarrow\) ) * le nom \(e_2\) de l'état suivant

<div style="float:right; margin-right:20%; margin-top:-2%;">

| État  | Lit | Ecrit   | Déplace | Suivant|
|:-:|:-:|:-:|:-:|:-:|
| $e_1$ | $x$ | $y$ | *gauche* ou $\leftarrow$ | $e_2$ |

</div>

<env>Notations</env> On écrit quelquefois <enc>$\delta(e_1,x) = (y, \leftarrow, e_2)$</enc> $\,\,$ ou bien :

pour modéliser l'action/transition/instruction élémentaire suivante :
  > * Si, à un instant donné, la machine : 
  >   * se trouve dans l'état $e_1$, et que 
  >   * la tête de lecture lit le symbole $x$ (dans la case courante), 
  > * Alors la machine :
  >   * écrit $y$ à la place de $x$ (dans la case courante),
  >   * déplace le **ruban** vers la gauche
  >   * passe dans l'état $e_2$

La <bred>Table des Actions/Transitions</bred> est la Table contenant exhaustivement, et dans le bon ordre, TOUTES les Actions/Transitions à exécuter

• SI la machine arrive à l'un des états connus comme états finaux, ou états acceptants, ALORS la machine s'arrête : dans ce cas, on note \(prog(m)\) le contenu du ruban SINON, la machine ne s'arrête pas, et l'on a une boucle infinie : dans ce cas \(prog(m)\) n'est pas défini

Interprétation Moderne, en termes de programme/algorithme * La machine calcule le résultat \(prog(m)\) d'une fonction (informatique/mathématique) \(prog\), pour une entrée \(m\) donnée : une machine de Turing se comporte donc, dans notre terminologie moderne, comme un (ordinateur exécutant un) programme/algorithme/fonction \(prog\) spécifique recevant \(m\) en entrée, et renvoyant \(prog(m)\) en sortie. * La Table d'Actions/Transitions de la machine correspond à notre vision moderne de programme/algorithme.

une tentative naïve de Définition

Plusieurs définitions formelles et rigoureuses existent, toutes très proches les unes des autres, nous nous contenterons d'une description un peu plus détaillée :

Une machine de Turing \(M\) est composée de plusieurs concepts :

• Un Ruban Infini (vers la gauche et vers la droite) de cases consécutives, dans lesquelles on peut lire/écrire :
• des symboles d'un alphabet de travail \(\,\Gamma\) fini donné : Tout symbole est possible, mais en pratique, souvent en binaire : des \(0\) ou des \(1\)
• un symbole spécial appelé symbole blanc ou symbole vide, et noté VIDE ou vide (quelquefois \(0\)) par la suite. Par défaut : toutes les cases contiennent initialement le symbole blanc/vide.
• Une Tête de lecture/écriture qui peut :
• être positionnée sur une seule case à la fois
• lire le contenu de la case
• écrire dans la case : e.g. un \(0\) ou un \(1\), ou d'une manière générale, tout autre symbole de l'alphabet de travail \(\, \Gamma\)

• être déplacée :

  • déplacer le Ruban vers la gauche, noté \(\leftarrow\) \(\Leftrightarrow\) déplacer Tête vers la droite, ou bien
  • déplacer le Ruban vers la droite, noté \(\rightarrow\) \(\Leftrightarrow\) déplacer Tête vers la gauche

  ATTENTION : la convention est de donner les déplacements du Ruban (et non PAS de la Tête), mais cela peut varier selon les auteurs et les contextes * un registre d'état qui mémorise l'état courant de la machine de Turing, sorte de point intermédiaire dans le déroulement de la procédure mécanique : * Il existe un état spécial, appelé état initial \(e_0\) (quelquefois \(e_1\)), qui est l'état de départ de la machine avant son exécution : certaines cases peuvent être préremplies avec des symboles de l'alphabet, et on connaît la position de la tête de lecture * Il existe un ensemble fini \(Q\) d'états (intermédiaires) possibles : \(Q=\{e_1, e_2, e_3, ...\}\), chaque état étant caractérisé par la donnée de : * le contenu du ruban * la position de la tête de lecture/écriture

  Logique d'Exécution Le comportement de la machine (comment déterminer la ou les actions à faire) est déterminé par l'état dans lequel elle se trouve ainsi que par la valeur lue dans la case courante, on en déduit alors : quelle valeur écrire dans la case courante, quel est le déplacement du Ruban, quel doit être l'état suivant * un ensemble d'états dits états acceptants \(F \subseteq Q\), ou états finaux ou états terminaux (il peut y en avoir plusieurs), qui correspondent à la fin de la procédure d'exécution de la machine : tous les états finaux seront notés FIN ou fin * Une Table d'Actions/Transitions notée \(\delta\), qui résume en une seule table (de plusieurs lignes), toutes les actions/transitions à faire étant donné l'état courant, et la valeur lue de la case courante : c'est cette Table d'Actions/Transitions qui correspond en fait à notre vision moderne d'un algorithme.

Remarque Écrire le caractère VIDE dans une case revient à effacer un caractère (s'il y en avait un..)

Animation HTML5/JS réalisée par Hugo Lehmann, Centrale Lille Projets,
librement adaptée d’une applet Java écrite par Hamdi Ben Abdallah.

Explications écrites supplémentaires (pour chacun(e) des programmes/Tables d'actions ci-dessus) https://interstices.info/comment-fonctionne-une-machine-de-turing/

Machine Universelle de Turing

Jusqu'à présent, nous n'avons pas dit comment, ni où, était stockées les instructions de la table d'actions/transitions dans une machine de Turing \(M\) : nous avons simplement supposé que la table d'actions/transitions faisait partie intégrante de la machine \(M\). Initialement, Turing envisage de stocker ces informations dans un deuxième ruban, avant de s'apercevoir qu'une telle deuxième machine est en fait équivalente à une machine (dite machine Universelle de Turing \(U\)) avec un seul ruban.

Une machine Universelle de Turing est donc un concept abstrait qui prouve de manière théorique qu'une machine calculante (futurs ordinateurs) peut contenir:

• les données (i.e. les entrées et leurs calculs - intermédiaires ou finaux), mais aussi
• les programmes/algorithmes (i.e. les instructions de la procédure mécanique stockées de la table d'actions/transitions) sous forme d'une chaîne de caractère de l'alphabet de travail (quelconque, mais en pratique, souvent binaire).

Ce principe révolutionnaire en fait le fondement intellectuel de l'architecture matérielle des tout premiers vrais ordinateurs, connue sous le nom d'Architecture de Von Neuman, conçus par John Von Neumann dès \(1946\).

Une **machine de Turing $M$ (quelconque)**
vs une **machine Universelle de Turing $U$**

Une **machine de Turing (quelconque)** $M$ réalise un calcul $prog(m)$, à partir d'une entrée $m$ écrite sur son ruban : cela revient à **identifier une machine de Turing $M$ (quelconque) d'entrée $m$ avec un programme/algorithme $prog$ déterminé, avec une entrée $m$**. Une machine Universelle de Turing $U$ est une machine de Turing qui peut **simuler n'importe quelle machine de Turing $M$ avect n'importe quelle entrée $m$** : * l'entrée $m_U$ de la machine Universelle $U$ est la conjonction de : * la table d'actions/transitions de la machine $M$ à simuler (une *description* de $M$), et de * l'entrée $m$ de la machine $M$ à simuler * L'alphabet de $U$ est (en général) celui de $M$ * La table d'actions/transitions de $U$ est celle de $M$

Interprétation Moderne Une machine Universelle de Turing peut simuler l'exécution de n'importe quel programme/algorithme \(prog\) avec n'importe quelle entrée \(m\) : C'est pourquoi, pour certains mathématiciens (par ex., Martin Davis) une machine Universelle de Turing peut être vue comme un modèle (de calcul) abstrait de :

• l'ordinateur à programme enregistré dit à architecture de Von Neumann, mais aussi de :
• Un Système d'Exploitation (un programme qui peut exécuter tout programme)
• Un Compilateur (un programme qui exécute tout programme, et le convertit un autre chose)
• Le Jeu de la vie est une machine Universelle de Turing : un Jeu qui peut exécuter n'importe quel Jeu...et même n'importe quel autre programme, et dans lequel on peut reproduire toutes les opérations booléennes et arithmétiques

Un Prototype de Machine Universelle de Turing
de fréquence $0,5 Hz$, (durée: $16$ min $44$)

Une Machine Universelle de Turing avec le Jeu de la Vie (durée : $18$ min $40$, repère -Turing- à $11$ min $40$)

Conclusion

On retrouve dans une machine Universelle de Turing tous les principaux éléments précurseurs des ordinateurs modernes :

• un ruban qui modélise la mémoire
• un alphabet de travail pour modéliser le codage binaire (\(0\) et \(1\)) de l'information
• la table d'actions/transitions qui modélisent les instructions d'un programme/algorithme
• Un cycle (état + lecture \(\Rightarrow\) écriture + état suivant + déplacement tête), pour modéliser le cycle d'horloge, et donc aussi la fréquence/cadence d'horloge.

Machines Turing-complètes

On dit qu'un instrument de calcul, contruit en tant que vrai prototype physique de machine calculante, est Turing-complet \(\Leftrightarrow\) il dispose de capacités d'exécution d'algorithmes équivalentes à celles d'une machine Universelle de Turing

Test de Turing \(=\) Imitation Game

Dans l'article « Computing Machinery and Intelligence » (Mind, octobre \(1950\)), Turing explore le problème de l'intelligence artificielle et propose une expérience maintenant connue sous le nom de Test de Turing ou Jeu de l'Imitation (Imitation Game ...) : il s'agit de ce que l'on appelle aujourd'hui un chatbot (agent conversationnel), càd d'une méthode qui permettrait de vérifier qu'un programme est capable de simuler les réponses d'un être humain sans que celui-ci ne se rende compte qu'il parle avec un ordinateur. De nos jours, le test consiste à devoir "tromper au moins \(30\%\) de juges humains (des chercheurs) pendant \(5\) minutes à travers d'un chat (échanges de textes écrits)". En \(2014\), un ordinateur réussit à se faire passer pour la première fois pour un humain (certes, dans le cas d'un garçon de \(13\) ans, d'origine ukrainienne, ce qui justifie que le résultat soit contesté par certains) sur des thèmes non choisis à l'avance. Références : voir par exemple 1. slate.fr, 2014 ou 2. Le monde, 2014. Ce résultat est néanmoins contesté : 3 Blog de Jean-Paul Delahaye...

En \(1950\), Turing fait néanmoins le pari que « d'ici \(50\) ans, il n'y aura plus moyen de distinguer les réponses données par un homme ou un ordinateur, et ce sur n'importe quel sujet » : pari tenu ?

Quelques Repères Historiques

• \(1997\) : l’ordinateur Deep Blue développé par IBM, conçu spécialement pour le jeu d’échecs, a battu Garry Kasparov alors champion du monde et, depuis, d’autres machines ont atteint des résultats comparables. Même les bons joueurs d’échecs reconnaissent que, face à ce genre de programmes et sans information particulière, il leur est impossible de savoir s’ils jouent contre une machine ou contre un être humain. C’est une forme de test de Turing (où le dialogue est limité à des échanges de coups)

• \(2011\) : le programme d'Intelligence Artificielle (IA) nommé Watson, développé par la firme IBM, a réussi à gagner un concours contre les champions du jeu Jeopardy (où des questions générales sont posées en langage naturel). Cette victoire a été analysée comme la réussite d’un test de Turing partiel mais, cette fois, en s’approchant un peu plus près des conditions imaginées par Turing pour son jeu de l’Imitation.

• \(2017\) : le programme d'IA AlphaGo (qui utilise la méthode de Monte-Carlo) développé par l'entreprise Deepmind (créée en \(2010\), et rachetée par Google en \(2014\)), est le premier programme à battre Ke Jie, alors champion du monde du Jeu de Go. En \(2015\), AlphaGo avait déjà battu Fan Hui un joueur professionnel français de Go (2ème dan, et champion européen), puis en \(2016\) il bat largement Lee Sedol, un des meilleurs joueurs mondiaux (9ème dan, considéré le meilleur du monde). AlphaGo combine des techniques d'apprentissage automatique, et de parcours de graphes, associés à des données issues de nombreuses parties jouées avec des humains, d'autres ordinateurs et surtout lui-même. En \(2017\) encore, AlphaGo est remplacé par une version améliorée AlphaGo Zero, qui n'utilise plus la méthode de Monte-Carlo, ni a le besoin d'aucune donnée provenant de parties jouées précédemment entre humains : il joue seulement contre lui-même pour apprendre (aprentissage automatique) Toujours en \(2017\), Deepmind développe AlphaZero (github page) qui généralise l'approche d'AlphaGo Zero à d'autres Jeux que le Go. Dès \(2018\), Deepmind annonce le développement d'AlphaFold, qui prédira dès \(2020\) la structure des protéines de manière révolutionnaire.

Aller plus loin * Conférence (pdf) de Jean-Paul Delahaye : IA et Test de Turing * le projet Leela Zero, en \(2017\), est un projet Open Source basé sur le code d'AlphaGo Zero ouvert librement en \(2017\)

les machines La Bombe (de Turing) \(1938\) vs Enigma \(1918\)

Introduction

Enigma et La Bombe de Turing ($8$ min $00$)

Les machines Enigma, \(1918\)

Machine Enigma

Les machines Enigma, ou machines M pour les allemands, sont des machines électromécaniques portatives servant au chiffrement et déchiffrement, brevetées et développées dès \(1918\) par l'ingénieur en électricité allemand Arthur Scherbius. Pour protéger ses propres brevets, il achète en \(1927\) les droits d'une machine à rotors, développée et brevetée dès \(1919\) par le chercheur hollandais Hugo Koch. Initialement des machines commerciales, dont les premières ventes (même internationales, dès \(1923\)) sont un échec total (pour cause de prix démesuré [?] : l'équivalent de \(30000\,\$\) de nos jours), la machine sera achetée dès \(1926\) par la marine allemande, et dès \(1929\) par l'armée de terre allemande, puis son usage sera étendu à toutes les forces armées allemandes. Cryptanalyse Enigma est complexe : La combinaison de ses \(3\) rotors de \(26\) lettres offre \(159\) milliards de milliards de clés possibles - et elles changent chaque jour. Enigma a été vaincue par une logique fondée sur la connaissance de son fonctionnement interne et l’exploitation des imprudences des chiffreurs allemands, permettant une attaque par la recherche de solutions à l'aide de moyens mécaniques. On ne peut pas exactement parler d'attaque par force brute, car les méthodes ne testaient pas toutes les combinaisons possibles, mais presque.., donc la force brute est la méthode moderne qui s'en approche le plus, de manière juste un peu restreinte.

Unix L'algorithme (simplifié) de chiffrement d'Enigma a été implémenté par un étudiant en tant que commande intégrée dans Unix (dans la librairie crypt). Cette commande a été utilisée par des laboratoires civils et militaires qui croyaient protéger ainsi leurs communications (les travaux de déchiffrement de Bletchley Park restèrent en effet secrets jusqu'en \(1974\)), ce qui a pu faciliter l'espionnage industriel.

La Bombe, \(1938\)

Machine La Bombe d'Alan Turing

La Bombe (elle fait tic-tac quand elle fonctionne) fut un instrument électromécanique initialement inventé et utilisé par les cryptologues polonais en \(1938\) puis modifiée par la suite par les britanniques en \(1940\) à Bletchley Park, grâce à la collaboration des polonais, afin de casser les codes allemands d'Enigma. La première machine La Bombe est conçue vers octobre \(1938\) par le cryptologue polonais Marian Rejewski travaillant au Biuro Szyfrów. En mai \(1940\), les Allemands perfectionnent leur système cryptographique, Turing reprend l'idée des Polonais et conçoit une machine plus performante, la Bombe de Turing, qui sera par la suite modifiée par un autre mathématicien, Gordon Welchman. Turing prendra ensuite la tête de l’équipe chargée de trouver les clés de l’Enigma.