Dimostrare da zero che un problema è indecidibile, con un argomento diagonale, è faticoso. Per fortuna basta farlo una volta. Per tutti gli altri problemi si usa una riduzione: si mostra che, se sapessimo risolvere il nuovo problema, sapremmo risolvere anche uno già noto come irrisolvibile. La riduzione è lo strumento di lavoro quotidiano sia della calcolabilità sia della complessità, e capirne bene la direzione evita la maggior parte degli errori.
La definizione
Siano A e B due linguaggi. A è riducibile per mappatura a B, e si scrive A ≤ₘ B, se esiste una funzione calcolabile f tale che per ogni stringa w:
w ∈ A se e solo se f(w) ∈ B
«Calcolabile» significa che esiste una macchina di Turing che, su input w, si ferma sempre lasciando f(w) sul nastro. La funzione trasforma istanze del primo problema in istanze del secondo, preservando la risposta.
L'intuizione è: B è almeno difficile quanto A. Se ho un decisore per B, ottengo un decisore per A calcolando f(w) e chiedendo a B.
Le due conseguenze
Da A ≤ₘ B discendono due implicazioni:
- se B è decidibile, allora A è decidibile;
- se A è indecidibile, allora B è indecidibile.
La seconda è la contronominale della prima, ed è quella che si usa per dimostrare l'indecidibilità. Lo stesso vale per la riconoscibilità: se A ≤ₘ B e B è riconoscibile, anche A lo è.
La direzione giusta
L'errore più comune è ridurre nel verso sbagliato. Per dimostrare che un problema nuovo B è indecidibile:
- si parte da un problema A già noto come indecidibile, per esempio A_TM;
- si costruisce f che trasforma istanze di A in istanze di B.
Se si fa il contrario, cioè si riduce B ad A_TM, si dimostra soltanto che B non è più difficile di A_TM, il che non dice nulla sulla sua indecidibilità. Un modo per ricordarlo: si riduce dal problema noto al problema nuovo.
Esempio 1: il linguaggio vuoto
Sia E_TM = {⟨M⟩ : L(M) = ∅}. Vogliamo mostrare che è indecidibile.
Data ⟨M, w⟩, costruiamo la macchina M_w che, su input x, ignora x, simula M su w e accetta se M accetta. Allora:
- se M accetta w, M_w accetta ogni stringa: L(M_w) = Σ*, non vuoto;
- se M non accetta w, M_w non accetta nulla: L(M_w) = ∅.
La funzione ⟨M, w⟩ ↦ ⟨M_w⟩ è calcolabile: si tratta di scrivere una descrizione di macchina a partire da un'altra. Abbiamo così una riduzione di A_TM al complemento di E_TM. Poiché un linguaggio è decidibile se e solo se lo è il suo complemento, E_TM è indecidibile.
Si può dire di più: il complemento di E_TM è riconoscibile, perché si possono provare in parallelo tutte le stringhe con la tecnica a coda di rondine. Quindi E_TM non è riconoscibile, altrimenti sarebbe decidibile.
Esempio 2: equivalenza di macchine
Sia EQ_TM = {⟨M₁, M₂⟩ : L(M₁) = L(M₂)}. Usiamo il risultato precedente.
Sia R una macchina che rifiuta ogni input, quindi L(R) = ∅. La funzione ⟨M⟩ ↦ ⟨M, R⟩ è calcolabile e soddisfa:
⟨M⟩ ∈ E_TM se e solo se ⟨M, R⟩ ∈ EQ_TM
Dunque E_TM ≤ₘ EQ_TM, e EQ_TM è indecidibile. Poiché E_TM non è riconoscibile, nemmeno EQ_TM lo è. Si dimostra inoltre che neppure il complemento di EQ_TM è riconoscibile: l'equivalenza fra programmi è un problema difficile in entrambe le direzioni.
Riduzioni di Turing
Esiste una nozione più generale. A è Turing-riducibile a B, scritto A ≤_T B, se A si può decidere con una macchina che dispone di un oracolo per B: una scatola nera che risponde istantaneamente a domande del tipo «x ∈ B?», anche più volte e in modo adattivo.
Differenze importanti:
| Aspetto | Mappatura (≤ₘ) | Turing (≤_T) |
|---|---|---|
| Domande all'oracolo | Una sola, alla fine | Quante se ne vuole |
| Uso della risposta | Restituita così com'è | Elaborata liberamente, anche negata |
| Preserva la riconoscibilità | Sì | No |
| Ogni linguaggio si riduce al complemento | No | Sì |
Proprio l'ultima riga spiega perché, nell'esempio del linguaggio vuoto, siamo passati per il complemento: con una riduzione di Turing avremmo potuto negare la risposta direttamente, ma avremmo perso l'informazione sulla riconoscibilità. Le riduzioni di mappatura sono più restrittive e per questo dicono di più.
Uno schema da seguire
Quando devo dimostrare l'indecidibilità di un problema, procedo così:
- scelgo un problema di partenza noto: A_TM, HALT_TM, E_TM o un altro già dimostrato;
- descrivo f come un programma: «data l'istanza x, costruisci la macchina che…»;
- verifico che f sia calcolabile e che si fermi sempre, anche quando le macchine descritte da f non si fermerebbero;
- dimostro entrambe le direzioni del «se e solo se».
Il punto 3 è sottile: f non deve eseguire le macchine, ma solo scriverne la descrizione. Costruire il testo di M_w richiede un tempo finito anche se M_w, una volta eseguita, girerebbe per sempre.
In sintesi
- A ≤ₘ B significa che esiste f calcolabile con w ∈ A se e solo se f(w) ∈ B.
- Per provare che B è indecidibile si riduce a B un problema già noto come indecidibile.
- E_TM ed EQ_TM sono indecidibili e non riconoscibili.
- Le riduzioni di Turing ammettono più domande a un oracolo ma non preservano la riconoscibilità.
- La funzione di riduzione scrive descrizioni di macchine, non le esegue.
