1 - Un vrai ordinateur en papier

L'idée

En 1834, le mathématicien anglais Charles Babbage fut l'un des précurseurs de l'informatique.

Son idée était de produire des tables nautiques, astronomiques et mathématiques exactes : à l'époque, les tables sont écrites ou tapées à la main et comportent donc des erreurs de recopies ou de calculs.

La machine mécanique

Babagge fut le premier à énoncer le principe d'un ordinateur. Il s'est inspiré de la machine à tisser Jacquard (inventées en 1801 par le lyonnais Joseph Marie Jacquard) qui utilise des cartes perforées pour encoder les informations.

Partant de ce principe, Charles Babbage imagine un calculateur mécanique qui recevrait instructions et données à partir de la lecture des perforations sur les fiches.

Il passa le reste de sa vie à travailler sur les détails de cette machine analytique, tentant de la faire fonctionner... sans succès.

Un échec ?

Même s'il ne parvint pas à la construire de son vivant, elle n'a été réellement opérationnelle qu'en 1991 (avec l'équivalent des technologies d'époque) lorsque des universitaires ont cherché à la construire à l'aide des plans de Baggage. Avec un peu plus de chance (il avait commis quelques petites erreurs de conception), il aurait pu réussir à construire sa machine. La théorie était bonne et fonctionnelle.

Identification des registres et des cases de la mémoire centrale.

Une adresse commençant par R fait référence à un registre.

Une adresse commençant par @ fait référence à une case de la mémoire centrale.

Jeux d'instructions

Notre machine M10 possède deux jeux d'instructions :

1. les instructions de transfert.

Une instruction MOV DST SRC permet de placer le contenu de la source SRC dans la destination DST.

DST peut être un registre ou une case de la mémoire centrale.

SRC peut être un registre, une case de la mémoire centrale ou une valeur.

Exemples :

MOV RA #3 : place la valeur 3 dans le registre RA.

MOV RA @3 : place le contenu de la case 3 de la mémoire centrale dans le registre RA.

MOV @3 RA : place le contenu du registre RA. dans la case 3 de la mémoire centrale

MOV RA RB : place le contenu du registre RB dans le registre RA.

Plus fort, les crochets peuvent indiquer d'aller lire le contenu de la case mémoire dont l'adresse est contenue dans un registre.

MOV RA #1 : place la valeur 1 dans le registre RA.
MOV RB [RA] : ramène dans le registre RB le contenu de la case mémoire pointée par le registre RA. Sur notre exemple, cela revient à aller lire la case mémoire d'adresse 1, puisque [RA] = @1.

2. les instructions arithmétiques et logiques réalisées par l'UAL (+, , -, *, ET, OU ... ) à partir des deux données reçues,

L'instruction ADD YY XX additionne les contenus liées à YY et XX et place le résultat dans le registre accumulateur.

Schématiquement RA <-- YY + XX.

YY XX peuvent être des cases-mémoires ou des valeurs.

ADD @1 @3 : l'équivalent de RA = @1 + @3.

ADD @2 #5 : l'équivalent de RA = @2 + 5.

L'instruction SUB YY XX réalise la soustraction de YY et XX et place le résultat dans le registre accumulateur.

Schématiquement RA <-- YY - XX.

XX peut être un case de la mémoire centrale ou une valeur.

SUB @5 #3 : l'équivalent de RA = @5 - 3.

Un tout petit rikiki programme

Imaginons que la mémoire centrale contienne ceci :

Voici un programme dans lequel RA indique l'Accumulateur :

ADD @0 @2
MOV @0 RA

Que fait-il  ?

1. ADD @0 @2 place dans le registre RA la somme des contenus de @0 et @2.
2. MOV @0 RA place alors 35 dans la case mémoire 0.

Assembleur ?

L'assembleur est le nom usuel donné aux programmes ci-dessus. Il s'agit de jeux d'instructions qui communiquent directement avec le processeur. Chaque famille de processeurs a donc son propre langage d'assemblage.

Un programme réalisé pour un processeur particulier ne peut donc pas être exécuté par un processeur d'une autre famille. Il s'agit donc d'un langage de très bas niveau ! Par contre, il est très rapide.

