Prouver que la machine M fonctionne Turing en temps O $ (2 ^ {dn}) $

Question

Je suis en train de résoudre cette question afin d'examiner mon examen, et celui-ci m'a obtenu un peu perplexe. Des regards de celui-ci, il semble être une question assez simple en avant, mais je ne peux pas comprendre ce que les étapes pour commencer.

Soit $ M $ une machine de Turing linéaire spatial constitué d'une seule bande. Nous disons $ M $ est une machine de Turing linéaire espace si des arrêts M sur chaque entrée, et s'il y a des constantes $ c $ et $ N_ {0} $ tel que pour toutes les entrées $ x \ in \ Sigma ^ {\ ast} $ de longueur $ n \ geq N_ {0} $, $ M $ en cours d'exécution sur les visites $ x $ au plus $ c \ cdot n $ carrés de bande.

Prouver que pour une constante $ d $, $ M $ fonctionne en temps O $ (2 ^ {dn}) $.

J'ai quelques idées pour commencer. Tout d'abord, mon intuition me dit que je viens de construire un algorithme qui fonctionne selon les règles et accepte / rejets dans le temps $ O (2 ^ {dn}) $. En second lieu, theres un indice qui me dit de « considérer le nombre de configurations », cependant, je ne suis pas sûr sur la façon d'intégrer cela.

Merci d'avance pour toute aide.

Answer 1

Votre intuition est problématique, pour la raison suivante: on vous donne une machine spécifique $ M $, pas une langue. Par conséquent, si vous décrivez un algorithme qui fonctionne dans O $ (2 ^ {dn}) $ et décide la même langue, vous prouvez efficacement que $ L (M) $ est décidable en O $ (2 ^ {dn}) $, mais cela ne signifie pas que $ M $ lui-même fonctionne dans ce laps de temps.

Comme l'indice suggère, considérer le nombre de configurations possibles de $ M $: rappel qu'une configuration d'un TM se compose du contenu de la bande, la position de la tête, et l'État. Étant donné que l'alphabet de la machine est fixée, et que la bande utilisée dans la course de $ M $ sur $ x $ est de taille $ c \ cdot | x | $, essayez de borner le nombre de configurations possibles (exprimées dans la taille de $ M $ et $ | x | $)

Maintenant, rappelons que $ M $ toujours des haltes. Qu'est-ce que cela veut dire au sujet de la séquence de configurations, il passe par sa course sur $ x $?

La combinaison de ces deux observations que vous obtiendrez la réponse. Commentaire si vous avez besoin d'autres conseils.