Worldlex Wiki En informatique théorique , une machine à pointeurs est une machine de calcul abstraite atomistique dont la structure de stockage est un graphe . Un algorithme de pointeur peut également être un algorithme restreint au modèle de machine à pointeurs.
Certains types particuliers de machines à pointeurs sont appelés automate de liaison, machine KU, SMM, machine LISP atomistique , machine à pointeur d'arbre, etc.
Les machines à pointeurs ne possèdent pas d'instructions arithmétiques. Le calcul s'effectue uniquement par la lecture de symboles d'entrée, leur modification et divers tests sur leur structure de stockage (l'agencement des nœuds et des pointeurs), puis par la production de symboles de sortie en fonction des résultats de ces tests. En ce sens, ce modèle est similaire à la machine de Turing .
Types de « machines à pointeur »
Gurevich et Ben-Amram recensent tous deux plusieurs modèles « atomistiques » très similaires de « machines abstraites » ; Ben-Amram estime qu’il convient de distinguer les « modèles atomistiques » des modèles « de haut niveau ». Les modèles atomistiques suivants seront présentés ci-dessous :
- Machines de modification de stockage de Schönhage (SMM),
- Machines Kolmogorov – Uspenskii (KUM ou KU-Machines).
Ben-Amram présente également les variétés suivantes, qui ne sont pas abordées plus en détail dans cet article :
- Machine atomistique pure LISP (APLM)
- Machine atomistique entièrement LISP (AFLM),
- Machines à pointeur atomistiques générales,
- Le langage I de Jones (deux types).
Modèle de machine de modification de stockage (SMM) de Schönhage
La présentation suivante fait suite à celle de van Emde Boas.
La machine se compose d'un alphabet fixe de symboles d'entrée, d'un programme fixe et d'un graphe orienté mutable dont les flèches sont étiquetées par des symboles de l'alphabet. Ce graphe constitue la mémoire de la machine . Chaque nœud du graphe possède une unique flèche sortante, étiquetée par chaque symbole, même si certaines de ces flèches peuvent boucler vers le nœud d'origine. Un nœud fixe du graphe est identifié comme le nœud de départ ou « actif ».
Chaque mot de symboles de l'alphabet peut alors être traduit en un chemin à travers la machine ; par exemple, 10011 se traduirait par le fait de prendre l'arête 1 à partir du nœud de départ, puis l'arête 0 à partir du nœud résultant, puis l'arête 0, puis l'arête 1, puis l'arête 1. Ainsi, un mot identifie un nœud, le nœud final du chemin, mais cette identification changera à mesure que le graphe change au cours du calcul.
La machine peut recevoir des instructions qui modifient la disposition du graphique. Les instructions de base sont :
(1) nouvelle instruction w , qui crée un nouveau nœud à la fin du chemin w , avec toutes ses arêtes dirigées vers l'avant-dernier nœud dans w .
(2) L'instruction « set w to v » (re)directe une arête vers un nœud différent. Ici, w et v représentent des mots . Cette instruction modifie la destination de la dernière arête du chemin w .
(3) Si v = w alors instruction z : Instruction conditionnelle comparant deux chemins représentés par les mots w et v pour déterminer s'ils aboutissent au même nœud ; si c'est le cas, passer à l'instruction z, sinon continuer. Cette instruction remplit la même fonction que la commande « si » dans tout langage de programmation impératif .
(4) lire et écrire des instructions d'entrée/sortie, en accédant à une bande d'entrée en lecture seule et à une bande de sortie en écriture seule, contenant toutes deux des symboles de l'alphabet.
Knuth a noté que le modèle SMM coïncide avec un type d'« automate de liaison » brièvement expliqué dans le premier volume de The Art of Computer Programming .
Modèle de machine Kolmogorov – Uspenskii (machine KU)