Je suis tombé sur le problème ci-dessous dans ce pdf :
Étant donné un TM M, si M écrit un symbole non vierge lorsquil est lancé sur la bande vide.
La solution donnée est la suivante:
Que la machine nécrit que du blanc symbole. Alors son nombre de configurations dans le calcul com sur w est q × 2, où q est le nombre détats de M; le facteur 2 est pour les choix re. la direction du mouvement des têtes; il ny a aucun facteur pour le symbole écrit car il est toujours vide. Le problème est donc décidable, décidé par la machine suivante: entrée (M, w), exécuter M sur w pour q × 2 étapes; si jamais il M écrit un symbole non vide, arrêtez avec une réponse oui; si M nécrit jamais un symbole non vide, arrêtez sans réponse
Doutes:
Q1. Comment être sûr que toutes les configurations de qx 2 se produiront lors de lexécution de qx 2 étapes sur w? Certaines configurations peuvent être répétées en qx 2 étapes.
Q2. La question dit « au démarrage sur le bande vide « , mais la réponse a essayé de simuler TM sur une chaîne non vide w. En quoi cela a-t-il un sens?
Réponse
Q1: Un état peut se répéter. Le fait est que si un état se répète et quaucun symbole non vide na même été écrit, alors vous savez que la machine de Turing ne sarrêtera jamais car elle est nécessairement bloquée en parcourant certains des états rencontrés jusquà présent. Étant donné quaucun des états du cycle na amené la TM à écrire un symbole non vide, la TM nécrira jamais de symbole non vide.
Après $ 2q $ étapes, soit un symbole non vide a été écrit et vous pouvez répondre « oui », soit tous les symboles écrits étaient vides et (au moins) un état doit avoir été rencontré deux fois ou plus, ce qui signifie que vous pouvez répondre « non ».
Q2: Je suppose que $ w $ est défini quelque part pour être la chaîne vide. Si la TM peut être démarrée avec une chaîne arbitraire $ w $ , alors une variante de la solution ci-dessus fonctionne toujours. Supposons que la tête de la TM commence au début de $ w $ . Le nombre détats augmente dun facteur dau plus $ 1+ | w | $ afin de prendre en compte tous les états possibles de la bande (si seuls des symboles vides sont écrits , alors la bande contient toujours lun des suffixes $ 1+ | w | $ de $ w $ ). Si la tête peut commencer nimporte où, alors ce facteur sera au plus $ 1+ | w | ^ 2 $ .
Commentaires
- Au premier trimestre. Voulez-vous dire " soit un symbole non vide a été écrit, et vous pouvez répondre oui … et vous pouvez répondre non "? Parce que la question demande " si M écrit un symbole non vide ". Au T2. Na pas obtenu " dans le nombre détats correspondant au nombre de sous-ensembles de positions de w qui ont été écrasés par un symbole vide "
- Vous avez raison. Jai fixé ma réponse. Jai également clarifié la dernière partie.