Bonjour,
une question sur les machines de Turing :
Quelle est le nombre d'états minimum N(n) d'un automate
de Turing sur un alphabet {#, 0, 1} qui :
- retourne 1 lorsque qu'il lit #000...00# (n fois zéro)
- retourne 0 sinon
Le mot initial sur la bande est toujours 000...#000...000#000... (k fois zéro entre deux symboles #) et la tête de lecture pointe au début sur le premier symbole #
Merci de réponses
David
-----