NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 26/04/2016

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

LOGIQUE

 

Débutants

Logique

Intelligence artificielle

 

Glossaire

Logique

 

 

INDEX

 

 

Logique

 

Alan Turing

Introduction

Algorithmes

Jeux

Théorie

Machine de Turing

Systèmes experts

Rx neuronaux

Programmation

Automate

Lambda-calcul

 

Sommaire de cette page

>>> Film en 2015: Imitation Game

>>> Alan Turing – Biographie

       >>> Énigma et son décryptage

>>> Machine de Turing – Approche

>>> Résolution

>>> Instructions

>>> Résultat

>>> Automate

>>> Décidabilité

>>> Le test de l'imitation

 

 

 

  

 

Voilà les résultats José. La bonne nouvelle c'est que l'ordinateur a bien passé le test de Turing. La mauvaise, c'est que toi, par contre, tu l'as raté!

 

Les machines un jour pourront résoudre tous les problèmes, mais jamais aucune d'entre elles ne pourra en poser un !

Einstein

 

Les gens normaux... croient que si ça marche, c'est qu'il n'y a rien à réparer. Les ingénieurs croient que si ça marche, c'est que ça ne fait pas encore assez de choses.           

Scott Adams, Le principe de Dilbert

Voir Pensées & humour

 

 

 

ALAN TURING

&

MACHINE DE TURING

 

 

Alan Turing (1912-1954): le "ADAM" des ordinateurs.

 

Tous les ordinateurs et microprocesseurs d'aujourd'hui sont encore basés sur le principe énoncé par Turing.

 

Son aspect élémentaire et basique sert également à déterminer si un calcul peut être réalisé sous forme automatique (algorithme).

 

 Anglais : Turing machine

 

Actualité janvier 2015

Nous (Parenthèse Cinéma) souhaitons vous informer de la sortie au cinéma le 28 janvier 2015 du film IMITATION GAME, réalisé par Morten Tyldum. Graham Moore (né en 1981) a reçu l'Oscar du meilleur scénario adapté en février 2015. Il s'agit de l'adaptation de la biographie: Alan Turing ou l'énigme de l'intelligence (Alan Turing: The Enigma) d'Andrew Hodges (1992).

 

1940 : Alan Turing, mathématicien, cryptologue, est chargé par le gouvernement britannique de percer le secret de la célèbre machine de cryptage allemande Enigma, réputée inviolable. À la tête d’une équipe improbable de savants, linguistes, champions d’échecs et agents du renseignement, Turing s’attaque au chef-d’œuvre de complexité dont la clef peut conduire à la victoire. C’est le portrait d’un homme qui contribua à changer le cours de la Seconde Guerre mondiale mais se retrouva condamné par la société de l’époque en raison de son homosexualité et en mourut.

 

Nous avons rédigé un dossier pédagogique destiné plus particulièrement aux professeurs d’histoire et de mathématiques. Il comprend de nombreux éclairages sur la vie et les travaux d’Alan Turing, le fonctionnement de la machine Enigma et le contexte historique. Ce dossier propose également plusieurs décryptages à résoudre en classe, avec à la clé des places de cinéma à gagner pour découvrir le film. Vous pourrez le télécharger sur le site du film à la rubrique « Document pédagogique » en cliquant ICI

L’équipe Parenthèse Cinéma

 

 

 

Biographie d'Alan Turing

 

Alan TURING (1912-1954 /41 ans)

 

*    Mathématicien britannique.
 

*    24  décembre 2013: Alan Turing gracié par la reine Élisabeth.

*    Il avait été condamné pour "outrage aux bonnes mœurs " et contraint à la castration chimique en raison de son homosexualité.

*    Considéré comme "l'Einstein des mathématiques",  Alain Turing est mort en 1954 à l'âge de 41 ans, empoisonné au cyanure. Suicide?

*    Alan Turing a joué un rôle décisif pour briser les codes nazis. La machine Énigma (version navale) était utilisée par les sous-marins allemands croisant dans l'Atlantique Nord pendant la Seconde Guerre mondiale. Elle servait à crypter les messages. Certains historiens estiment que le décryptage de ces codes a précipité la chute d'Hitler, qui autrement aurait pu tenir un ou deux ans de plus.

*    Durant sa courte existence, Alan Turing sera parvenu à poser les fondations de l'informatique moderne et à définir les critères de l'intelligence artificielle encore en vigueur: le fameux "test de Turing" qui se fonde sur la faculté d'une machine à tenir une conversation.

 

Au Cambridge King's Collège.

 

Du temps de Bletchley Park.

 

Marin au périscope d'un sous-marin. Symbolise la réussite de Turing à décrypter l'Énigma navale (baptisée Dolphin).

 

Énigma

 

 

La B.O.M.B.E

D'après RTS.Ch 25/12/2013 – & nombreux articles dans la Presse

 

Biographie chronologique d'Alan Turing

1912

0

Naissance  à  Londres

1926-31

14 à 19

École de Sherborne.

1930

18

Mort de son ami Christopher Morcom.

1931-34

19-22

King's College (Université de Cambridge).

1932 …

20

Mécanique quantique, probabilité, logique…

1933

21

Il connait les travaux de Bertrand Russel sur les fondements de es mathématiques.

1936

24

Machine de Turing, calculabilité, calculateur universel.

Gödel ne conclut pas sur la décidabilité en mathématiques. Turing va s'y attaquer.

1936-38

24-26

Université de Princeton.

Ph.D en logique, algèbre, théorie des nombres.

1936-37

/

Publie: On computable numbers, with an application to the Entscheidungsproblem, texte qui se rapporte à la machine de Turing.

1938-39

26-27

Retour à Cambridge.

Traite de la machine Énigma.

1839-42

27-30

Conçoit la "BOMBE", machine de décryptage d'Énigma avec le mathématicien Gordon Welchman.

1942

30

Décrypte les messages d'Énigma marine installée à bord des sous-marins allemands.

1943-45

31-33

Chef consultant en cryptologie auprès des Américains.

1945

33

National Physical Laboratory à Londres.

1946

34

Concepteur précurseur en calculateurs et en programmation. Turing conçoit les plans du premier ordinateur moderne, mais n'a pas les moyens de le réaliser.

1947-48

35-36

Programmation, réseaux de neurones, intelligence artificielle.

1948

36

Université de Manchester avec premières applications mathématiques sur ordinateurs. Il anticipe de plusieurs décennies l'intelligence artificielle et les réseaux de neurones.

1950

38

Test de Turing caractérisant l'intelligence d'une machine. Il est le premier à écrire des programmes informatiques, dont le programme d'un jeu d'échecs dont ses collègues se moquent. Une passion inutile, disent-ils.

1951

39

Fellow of the Royal Society (FRS).

Théorie non-linéaire de la vie biologique

1952

40

Arrêté pour homosexualité.

Perd ses habilitations en matière de sécurité.

1953-54

41-42

Travaux sur la biologie et la physique restés inachevés.

1954

42

Décès par empoisonnement au cyanure: meurtre ou empoisonnement?

 

 

Sportif

Marathon en 2 h 46 min 3 s.

Seulement 11 s de plus que le champion olympique de l'époque (1948).

 

 

 

Décryptage de la machine Énigma

 

Énigma et son décryptage

 

Principe du codage Énigma

*    La clé de codage est changée tous les jours selon des instructions communiquées à tous les utilisateurs.

Une lettre à coder est transformée par trois rotors puis une boite de câblage pour ressortir sous une forme cryptée. à travers ces arcanes la lettre A, par exemple, devient K.

 

*    Choix de trois rotors parmi cinq qui comporte 26 lettres. Ce qui offre:

(5 x 4 x 3) x (263) = 1 054 560 possibilités.

 

*    Boite de câblage transformant 10 paires de lettres et laissant les six restantes inchangées. Ce qui offre:

26! / (6! x 10! x 210) = 150 738 274 937 250 possibilités.

 

