Différences
Ci-dessous, les différences entre deux révisions de la page.
| Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
|
fr:research:bsp [2018/03/29 16:27] apeiron |
— (Version actuelle) | ||
|---|---|---|---|
| Ligne 1: | Ligne 1: | ||
| - | Ce travail a démarré fin 2016, et a été réalisé en collaboration avec Frédéric Gava, maître de conférences à l'Université Paris-Est Créteil. Bien qu'il n'ait pas été financé par contrat, j'ai été affilié au Laboratoire d’Algorithmique, Complexité et Logique pendant que j'exerçais mon activité de chercheur bénévole. | ||
| - | |||
| - | ====== Versions ====== | ||
| - | |||
| - | {{ :fr:research:bsp-asm.pdf |rapport technique}} disponible sur [[https://hal.archives-ouvertes.fr/hal-01717647|HAL]] | ||
| - | |||
| - | {{ :fr:research:bsp-while.pdf |rapport technique}} | ||
| - | |||
| - | ====== Résumé ====== | ||
| - | |||
| - | La thèse de Gurevich énonce que l'ensemble des algorithmes séquentiels sont capturés par ses trois postulats. De plus, il a prouvé que ces trois postulats définissent le même ensemble que ses Abstract State Machines. Ainsi, nous avons que ASM = Algo. Cela montre que l'approche axiomatique des postulats est équivalente à l'approche opérationnelle des ASMs. | ||
| - | |||
| - | Dans [[fr:research:fi-while|cet article]], j'ai montré que les langages impératifs usuels sont non seulement Turing-complets mais aussi algorithmiquement complets. Cela a été fait en prouvant qu'un langage impératif minimal While est **algorithmiquement équivalent** aux ASMs de Gurevich. Ainsi, nous avons While ≃ ASM, ce qui signifie plus précisément que les exécutions des deux modèles de calcul sont les mêmes, à variables fraîches et dilatation temporelle près. Donc nous avons While ≃ Algo, ce qui montre que tout langage de programmation contenant les commandes de While est algorithmiquement complet (pour les algorithmes séquentiels). | ||