Modélisation d’un ordinateur

Un ordinateur c’est :

- un processeur + des registres,

- une mémoire pour le programme,

- une mémoire pour les données. Cycle : exécuter une instruction du programme sur l’ensemble registres + mémoire. Etat : registres + mémoire. Cycle : fonction de transition sur les états. Le couple fonction de transition + état initial détermine l’exécution du programme.

Modélisation d’un programme

Modélisation d’un programme sur un ordinateur :

- un ensemble fini d’états,

- une fonction de transition,

- un état initial. Modélisation de l’exécution d’un programme : séquence d’états obtenus par applications successives de la fonction de transition a l’état initial. Séquence infinie : préfixe + (séquence fini)^{∗}.

Modélisation d’un programme (suite)

Problème : nombre fini d’instances du problème (états initiaux) vs nombre infini d’instances d’un problème (mots d’un langage). Solutions:

- nombre d’états infini ou,

- introduire les instances du problème caractère par caractère via un ruban et une tête de lecture (choix provisoire). Cycle :

1. lecture d’un caractère,

2. application de la fonction de transition,

3. déplacement de la tête de lecture.