[6 giugno 2024] Calcolabilità

[matypist]

[Exyss]

Prima di tutto, osserviamo che il linguaggio $\varnothing$ sia regolare, mentre il linguaggio $\{ 0^n1^n \mid n \in N \}$ non lo è.

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) Verifica se $x \in \{ 0^n1^n \mid n \in N \}$. 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 NONREGULAR$. Concludiamo quindi che $\langle M, w \rangle \notin A_{TM} \implies f(\langle M, w \rangle) = \langle M_2 \rangle \notin NONREGULAR$.

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

• Se $x \notin \{ 0^n1^n \mid n \in N \}$ allora $M_2$ rifiuta, dunque $x \notin L(M_2)$.
• Se $x \in \{ 0^n1^n \mid n \in N \}$ 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 \{ 0^n1^n \mid n \in N \} \iff x \in L(M_2)$, il che è equivalente a dire che $L(M_2) = \{ 0^n1^n \mid n \in N \}$, da cui segue che $\langle M_2 \rangle \in NONREGULAR$. Concludiamo quindi che $\langle M, w \rangle \in A_{TM} \implies f(\langle M, w \rangle) = \langle M_2 \rangle \in NONREGULAR$.

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

---

La dimostrazione richiesta nel secondo punto è presente sul libro di testo.

[18xChris]

Ho una domanda sul punto 1a) :
Hai verificato l'appartenenza di x ad un preciso linguaggio non regolare (${0^n1^n}$), ma x potrebbe appartenere ad esempio a ${0^n 1^n 2^n}$, che e' comunque non regolare, quindi non capisco perche' vada bene verificare l'appartenenza di x ad un linguaggio particolare e non ad un linguaggio non regolare qualsiasi (possiamo verificare se x e' convertibile in regex ad esempio)

[Exyss]

Difatti va bene un qualsiasi linguaggio non regolare (decidibile ovviamente) ai fini della dimostrazione.