*    La machine Énigma transforme une lettre en une autre selon:

158 962 555 217 826 360 000 possibilités.

 

 

Machine Énigma

 

*    Selon une capacité supérieure à celle du moment, prenons une machine capable de tester un million de code à la seconde.

*    Il faudrait:

159 1018 / (106 x 3600 x 24 x 365,25) = 5 000 000 années.

*    Inconcevable! Turing et son équipe vont réduire ce temps à une petite demi-heure en exploitant plusieurs trouvailles dont les suivantes:

*     Les Allemands émettent un bulletin météo (Wetterbericht) tous les matins lequel se finit par "Heil Hitler". Les analystes vont chercher en priorité de tels mots, sans oublier les formules de politesse ou les grades militaires.

*     Le codage des lettres possède une propriété remarquable: une lettre n'est jamais codée par elle-même. Les analystes vont chercher les cas où aucunes lettres ne sont communes entre les mots connus et le texte crypté.

*     Par ailleurs, un test mené jusqu'à découvrir une incompatibilité invalide du même coup toutes les solutions intermédiaires.

… et la "bombe" de Turing pour décrypter Énigma

(celle-ci fut construite par l'US Navy

avec l'aide de Turing)

 

Grâce à l’ingéniosité de Turing et de ses collègues, la plupart des messages  allemands interceptés sont décryptés dès 1942.

Les Polonais avaient développé leurs propres méthodes adaptées au premières versions d'énigma. Turing contribue à la construction des "bombes" plus sophistiquées utilisées par la Marine allemande, notamment à bord des sous-marins (U-Boat).

 

Turing cherche à décoder les machines de cryptage

comme un scientifique essaie de trouver les lois de la nature.

 

 

Turing, un homme décisif pour la victoire de 1945

 

En 1939, de retour de Princeton, Turing est convoqué à Bletchley Park avec un autre mathématicien et des personnes d'horizons divers. Le but; décoder les messages radio des Allemands. l'équipe dispose d'une machine Énigma venue de Pologne sans en connaitre le mode d'emploi. Les Allemands considèrent leur machine Énigma comme la machine de cryptage absolue.

Turing à l'idée d'une machine pour casser le codage: le BOMBE. Elle sera fabriquée en série et va décoder des milliers de messages. C'est la première fois que la machine empiète sur l'intelligence humaine; le début de l'intelligence artificielle.

Les combats aériens sont désormais en faveur des Britanniques. Les Allemands se reportent sur la guerre sous-marine. Établissement de la base des sous-marins à Lorient. L'amiral Dönitz met en place la tactique de la meute: un SM en patrouille qui détecte un convoi américain en informe le QG, lequel  focalise tous les SM sur le convoi. C'est 20 navires qui coulent d'un coup!

La machine Énigma des U-boat, baptisée Dolphin, est plus complexe que la machine terrestre. La Hut 8 à Bletchley est dédiée à la machine Dolphin, à sa tête Alan Turing. Après des semaines de recherches, Turing a la révélation en une nuit: utiliser les statistiques, traquer les "résonances" (coïncidences) et pondérer les possibilités. Sa méthode est nommée Banburisme.

L'équipe reçoit un coup de pouce du fait de la saisie d'une machine Énigma, avec ses codes pour quelques semaines, dans un SM en difficulté, abandonné par les Allemands et investi par les Britanniques. Tous les messages allemands sont décodés et les convois protégés des attaques des U-Boat.

Turing et trois collègues plaident en faveur de moyens auprès de Churchill qui les leur accorde. Bletchley passe de l'artisanat à une véritable industrie.

Fin 1941, les États-Unis entrent en guerre.

Les Allemands inventent une nouvelle machine de cryptage (Tunny) basée sur le code numérique des télescripteurs et non plus le morse. Turing en réalise une réplique assez rapidement, et finit par décoder les messages. Cette fois, ce sont les Russes qui vont profiter des informations interceptées.  Ils repoussent une attaque fomentée par Hitler et se dirigent vers Berlin.

Le décodage des messages reste laborieux. Turing cherche à le systématiser avec une machine.  Tommy Flowers (1905-1998) est spécialiste des tubes à vide et se propose de réaliser cette machine qui comporterait de l'ordre de 2000 lampes. Sur un critère de fiabilité, son projet est refusé. Têtu, il se lance malgré tout dans le projet. Il développe Colossus, le premier ordinateur électronique programmable du monde, et va aider à décrypter les messages allemands. Le rêve de Turing est réalisé.

 

 

 

 

 

Colossus

 

En 1944, Colossus décode tous les messages allemands et va servir à tester la réception d'une grande manœuvre d'intoxication. Il faut faire  croire aux Allemands que le débarquement aura lieu à Calais (opération Fortitude). Ce qui sera le cas.

 

 

 

À la fin de la guerre, Turing et ses collègues sont laissés dans l'ombre, secret militaire oblige. Même, Turing en sait trop, il est une menace pour le gouvernement britannique.

1945 – Turing conçoit les plans du premier ordinateur moderne, mais n'a pas les moyens de le réaliser.

1948 – Il anticipe de plusieurs décennies l'intelligence artificielle et les réseaux de neurones.

1950 – Il est le premier à écrire des programmes informatiques, dont le programme d'un jeu d'échecs dont ses collègues se moquent. Une passion inutile, disent-ils.

 

Turing continue son entrainement à la course à pied et passe très près de la sélection pour les Jeux Olympiques.

Il a une aventure avec un jeune homme et, en mars 1952, il est condamné pour outrage aux mœurs. Pour vaincre son homosexualité, il devra subir une castration chimique. Son corps change. Il est inquiet. Il a du mal à se concentrer … On le retrouve mort en juin 1954 avec du cyanure dans le corps et une pomme sur sa table de nuit.

En 2013, la reine accordera son pardon royal.

La pomme de Newton  La pomme de Turing  La pomme d'Apple ???

Voir Histoire des ordinateurs / Histoire de l'informatique

 

 

 

 

Machine théorique de Turing

 

Machine de Turing – Approche

 

*    Je me pose le petit problème simple indiqué ci-dessous, tout en souhaitant l'automatiser. Aujourd'hui, c'est un jeu d'enfant avec un programme. Voyons la base de cette réalisation.


 
Problème

Chaque fois qu'il y a une suite de 1 (Chaîne de 1).

Je souhaite ajouter un et un seul 1 à la suite.

 

Départ         0 0 1 1 1 0 0                                              

Arrivée         0 0 1 1 1 1 0                                              

 

Principe

 

*    On va examiner la suite des bits (0 et 1)

en séquence de la gauche vers la droite, et

former une autre chaîne en fonction des données de chaîne de départ.

*    Turing avait imagé la chose:

Il utilise une bande perforée qui défile devant la tête d'un lecteur,

la chaîne de bits ayant été inscrite sur la bande.

La nouvelle chaîne de bits sera imprimée sur une autre bande.

 

Je vais simplifier la machine historique de Turing pour les besoins d'une introduction simple.
 

 

 

Résolution

 

Tableau de marche

 

Bilan

 

 

 

Instructions

 

Ce que l'on cherche

L'idée consiste à recenser les ordres qui sont communs: chaque fois que c'est comme ça, je fais cela.

Le but étant de disposer d'ordres (instructions) très généraux.
 

Tentative

On pourrait dire chaque fois que:

*      je lis un 1, j'écris un 1 => instruction 1,

*      je lis un 0, j'écris un 0 => instruction 2.

 

Mais, on a constaté que ce n'est pas toujours vrai.

Il faut tenir compte de l'état d'une variable (mémoire) interne.

On va donc trouver quatre cas possibles:

 

Baptêmes

 

Ce que je sais

Bit lu en entrée

E

Variable d'état interne

V

Ce que je fais

Bit à écrire en sortie

S

Ce que devient la variable interne

W

 

 

Quatre cas possibles (Attention: récapitulatif logique et non chronologique)

 

 

 

 

Résultat en résumé

 

*    Pour ajouter un 1 à une chaîne de 1 inscrite sur une bande, la bande est lue bit à bit et

pour chacun des bits,

on examine la liste des quatre instructions ainsi résumées:  
 

 

*    En plus, à chaque cycle, la valeur de V devient égale à la valeur de W du calcul précédent:  Vn = Wn – 1

 

 

 

 

Automate

 

*    On a vu le procédé imaginé par Turing avec la bande perforée.

*    On peut imager également avec un autre concept: celui de l'automate

Voir le développement en automate
 

 

 

Décidabilité

 

*    Étant donné un problème bien défini, soumis à une machine de Turing, la question est de savoir si la machine va trouver un point d'arrêt.
Turing  a montré (1937) qu'il n'existe pas d'algorithme qui permette de connaître cette réponse

 

*    De nombreux problèmes de mathématiques se résument à cette question fondamentale.
La théorie des machines de Turing est équivalente à la théorie des fonctions récursives.

*    Turing avec sa machine et Church avec son lambda-calcul ont chacun montré qu'il n'y a pas d'algorithme général pour décider d'une question mathématique.

 

*    Le fameux 10e problème de Hilbert est insoluble.
Existe-t-il une procédure automatique qui résolve tous les problèmes de mathématiques les uns après les autres ?

*    Conjecture de Turing et Church.
Un problème ne pouvant être résolu par une machine de Turing ne peut l'être par l'esprit humain.
La démonstration fait appel à

*    divers types théoriques de machines de Turing,

*    une démonstration par l'absurde, et

*    un procédé du type de la diagonale de Cantor.

Elle est expliquée dans le livre The emperor's New Mind de Roger Penrose.

Voir Théorie décidabilité / Toute pensée est un (lambda) calcul

 

 

Le test de l'imitation

Jeu qui consiste à isoler trois personnes: un homme, une femme et une tierce personne. Celle-ci doit deviner qui est l'homme et qui est la femme, sachant que "homme et femme" doivent s'employer à brouiller les cartes. Le moyen de communication doit être neutre (dialogue via des ordinateurs par exemple).

Turing s'inspire de ce jeu pour proposer son test – le test de Turing – la tierce personne doit reconnaitre un humain ou un ordinateur. En cas d'échec, la machine est réputée avoir réussi le test. Elle a un comportement "humain".

ELIZA, programme de conversation pionnier en 1964, puis ALICE, nettement plus performant en 1995 sont les plus connus des agents conversationnels (chatbot ou chatterbot). Sans réussir le test de Turing, ALICE a remporté le prix Loebner relatif au test de Turing.

Vous pouvez vous amuser avec ALICE sur Internet:

 

 

 

 

 

 

 

Suite

*    Systèmes experts

*    Automate

Voir

*    Dualité

*    Complexité de Kolmogorov

*    Énigmes et paradoxes

*    Événements chronologiques

*    Histoire de l'informatique

*    Histoire des ordinateurs

*    Incomplétude

*    LogiqueIndex

*    Multimédia et informatiqueIndex

*    Outils de la logique

*    Phyllotaxie vue par Turing

*    Raisonnement

*    Turing et le Bureau 47

Livre

*    L'homme qui en savait trop – Laurent Alexandre et David Angevin – Robert Laffont – 2015

*    The emperor's New Mind de Roger Penrose

Sites

*    La vie d'Alan Turing, l'explication de l'algorithme d'Enigma (vidéo de "e-penser")

*    L'héritage d'Alan Turing (pdf) – CNRS (2012)

*    Alan Turing – La réhabilitation d'un grand mathématicien – Cité des Sciences et de l'Industrie – texte et documentation vidéo.

Film

*    Imitation Game – Morten Tyldum – Sortie le 28 janvier 2015 – Voir dossier et biographie de Turing (pdf)

*    La drôle de guerre d'Alan Turing – Comment les maths ont vaincu Hitler – Denis Van Waerebeke – 2015

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Logique/IAturing.htm