Modèles de calcul non initialisés

Dans cet exposé, on considère les modèles de calcul usuels (machines de Turing, machines à compteurs) comme des systèmes dynamiques, correspondant à l’application de leur fonction de transition sur une configuration quelconque. En particulier, dans ce contexte, il est nécessaire d’observer leur comportement partant de n’importe quelle configuration, plutôt que d’une configuration initiale donnée.

Le problème devient alors totalement différent. Par exemple, la preuve de l’indécidabilité de l’existence d’une configuration sur laquelle une machine de Turing ne s’arrête pas (Hooper, 1966) est bien plus délicate que l’indécidabilité de l’arrêt d’une machine de Turing partant d’une configuration donnée (Turing, 1937), et ce phénomène se répète pour la majorité des modèles de calcul.

Après une présentation générale de la problématique, nous essaierons dans cet exposé d’illustrer les méthodes permettant de résoudre ou contourner le problème dans le cadre du modèle de calcul des pavages par tuiles de Wang, qui convient fort bien à un traitement dynamique.