Langage machine

En réalité, le langage machine est constitué uniquement des octets reçus par le processeur qui ne sait lire que des bits bien entendu.

La différence est mince avec l'assembleur en réalité. Pourquoi ?

Simplement car l'assembleur est une sorte de traduction directe du langage machine en utilisant des symboles textuels.

Imaginons que le processeur comprenne que lorsqu'il reçoit l'octet  0000 1111 , on désire lui faire faire l'addition des contenus des registres R1 et R2, comme  0001  et  0010 .

Le processeur reçoit donc :

 0000 1111 0001 0010 

Ceci est du langage machine.

Et comme c'est compliqué à comprendre par un humain, les humains ont inventé l'assembleur qui est juste une sorte de traduction entre octet et chaînes de caractères.

Plutôt que de noter

•  0000 1111  pourrait coder ADD entre deux registres;
•  0001 , qui correspond à R1 ou RA;
•  0010 , qui correspond à R2 ou RB.

On obtient alors les instructions du langage d'assemblage qu'on va pouvoir transmettre à un programme nommé... l'assembleur. Et c'est lui qui va transformer le langage d'assemblage en langage machine.

Comme cela, tout le monde est content.

• L'humain comprend ce qu'il veut dire.
• Le processeur reçoit l'unique langage qu'il comprend.

Assembleur, langage d'assemblage

Normalement :

• Le langage machine est la suite d'octets
• Le langage d'assemblage où on transforme juste certaines suites d'octets en bouts de texte
• L'assembleur est le nom du programme qui traduit le langage d'assemblage en langage machine

Mais, tout le monde parle d'assembleur plutôt que de langage d'assemblage.

Alan Turing

Alan Turing (1912-1954) est un mathématicien et cryptologue britannique. Nous allons voir que ses recherches fondent la science informatique.

La machine de Turing

Alan Turing présente en 1936 une machine imaginaire, pure création de l'esprit, nommée depuis machine de Turing.

Une machine de Turing est une machine mécanique virtuelle, un mécanisme simple qui S'IL ETAIT CONCU REELLEMENT permettrait d'exécuter des algorithmes. Elle fut inventée avant le premier ordinateur.

Même sans existence réelle, la machine constitue le modèle de ce qui peut être calculé ou pas. Si un calcul est théoriquement possible sur une machine de Turing, c'est qu'on pourrait la faire calculer par une machine automatique. Avec cette machine de l'esprit, Turing est parvenu à définir ce qui sera calculable un jour sur un ordinateur, une machine qui n'existait même pas encore.

La machine de Turing se compose :

1. d'un ruban infini divisé en cases consécutives qui peuvent contenir un ensemble fini de symboles.
2. d'une tête de lecture-écriture qui permet de lire l'une des cases à la fois ou d'y écrire un nouveau contenu.
3. d'un registre d'état enregistrant un nombre fini d'états (au départ, il contient "ETAT DE DEPART").
4. Une table d'actions. C'est un tableau à deux entrées qui indique ce qu'on doit faire lorsque la machine lit un symbole sur une case et étant dans.un état précis.

Décidable ou indécidable ?

Une catégorie particulière de problèmes est la catégorie des problèmes décidables. Il s'agit des problèmes pour lequel la machine finit toujours par s'arrêter et fournir une réponse OUI si la réponse est OUI sur les entrées fournies, et NON si la réponse est NON.

Les problèmes indécidables sont différents : la machine s'arrête et répond OUI si c'est OUI avec les entrées fournies mais peut parfois tourner en boucle sinon. En conséquence, tant que la machine n'a pas répondu, on ne peut pas distinguer ces deux cas :

• Elle va répondre OUI un jour, il faut juste lui laisser du temps
• Elle va répondre NON un jour, il faut juste lui laisser du temps.
• Elle est partie sur une boucle infinie et ne rendra plus jamais la main...

C'est pourquoi on parle de problème indécidable : lorsqu'on considère que ça devient long, on ne sait pas si ca vaut la peine d'attendre encore un peu, ou pas...

Alan Turing est donc vu comme l'un des pères de l'informatique.