Turing Machine

Lorsque le mathématicien Alan Turing a développé sa théorie, il a imaginé une machine comprenant :

  • un ruban infini sur lequel sont inscrits des symboles,
  • une tête de lecture qui peut lire ou écrire un symbole à la fois,
  • une suite finie d’instructions qui changent le symbole courant et déplacent la tête de lecture.

À quoi sert cette machine ?

Elle décrit simplement le fonctionnement de tout ordinateur. Tout ce qui peut s’écrire comme une suite finie d’instructions, c’est-à-dire tout programme ou algorithme, peut donc être exécuté par cette machine. Avec un ensemble bien choisi d’instructions, une machine de Turing peut simuler n’importe quelle autre machine de Turing : c’est ce qu’on appelle une machine de Turing universelle.

À quoi ça ressemble ?

Une machine de Turing est d’abord une expérience de l’esprit. Néanmoins, rien n’empêche d’en construire une. C’est ce qu’a fait Mike Davey.

(Via Seweryn)

Barbie docteur en informatique

Pour la journée internationale des droits de la femme, et en attendant le Ada Lovelace Day, je continue ma série de portraits de femmes en informatique. Aujourd’hui, je quitte les personnages historiques pour parler d’une contemporaine : Barbara Liskov. Avec le Professeur Liskov, nous quittons le domaine des pionniers (et des pionnières) pour celui de l’industrie informatique moderne ; on passe d’un machin hybride entre l’électronique et les mathématiques à une véritable discipline d’ingénierie. Enfin, qui essaye de l’être…

Barbara_Liskov.PNG.png

Barbara Liskov est arrivée en informatique un peu par hasard. Après son baccalauréat de mathématique à Berkeley en 1961, elle hésite à démarrer des études doctorales. Elle cherche un boulot mais ne trouve que des métiers ennuyeux. C’est comme programmeur qu’elle finit par trouver un métier qui l’intéresse. Elle reprend ses études à l’université de Stanford et en 1968, elle est la première femme à recevoir un doctorat d’informatique aux États-Unis. Son sujet de thèse concerne l’intelligence artificielle pour les échecs et les jeux.

Ses contributions scientifiques sont nombreuses mais on peut les résumer sans trop d’injustice en trois points :

  1. L’abstraction de données. Elle a été une pionnière dans ce domaine. Elle a démontré qu’en adoptant une méthode rigoureuse de développement et en utilisant des formalismes adaptés, on pouvait construire des logiciels à la fois plus complexes et plus sûrs.
  2. Le principe de substitution. Le principe de Liskov est une extension de la notion de type de données (point 1) aux langages orientés objet. Dans un langage orienté objet, on encapsule à la fois des données mais également des comportements. Barbara Liskov a donc développé une méthode de développement basée sur le contrat entre les objets, qui permet de préserver les propriétés des données et d’éviter des comportement inadaptés.
  3. Les systèmes distribués. Elle a développé le premier langage qui permet la programmation distribuée (sur plusieurs machines). Elle dirige le département de méthodologie de la programmation au MIT où elle travaille principalement sur la résistance aux pannes byzantines dans les systèmes distribués.

Pour tout ça (et bien d’autres choses encore), elle a reçu la médaille John von Neumann et le Prix Turing en 2008, pour son travail tant fondamental que pratique pour le progrès de la discipline informatique. Si le prix Turing ne vous dit rien, remplacez le par « Nobel d’informatique ». Si Barbie est ingénieur en informatique, c’est un peu grâce à Barbara.

Sources :
[1] Barbara Liskov, wikipedia.
[2] Barbara Liskov, profile from the National Academy of Engineering
[3] Q&A: Turing Award winner Barbara Liskov, CNET
[4] Barbara Liskov Wins Turing Award, Dr. Dobb’s