Un problema di decisione è una domanda che dipende da un insieme finito di parametri e che ammette una risposta sì/no (in generale, una risposta binaria).
Un’istanza di un problema viene fornita specificando dei valori per i suoi parametri, quindi un problema di decisione $\Pi$ può anche essere pensato come una funzione,
$$ \Pi : D_\Pi \rarr \{ SI, NO\} $$
dove:
Un’istanza positiva di $\Pi$ è un’istanza del problema $\Pi$ che ha risposta SI: l’insieme delle istanze positive di $\Pi$ è dunque:
$$ Y_\Pi = \{x \in D_\Pi \ | \ \Pi(x)=SI\} $$
Ci sono dei problemi che non possono essere risolti dalle macchine di Turing (e quindi, per la tesi di Church-Turing, neanche da altri modelli di calcolo). Avendo formalizzato le macchine di Turing come riconoscitori di linguaggi, per studiare i problemi che esse possono risolvere bisogna prima trovare una corrispondenza tra il riconoscimento di linguaggi e la risoluzione di altre classi di problemi, a partire dai problemi di decisione (che sono quelli per cui la corrispondenza è più immediata).
Una codifica di un problema $\Pi$ su un alfabeto $\Sigma$ è una funzione
$$ \#: D_\Pi \rarr \Sigma^* $$
che associa a ogni istanza del problema una stringa $\#(w)\in \Sigma^$. Tale funzione deve essere invertibile (cioè deve esistere una funzione $\#^{-1}:\Sigma^\rarr D_\Pi$ tale che $\#^{-1}(\#(x))=x$ per ogni $x\in D_\Pi$, il che rende in pratica possibile la decodifica di una stringa, per riottenere la corrispondente istanza del problema) e “calcolabile da un programma” (formalmente, dovrebbe essere calcolabile da una macchina di Turing o un altro modello equivalente, ma per semplicità si può sfruttare la tesi di Church-Turing, che permette di considerare funzioni “intuitivamente calcolabili”).
Data una funzione di codifica $\#$ su $\Sigma$ per un problema $\Pi,$ il linguaggio associativo a $\Pi$ è l’insieme delle stringhe che codificano le istanze positive del problema:
$$ L(\Pi)=\{w \in \Sigma^\ | \ w \text{ è la codifica di un'istanza positiva di }\Pi\} \\ =\{w \in \Sigma^\ | \ w = \#(x) \text{ con } x\in Y_\Pi\} \\ =\{w \in \Sigma^*\ | \ \Pi(\#^{-1}(x))=SI\} $$
Una macchina di Turing che riconosce $L(\Pi)$ risolve a tutti gli effetti $\Pi$: data la stringa $\#(x)$ che ceidifica un’istanza $x$ del problema, la macchina accetta $\#(x)$ se e solo se $\Pi(x)=SI$, mentre rifiuta $\#(x)$ o non si arresta se e solo se $\Pi(x)=NO$.
Ci sono altre classi di problemi ai quali è possibile associare linguaggi, riconducendoli a problemi di decisione equivalenti. Ad esempio, si consideri il seguente problema TS, chiamato problema del commesso viaggiatore:
Parametri: Un insieme di città $C = \{c_1, ..., c_n\}$, e la distanza $d(c_i, c_j)\in \natnums$ tra ogni coppia di città.
Domanda: Qual è il percorso minore che visita tutte le città una e una sola volta e torna alla città di origine? Formalmente, qual è un ordinamento $\lang c_{r(1)}, ..., c_{r(n)}\rang$ delle città che minimizza la funzione
$$ \Big( \sum_{i=1}^{n-1}d(c_{r(i)}, c_{r(i+1)})\Big) + d(c_{r(n)}, c_{r(1)}) $$
(dove $r:\{1, ..., n\} \rarr \{1, ..., n\}$ è una permutazione degli indici delle città)?