Séminaire du LIM (LIF et LSIS)
Jeudi 7 juin à 14h - Luminy, Salle 9009, dept Math
Maurice Margenstern et Lioudmila Pavlotskaya
LRIM, IUT de Metz
Un couple intéressant, MT+AF ; un résultat d'indécidabilité/décidabilité
On associe un automate fini à une machine de Turing dans les conditions suivantes : La machine de Turing travaille sur un ruban infini d'un seul côté, par exemple vers la droite, et chaque fois qu'elle sort de la configuration courante, l'automate lui fournit un symbole à lire, le symbole dépendant de l'état de la tête de la machine de Turing quand la tête sort de la configuration courante.
On démontre ici deux résultats :
- Il existe une machine de Turing à 5 instructions, U, et un automate fini A tels
que le couple U+A fonctionnant comme indiqué ci-dessus soit capable de simuler
toute machine de Turing.
- Pour toute machine de Turing M ayant au plus 4 instructions et pour tout
automate fini A, le problème de l'arrêt des calculs pour le couple M+A est
décidable (en fait il existe un algorithme de décision indépendant de M et de A
pourvu que M ait au plus 4 instructions).
Email : margens@iut.univ-metz.fr