Turing Machine qui peut se souvenir

Question

La machine de Turning spéciale est définie comme une machine à diurnure standard, uniquement que chaque étape est faite en fonction du contenu de la bande à partir du bord gauche à la position de la tête dans la bande. (La fonction de transition dans ce cas appartient à q x γ * -> q x x x {l, r})

Lequel des énoncés suivants est vrai:

a. Chaque langue l a une machine de Turing qui décide que si et seulement s'il y a une machine de Turning spéciale qui décide L.

b. Chaque langue L a une machine de Turing qui décide L dans un temps polynomial si et uniquement s'il y a une machine de Turning spéciale qui décide L dans un polynôme (polynôme de longueur d'entrée).

c. A, b réponds sont corrects.

d. A, b réponds sont incorrects.

Et ma question est: La bonne réponse est d et je ne peux pas comprendre pourquoi.

La réponse est: Chaque langue peut être décidée par une machine de Turning spéciale en temps de longueur d'entrée linéaire (O (n) lorsque N est la longueur d'entrée). Une fonction de transition passe à droite tant qu'aucun espace vide n'est vu et dès que vous voyez un espace vide commutateur à recevoir ou à rejeter en fonction du mot écrit sur la bande.

Ma question est la suivante: Comment puis-je décider de rejeter ou d'accepter un mot? Dans d'autres modèles de calcul, tels que PDA, DFA, nous avons défini la fonction de transition de la même manière, et aucun pouvoir n'a été ajouté au modèle. Pourquoi semble-t-il que la puissance soit ajoutée au modèle de calcul à la suite de la modification de la fonction de transition en matière de construction de machines?

merci.

Answer 1

donné toute langue $ l $ Il y a une machine de Turing spéciale $ t $ qui décide $ L $ en temps polynomial.

La machine Turing contient 3 états: les états initiaux $ q_0 $ , l'état d'acceptation $ q_a $ Et l'état de rejet $ q_r $ . Laissez $ \ gamma $ être l'alphabet de bande (y compris le symbole vierge $ \ varpsilon $ ), et laisser $ \ alpha x $ désigne le contenu de la bande à partir du bord gauche à la position de la tête dans la bande, où $ \ alpha \ in \ gamma ^ * $ et $ x \ in \ gamma $ . Comme d'habitude, je vais supposer que l'entrée est écrite à partir du début de la bande et que la tête est initialement positionnée au début de la bande. La fonction de transition $ \ delta $ est définie comme suit:

• $ \ delta (q_0, \ alpha x)= (q_0, x, r) $ si $ x \ Neq \ varpsilon $
• $ \ delta (q_0, \ alpha x)= (q_a, x, r) $ si $ x=varepsilon $ et $ \ alpha \ in l $
• $ \ delta (q_0, \ alpha x)= (q_a, x, r) $ si $ x=varpsilon $ et $ \ alpha \ pas \ in l $

Comme il existe des langues indéchées pour les machines de Turning régulières, cela implique immédiatement que A et B sont faux.

Les réponses D et C ne sont pas claires. Ils parlent de "deux réponses" mais on vous donne 4 $ réponses possibles.