[9 gennaio 2023] Calcolabilità

[matypist]

[Exyss]

Per il primo punto, ripropongo la soluzione presente sui miei appunti:

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

[aflaag]

Dimostrazione sulla falsa riga di quella di @Exyss

Si prenda un $L_i \in \textsf{REC}$, e viene dunque riconosciuto da qualche $R_i$ riconoscitore tale che $L(R_i) = L_i$; per costruirne un decisore, è sufficiente considerare la seguente macchina $D_i$ che, su input $w \in \Sigma^*$, computi come segue:

• $M$ simula concorrentemente ogni macchina $R_j$ per ogni $j \in [1, k]$;
• poiché $L_1, \ldots, L_k$ partizionano $\Sigma^*$, una ed una sola macchina accetterà, e dunque:
  • se la macchina che accetta è proprio $R_i$, $D_i$ accetta
  • se la macchina che accetta è un'altra $R_j$ con $j \neq i$, $D_i$ rifiuta

Allora, per costruzione $R_i$ decide $L_i$; infine, poiché il ragionamento è applicabile ad ogni linguaggio, segue la tesi.