Automates à compteurs fuyant

Un "automate" en théorie, c'est une machine avec des compteurs/variable(au moins 2) qui contiennent un nombre quelconque, disons les compteurs A et B. On a le droit de faire des truc comme "copier A dans B", "augmenter A", "diminuer A" et "Si A=0 faire ceci sinon cela". Des truc très bien défini qui permettent de simuler tout ce qu'un ordinateur peut faire comme calcul. (En plus on a une instruction "accepter" et une "refuser" mais c'est pour la fin du programme)

Et bien pour mon travail, je défini un autre type d'automate qui ressemble, avec des instructions comme "copier A dans B, mais pas totalement et on peut avoir B plus petit que A après, voir même B=0 si ça nous amuse" et "Si A=0 alors fait ceci, sinon fais 'cela' sauf si tu préfères faire 'ceci' ce que tu peux faire si tu veux"... Et ça m'énerve, je ne trouve aucune information sur ce genre de machine dans les articles que je lis ! Non mais c'est vrai, pourquoi personne il a fait des machines aussi bien définie et naturelle que mes nouveaux automates ?


Edit: il semble qu'il était connue que les automates non-déterministes que j'ai trouvée sont équivalents aux réseaux de pétri.

Commentaires

1. Le mardi 1 juin 2010, 22:39 par Typhon

Je me demandais qui avait programmé HAL 9000, on dirait que j'ai la réponse. Du coup, tu es démasqué en tant que Time Lord, puisque ça implique que tu ai voyagé dix ans en arrière.

Typhon

2. Le lundi 7 juin 2010, 11:45 par Wlad

""Si A=0 alors fait ceci, sinon fais 'cela' sauf si tu préfères faire 'ceci' ce que tu peux faire si tu veux"... "

Pour ça, tu peux utiliser UPPAAL, dont le simulateur a l'épatante propriété de tirer une solution au hasard quand un même automate peut emprunter plusieurs chemins à un moment donné.

3. Le lundi 7 juin 2010, 15:23 par Arthur Rainbow

Wl4d, je ne veux pas "au hasard", je veux tester TOUT les choix possible à la fois.
En plus, je me moque totalement d'avoir une simulation, je ne m'intéresse qu'à la question théorique de savoir si c'est décidable.

Mais en fait, ça l'est, j'ai découvert que j'ai juste donné une définition (étrange certes) des réseaux de Pétri :(.

Ajouter un commentaire

Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.

La discussion continue ailleurs

URL de rétrolien : http://www.milchior.fr/blog/index.php?trackback/304

Fil des commentaires de ce billet