Pierre Valarcher (LACL, Paris 12)

Yuri Gurevich montre que les Abstract State Machine simulent pas à pas tous les algorithmes et donc simulent pas à pas tous les modèles de machines séquentiels (Turing, RAM, …). Ce résultat peut être approfondi, pour les machines, en remarquant que :

  1. la simulation n’est pas l’identification
  2. les modèles de machines simulés par les ASM ne constituent pas, chacuns, une classe naturelle d’ASM.

Nous modifions les ASM en Multi-Algèbres Evolutives (EMA) en remplaçant le programme par une fonctionnelle définissable à partir de la partie statique de l’EMA. On montre alors que des classes naturelles d’EMA correspondent, via une “identification” et à certaines modifications près, aux modèles de calcul habituels. Les EMA apparaissent alors comme le modèle mathématique qui unifie tous les modèles de calculs séquentiels.

En collaboration avec S. Grigorieff (LIAFA).