Mi sono imbattuto in un problema di seguito in questo pdf :
Dato un TM M, se M scrive mai un simbolo non vuoto quando viene avviato sul nastro vuoto.
La soluzione fornita è la seguente:
Lascia che la macchina scriva solo in bianco simbolo. Allora il suo numero di configurazioni nel computo su w è q × 2, dove q è il numero di stati di M; il fattore 2 è per le scelte re. la direzione del movimento delle teste; non vi è alcun fattore per il simbolo scritto perché è sempre vuoto. Quindi il problema è decidibile, deciso dalla seguente macchina: input (M, w), esegui M su w per q × 2 passi; se M scrive mai un simbolo non vuoto, interrompi con la risposta sì; se M non scrive mai un simbolo non vuoto, interrompi senza risposta
Dubbi:
D1. Come essere sicuri che tutte le configurazioni di qx 2 vengano eseguite durante lesecuzione di qx 2 passaggi su w? Alcune configurazioni potrebbero essere ripetute in qx 2 passaggi.
D2. La domanda dice “quando viene avviata sul nastro vuoto “, ma la risposta ha cercato di simulare TM su una stringa non vuota w. Come ha senso?
Risposta
D1: Uno stato può essere ripetuto. Il punto è che se uno stato viene ripetuto e non è stato nemmeno scritto alcun simbolo non vuoto, allora sapevi che la macchina di Turing non si fermerà mai poiché è necessariamente bloccata nel ciclare attraverso alcuni degli stati incontrati finora. Poiché nessuno degli stati del ciclo ha fatto sì che la TM scriva un simbolo non vuoto, la TM non scriverà mai un simbolo non vuoto.
Dopo $ 2q $ , è stato scritto un simbolo non vuoto e puoi rispondere “sì”, oppure tutti i simboli scritti erano vuoti e (almeno) uno stato deve essere stato rilevato due o più volte, il che significa che puoi rispondere “no”.
D2: La mia ipotesi è che $ w $ è definito da qualche parte come stringa vuota. Se la TM può essere avviata con una stringa arbitraria $ w $ , allora una variazione della soluzione precedente funziona ancora. Supponiamo che linizio della TM inizi allinizio di $ w $ . Il numero di stati aumenta di un fattore al massimo $ 1+ | w | $ per tenere conto di tutti i possibili stati del nastro (se vengono scritti solo simboli vuoti , quindi il nastro contiene sempre uno dei $ 1+ | w | $ suffissi di $ w $ ). Se la testa può iniziare ovunque, questo fattore sarà al massimo $ 1+ | w | ^ 2 $ .
Commenti
- In Q1. Vuoi dire " o è stato scritto un simbolo non vuoto e puoi rispondere sì … e puoi rispondere no "? Perché la domanda chiede " se M scrive mai un simbolo non vuoto ". In Q2. Impossibile ottenere " nel numero di stati corrispondenti al numero di sottoinsiemi di posizioni di w che sono stati sovrascritti da un simbolo vuoto "
- Hai ragione. Ho corretto la mia risposta. Ho anche chiarito lultima parte.