[8 aprile 2024] Calcolabilità

[Antaarees]

[Exyss]

Sia $f : \Sigma^* \to \Sigma^*$ la funzione calcolata dalla seguente TM $F$ definita come:

$F$ = "Data la stringa $\langle M,w \rangle$ in input:

1. Costruisci una TM $M_2$ definita come:
   $M_2$ = "Data la stringa $x$ in input:
   a) Controlla se $x$ sia della forma $(01)^{*}$. Se falso, rifiuta.
   b) Esegui il programma di $M$ su input $w$. Se l'esecuzione accetta allora anche $M_2$ accetta, altrimenti essa rifiuta."
2. Restituisci la stringa $\langle M' \rangle$"

Supponiamo che $\langle M, w \rangle \notin A_{TM}$. Ciò implica che $w \notin L(M)$, dunque per costruzione stessa di $M_2$ abbiamo che quest'ultima rifiuterà sempre qualsiasi stringa $x$, dunque $L(M_2) = \varnothing$ e quindi che $\langle M_2 \rangle \notin B$. Concludiamo quindi che $\langle M, w \rangle \notin A_{TM} \implies f(\langle M, w \rangle) = \langle M_2 \rangle \notin B$.

Viceversa, supponiamo che $\langle M, w \rangle \in A_{TM}$, dunque $w \in L(M)$. A questo punto abbiamo due casi:

• Se $x \notin L((01)^{*})$ allora $M_2$ rifiuta, dunque $x \notin L(M_2)$.
• Se $x \in L((01)^{*})$ allora $M_2$ accetta, dunque $x \in L(M_2)$.
  Dunque, sotto l'ipotesi che $\langle M, w \rangle \in A_{TM}$ abbiamo che $x \in L((01)^{*}) \iff x \in L(M_2)$, il che è equivalente a dire che $L(M_2) = L((01)^{*}$, da cui segue che $\langle M_2 \rangle \in B$. Concludiamo quindi che $\langle M, w \rangle \in A_{TM} \implies f(\langle M, w \rangle) = \langle M_2 \rangle \in B$.

In altre parole, otteniamo che $\langle M, w \rangle \in A_{TM} \iff f(\langle M, w \rangle) = \langle M_2 \rangle \in B$, dunque $f$ è una riduzione $A_{TM} \leq_m B$. Infine, poiché $A_{TM}$ è indecidibile ed è riducibile a $B$, ciò implica automaticamente che anche $B$ sia indecidibile.

---

La dimostrazione richiesta nel secondo punto è presente sul libro di testo. Un esempio di linguaggio non riconoscibile è costituito dal linguaggio $\overline{A_{TM}}$.

[18xChris]

Non so se la seguente risposta va bene ai fini dell'esame (probabilmente il prof sta implicitamente chiedendo la dimostrazione spiegata a lezione, mentre io do' un esempio direttamente e con cio' dimostro la tesi in questione):

• Un linguaggio non riconoscibile e' un linguaggio per il quale non esistono riconoscitori (i.e. non possiamo stabilire sempre se accetta)
• Il linguaggio Atm accetta <M,w> se M accetta w
• Costruiamo $Atm^c$ che accetta <M,w> se M non accetta w
• Se M non accetta W o rifiuta o va in loop, ma nel caso vada in loop non possiamo accettare (nel caso vada in loop non terminera' mai: non possiamo sapere che andra' in loop nel caso dovesse andarci)
• Quindi $Atm^c$ non e' riconoscibile

[Exyss]

Hai dimostrato che la tua macchina che prova a riconoscere $A_{tm}^c$ non riconosce sempre se simula direttamente M(w), non che non esista una macchina che riconosca $A_{tm}^c$

È vero che $A_{tm}^c$ non è riconoscibile, ma ciò è dimostrabile ad esempio con la riduzione $\overline{A_{tm}} \leq_m A_{tm}^c$, visto che il primo è irriconoscibile

[LucaSforza]

Per dimostrare il secondo punto non basta dimostrare che Atm non è decidibile e dimostrare che un linguaggio L è decidibile sse L è T-riconoscibile e L complementare è T-riconoscibile? Poi da qui dato che abbiamo dimostrato che Atm non è decidibile, ma che abbiamo un ricoscitore di Atm (ovvero la macchina di Turing universale) possiamo usare la dimostrazione di prima (un linguaggio L è decidibile sse L è T-riconoscibile e L complementare è T-riconoscibile) per dimostrare che Atm complementrare non è decidibile.

[CasuFrost]

per il secondo punto si può usare la numerabilità delle TM e la non numerabilità dei linguaggi, ma questa è più concisa