Est-il possible de décider si une MT atteint une certaine position sur la bande?

J'ai ces questions d'un ancien examen que j'essaie de résoudre. Pour chaque problème, l'entrée est un codage d' une certaine machine de Turing $M$ .

Pour un entier $c>1$ , et les trois problèmes suivants:

Est-il vrai que pour chaque entrée , M ne passe pas le position lors de l'exécution sur ? $x$ $|x|+c$ $x$

$x$ $\max \{|x|-c,1 \}$ $x$

Est-il vrai que pour chaque entrée , M ne passe pas la position lors de l'exécution sur ? $x$ $(|x|+1)/c$ $x$

Combien de problèmes sont décidables?

Le problème numéro (1), à mon avis, est dans si je comprends bien car, je peux exécuter toutes les entrées en parallèle et arrêter si certaines entrées ont atteint cette position et pour montrer que ce n'est pas in je peux y réduire le complément de Atm . Je construis une machine de Turing comme suit: pour une entrée je vérifie si est un historique de calcul, si c'est le cas, alors fonctionne bien et ne s'arrête pas, si ce n'est pas le cas, alors il s'arrête. $\text {coRE} \smallsetminus \text R$ $\text R$ $M'$ $y$ $y$ $M'$

Pour (3), je crois que c'est décidable car pour ce sont toutes les machines de Turing qui restent toujours sur la première cellule de la bande, car pour une chaîne d'un caractère il peut passer la première cellule, donc je besoin de simuler toutes les chaînes de longueur 1 pour les étapes (est-ce correct?), et voir si j'utilise uniquement la première cellule de chacune d'elles. $c \geqslant 2$ $|Q|+1$

Je ne sais pas vraiment quoi faire avec (2).

computability turing-machines undecidability Jozef
la source

1) Supposez-vous une bande infinie unilatérale? 2) Qu'est-ce que Atm?

Raphael

1) Oui, 2) Le problème d'acceptation.

Jozef

Relativement reliées Toutes les fonctions ont-elles une complexité d'espace constante dans REG?

adrianN

Réponses:

Toute situation qui demande si une machine de Turing est confinée à une section finie de la bande (disons de longueur ) sur une entrée donnée est décidable. $n$

L'argument fonctionne comme suit. Tenez compte de la machine de Turing, du ruban et de la position de la machine de Turing sur le ruban. Tous ensemble, ceux-ci ont un nombre fini de configurations. Pour être précis, il n'y a que configurations possibles. est l'ensemble des symboles de bande et est l'ensemble des états. Je vais continuer à utiliser le mot "configuration" pour décrire l'état de la machine de Turing combiné à l'état de la bande et sa position sur la bande pour le reste de cette réponse, mais ce n'est pas du vocabulaire standard. $t = n|\Gamma|^n|Q|$ $\Gamma$ $Q$

Exécutez la machine en gardant une trace de toutes ses configurations passées. Si jamais il dépasse le point , retournez "oui, passe la position ". Sinon, la machine se situe entre 0 et . Si la machine répète une configuration - son état, les symboles sur la bande et sa position sur la bande sont identiques à ce qu'ils étaient auparavant - retournez "non, ne passe jamais la position ". $n$ $M$ $n$ $n$ $M$ $n$

Selon le principe du trou de culasse, cela ne doit pas se produire en plus de étapes. Donc, tout ce qui précède est décidable; après au plus étapes simulées, vous obtenez une réponse. $t+1$ $t+1$

Un petit mot sur pourquoi cela fonctionne: lorsque la machine, la bande et sa position sur la bande se répètent, il doit y avoir eu une séquence de configurations entre ces répétitions. Cette séquence se reproduira, conduisant à la même configuration une fois de plus - la machine est dans une boucle infinie. C'est parce que nous gardons une trace de tous les aspects de la machine de Turing; rien en dehors de la configuration ne peut avoir d'impact sur ce qui s'est passé. Ainsi, lorsqu'une configuration se répète, elle se répétera à nouveau, avec une série de configurations identiques entre les deux.

