[27 marzo 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

[18xChris]

Per il secondo punto propongo la soluzione presente sugli appunti di CasuFrost

[cornflexxx]

Supponiamo $W_{TM}\in RE$, con decisore $D$, allora possiamo costruire un decisore T per $A_{TM}$:

1. Input $\langle M,w\rangle$
2. Costruisce la $TM$ $M'$:

• Su input $x$ : esegue $M(x)$, se $M$ accetta allora stampa $a$ e accetta
• altrimenti rifiuta

3. eseguiamo $D(\langle M',w,a\rangle)$ se accetta $\implies$ $T$ accetta