Riducibilità

Due possibilità per riconoscere che un problema $P$ è indecidibile:

• supporre l’esistenza di una MdT che decide $P$ e provare che questo conduce a una contraddizione
• considerare un problema $P'$ di cui sia nota l’indecidibilità e dimostrare che $P'$ “non è più difficile” del problema in questione $P$

Teorema (”vero” problema della fermata)

$HALT_{TM} = \{\lang M,w\rang| M \text{ è una MdT e } M \text{ si arresta su } w\}$ è indecidibile

• Dimostrazione

Schema di riduzione

Dal problema $A$ al problema $B$

1. sappiamo che $A$ risulta indecidibile
2. vogliamo provare che $B$ è indecidibile
3. assumiamo per assurdo $B$ decidibile ed usiamo questa assunzione per provare $A$ decidibile
4. la contraddizione ci fa concludere: $B$ indecidibile

Teorema (problema del vuoto)

$E_{TM} = \{\langle M \rangle | M \text{ MdT tale che } L(M) = \empty\}$ è indecidibile

• Dimostrazione

Funzioni calcolabili

Una funzione $f: \sum^* \to \sum^*$ è calcolabile se esiste una MdT $M$ tale che su ogni input $w$, $M$ si arresta con $f(w)$, e solo con $f(w)$, sul suo nastro

Questa definizione sottolinea la differenza tra definire una funzione $f$, cioè definire i valori di $f$, e calcolare tali valori di $f$

Riducibilità