Turing decidibile
Salve, ho questo esercizio:
Mostrare che [tex]L\in \{0,1\}^*[/tex] è decidibile sse [tex]L \leq_m 0^*1^*0[/tex]
E' corretto risolverlo così? Grazie
-Se [tex]L \leq_m 0^*1^*0[/tex] allora L è turing-riconoscibile.
Assumiamo che [tex]L \leq_m 0^*1^*0[/tex]. Costriusco [tex]M_L[/tex] una TM che decide L. Su input w, [tex]M_L[/tex] usa la riduzione per [tex]L \leq_m 0^*1^*0[/tex] per computare una nuova stringa x t.c. [tex]x\in 0^*1^*0[/tex] sse [tex]w\in L. M_L[/tex] allora usa il suo controllo finito per implementare un DFA che determina se [tex]x\in 0^*1^*0[/tex] o no. Se [tex]x\in 0^*1^*0[/tex] allora [tex]M_L[/tex] accetta, altrimenti [tex]M_L[/tex] rifiuta. Notiamo che il passo di riduzione non può andare in loop (per definizione di Turing-riducibile) a il passo del DFA non può andare in loop (perchè il DFA legge un simbolo di x ad ogni step e decide quando termina la lettura di x). Quindi, [tex]M_L[/tex] non va mai in loop. Di conseguenza, [tex]M_L[/tex] è un decisore per L il che significa che L è turing decidibile.
-Se L è turing-decidibile, allora [tex]L \leq_m 0^*1^*0[/tex].
Assumiamo che L sia turing-decidibile. Quandi, c'è una TM che decide L. Sia [tex]M_L[/tex] tale TM. per ridurre L a [tex]0^*1^*0[/tex], costruiamo una turing machine, M, che esegue le seguenti operazioni su input w:
Esegui [tex]M_L[/tex] su input w
Se [tex]M_L[/tex] accetta w, cancella il nastro e scrivi la stringa 0.
Se [tex]M_L[/tex] rifiuta w, cancella.
[tex]M_L[/tex] non può andare in loop: è un decisore.
Quindi, se [tex]w \in L[/tex], allora M scrive 0 sul suo nastro, e [tex]0 \in 0^*1^*0[/tex]. Altrimenti, M scrive [tex]\epsilon[/tex] sul suo nastro, e [tex]\epsilon[/tex] non appartiene a [tex]0^*1^*0[/tex]. Quindi, M riduce L a [tex]0^*1^*0[/tex].
Mostrare che [tex]L\in \{0,1\}^*[/tex] è decidibile sse [tex]L \leq_m 0^*1^*0[/tex]
E' corretto risolverlo così? Grazie
-Se [tex]L \leq_m 0^*1^*0[/tex] allora L è turing-riconoscibile.
Assumiamo che [tex]L \leq_m 0^*1^*0[/tex]. Costriusco [tex]M_L[/tex] una TM che decide L. Su input w, [tex]M_L[/tex] usa la riduzione per [tex]L \leq_m 0^*1^*0[/tex] per computare una nuova stringa x t.c. [tex]x\in 0^*1^*0[/tex] sse [tex]w\in L. M_L[/tex] allora usa il suo controllo finito per implementare un DFA che determina se [tex]x\in 0^*1^*0[/tex] o no. Se [tex]x\in 0^*1^*0[/tex] allora [tex]M_L[/tex] accetta, altrimenti [tex]M_L[/tex] rifiuta. Notiamo che il passo di riduzione non può andare in loop (per definizione di Turing-riducibile) a il passo del DFA non può andare in loop (perchè il DFA legge un simbolo di x ad ogni step e decide quando termina la lettura di x). Quindi, [tex]M_L[/tex] non va mai in loop. Di conseguenza, [tex]M_L[/tex] è un decisore per L il che significa che L è turing decidibile.
-Se L è turing-decidibile, allora [tex]L \leq_m 0^*1^*0[/tex].
Assumiamo che L sia turing-decidibile. Quandi, c'è una TM che decide L. Sia [tex]M_L[/tex] tale TM. per ridurre L a [tex]0^*1^*0[/tex], costruiamo una turing machine, M, che esegue le seguenti operazioni su input w:
Esegui [tex]M_L[/tex] su input w
Se [tex]M_L[/tex] accetta w, cancella il nastro e scrivi la stringa 0.
Se [tex]M_L[/tex] rifiuta w, cancella.
[tex]M_L[/tex] non può andare in loop: è un decisore.
Quindi, se [tex]w \in L[/tex], allora M scrive 0 sul suo nastro, e [tex]0 \in 0^*1^*0[/tex]. Altrimenti, M scrive [tex]\epsilon[/tex] sul suo nastro, e [tex]\epsilon[/tex] non appartiene a [tex]0^*1^*0[/tex]. Quindi, M riduce L a [tex]0^*1^*0[/tex].
Risposte
"St3llinaVanillina":
Mostrare che [tex]L\in \{0,1\}^*[/tex] è decidibile sse [tex]L \leq_m 0^*1^*0[/tex]
Scusa, questa notazione "[tex]L \leq_m \text{qualcosa}[/tex]" indica la riducibilità polinomiale?
"Rggb":
[quote="St3llinaVanillina"]Mostrare che [tex]L\in \{0,1\}^*[/tex] è decidibile sse [tex]L \leq_m 0^*1^*0[/tex]
Scusa, questa notazione "[tex]L \leq_m \text{qualcosa}[/tex]" indica la riducibilità polinomiale?[/quote]
esatto...
Quindi direi che la tua dimostrazione va bene, a parte qualche refuso qua e là.
Grazie mille! =) cos'ho sbagliato?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo