Bonjour,

J'ai une machine de Turing qui reçoit une entrée de n caractères.

Au bout de son exécution, elle aura prit les premières cases de son ruban.

Je dois prouver que le nombre de transitions de cette machine est polynomiale.

Je n'ai vraiment aucune idée comment m'y prendre, est-ce que quelqu'un pourrait m'aider?

Merci !