Étant donné une MT

Je veux déterminer si ce problème de décision est décidable. J'ai essayé d'établir des réductions à partir de Halt et "Accepte une chaîne vide", mais je n'ai pas encore trouvé de solution.

Est-ce que quelqu'un peut m'aider?

computability turing-machines undecidability Shuzheng
la source

Cela signifie que la machine doit rester au même endroit, sans bouger. Il n'y a pas beaucoup de possibilités pour un tel calcul?

Hendrik Jan

Ça pourrait bouger, en fait. Mais alors supposez que

δ (q_{0},_) = (q, a, D)

$\delta(q_0,\_) = (q,a,D)$ pour un état

q

$q$ , étiquette

a

$a$ et

D \in {L, R}

$D\in\{L,R\}$ . Que pouvez-vous dire sur l'affaire

q \neq q_{0}

$q\neq q_0$ ? Que se passe-t-il ensuite si

q = q_{0}

$q = q_0$ ?

Klaus Draeger

Ce problème peut être décidable. J'ai trouvé ce papier hal.inria.fr/inria-00074105 (je n'ai pas lu donc je ne suis pas sûr) qui pourrait vous intéresser. Il prétend que le problème d'arrêt pour une machine de Turing à un état est décidable. (qui est un problème assez proche de votre problème).

wece

Veuillez modifier le titre de la question "... lorsque la bande de démarrage est vide" si votre prime concerne "toute entrée de bande": le cas dans lequel la bande est bloquée est trivialement décidable (j'ai posté une réponse mais je l'ai soudainement supprimée lorsque J'ai vu le commentaire sur la prime)

Vor

Réponses:

Je dirais que c'est décidable.

Si j'ai bien compris, voici ce que je pense.

Tout d'abord, une MT part d'un état initial $s_0$ . Comment peut-il changer l'état? Dans votre fonction de transition, vous avez quelque chose comme $(s_0, x) \to (s_i, y, m)$ où $s_i$ est un état et $x$ , $y$ sont des symboles et $m$ est le mouvement de la tête (gauche droite ou rester). Donc, s'il quitte l'état initial, il devrait y avoir une transition de $(s_0, \_)$ à un état non $s_0$ . Il est facile de voir que c'est si et seulement si. Ainsi, vous pouvez construire une autre machine Turing qui a l'entrée comme TM dans certains encodages, passe par la fonction de transition et vérifie la condition ci-dessus, et le problème est décidable.

Eugène
la source

Je ne comprends pas cette réponse / cet algorithme. Considérez une MT qui a une règle de transition qui peut quitter l'état

s_{0}

$s_0$ si le symbole sous la tête est X. Maintenant, nous devons savoir si X peut jamais être présent dans n'importe quelle cellule de la bande. Supposons que la MT ait également des règles de transition sur l'état

s_{0}

$s_0$ qui se déplacent vers la gauche et / ou la droite et écrivent des symboles sur la bande, y compris potentiellement X. Maintenant, qu'allez-vous faire? Comment allez-vous savoir si la MT peut potentiellement écrire X sur une cellule puis revisiter cette cellule? Je ne vois aucun algorithme ici qui gère cette situation.

@DW Parlons-nous ici d'une MT détéministe ou non déterministe?

Eugene

C'est une question que vous devriez poser à l'affiche originale si vous pensez qu'elle n'est pas claire, mais avec les informations fournies, je pense que nous devrions supposer une MT déterministe. Cela dit, je soupçonne que j'ai été influencé par le texte de prime, qui faisait référence à "ne quitte jamais l'état initial, peu importe l'état initial de la bande" ~, ce qui est un peu différent de "ne quitte jamais l'état d'entrée lorsque l'initiale l'état de la bande est entièrement vierge ", donc peut-être que mon objection est sans rapport avec la question posée.

Quoi qu'il en soit, il serait peut-être utile de justifier plus soigneusement la partie "facile à voir ...". Par exemple, vous ne semblez pas utiliser explicitement le fait que la bande initiale est entièrement vierge, même s'il semble que cela fasse une grande différence.

Tridement décidable. Étant donné que la bande est vraiment vierge, alors T dans l'état $s_0$ doit changer la cellule de bande actuellement analysée et effectuer l'une des trois opérations suivantes: (1) passer à un état différent et se déplacer vers la gauche ou la droite (ou l'arrêt); (2) Transition vers $s_0$ et déplacer une cellule vers la gauche; (3) Transition vers $s_0$ et déplacez une cellule vers la droite. Pour (2) et (3), la tête TM s'est éloignée de la cellule de bande d'origine et est en train de balayer une cellule vierge; par conséquent, il se trouve maintenant dans la même situation qu'il a commencé et agira de la même manière. Ainsi, pour (2) ou (3), le comportement de la MT sur une bande vierge consiste à se déplacer indéfiniment dans une direction, laissant une traînée de cellules (probablement) modifiées. Cette propriété peut donc être vérifiée en inspectant le contenu d'une seule ligne du «programme» de la MT (c'est-à-dire la règle de transition pour $s_0$ numérisation vierge) - si le nouvel état n'est PAS $s_0$ (y compris les «arrêts»), la réponse est OUI, sinon la réponse est NON.

Je suis également raisonnablement certain que le problème est toujours décidable étant donné les entrées arbitraires - il suffit de faire plus attention à la direction dans laquelle la tête de bande se déplace en fonction du contenu actuel des cellules.

PMar
la source