Il est donc décidable de limiter la bande à une partie finie de la chaîne. Par conséquent, en itérant sur toutes les chaînes d'entrée possibles, le problème est en pour les trois questions. Vous l'avez peut-être déjà réalisé (entre vos idées pour 1 et 3 et la réponse de Ran G pour 2, cela semble résolu de toute façon), mais j'ai pensé que cela valait quand même la peine d'être publié. $\text{coRE}$

SamM
la source

"Si la machine répète une configuration, [...] retournez" non "" - c'est faux. Une machine non déterministe peut exécuter une boucle plusieurs fois, puis passer à autre chose.

Raphael

Nous parlons ici de machines de turing qui ne sont pas supposées non déterministes. S'il n'était pas déterministe, simulez la version déterministe.

SamM

Belle explication. Voir aussi la première version de ma réponse (que je révise une fois que j'ai réalisé que le PO ne le demandait pas tout à fait ..)

Ran G.

@Sam: Cela fonctionne dans l'autre sens: sauf indication contraire, une machine de Turing peut être non déterministe. Qu'est-ce qu'une "version déterministe"? Si vous entendez un déroulement complet des choix, une configuration répétée perd tout son sens car elle peut se produire dans différentes branches.

Raphael

@Raphael la manière standard de le faire est un graphe de configuration: les sommets sont les mêmes configurations que Sam a définies, et il y a un bord dirigé de la configuration A vers B si le NTM peut passer de A à B en une seule étape. Le graphique est fini et si la machine s'arrête est une simple question d'accessibilité du graphique. Cela montre également que

est un sous-ensemble de

N S P A C E (s)

$\mathsf{NSPACE}(s)$

D T I M E (2^{O (s)})

$\mathsf{DTIME}(2^{O(s)})$

Sasho Nikolov

(2) est très similaire à (3) et le même raisonnement que vous aviez pour (3) s'applique également ici: notez que les machines qui dans ont une propriété étrange - elles ne lisent pas la totalité de l'entrée (elles n'atteignent jamais derniers bits.) Et cela est vrai pour chaque entrée. $L_2$ $c$

Ok, considérons maintenant uniquement les entrées jusqu'à la longueur . Pour chacun d'eux, il n'y a que deux options: la machine boucle / s'arrête sans déplacer la tête, ou elle déplace la tête. Si elle déplace la tête sur un certain (avec ), cette machine n'est pas dans raison de cette entrée . Sinon, je prétends que la machine est en . Comme il ne bouge jamais la tête - il n'a aucune idée de la taille de l'entrée! cela signifie qu'il se comporte de la même manière pour toutes les entrées de longueur . Par conséquent, est décidable. $c$ $x$ $|x|\le c$ $L_2$ $x$ $L_2$ $|x|>c$ $L_2$

A sonné.
la source

Comment expliquez-vous les machines non déterministes?

Raphael

Je n'ai pas considéré les MNT, mais ce devrait être tout à fait la même chose. Pour tous les mots de longueur jusqu'à

le nombre de configurations que le NTM peut être sans déplacer la tête est fini.

c

$c$

Ran G.

Oui, mais votre argument échoue. Vous ne pouvez pas déterminer en temps fini (par simple simulation) si un NTM quitte une position donnée.

Raphael

@Raphael pourquoi pas? ne pouvez-vous pas simuler l'arborescence entière des configurations (de profondeur

) dans un temps fini

| x |

$|x|$

e x p (| x |)

$exp(|x|)$

Ran G.

Pourquoi la profondeur

être assez?

aurait plus de sens. D'ici là, la simulation a trouvé une branche où

quitte la première position, s'il y en a.

| x |

$|x|$

| Q |

$|Q|$

M

$M$

Raphael