Problema della terminazione
# Problema della terminazione

Il problema della terminazione (dall'inglese Halting problem, tradotto anche con problema dell'arresto o problema della fermata) chiede se sia sempre possibile, descritto un algoritmo e un determinato ingresso finito, stabilire se l'algoritmo in questione termina o continua la sua esecuzione all'infinito. È stato dimostrato che non può esistere un algoritmo generale in grado di risolvere il problema per tutti i possibili ingressi. La versione più nota del problema è quella proposta nel 1936 dal matematico Alan Turing, insieme alla dimostrazione della sua indecidibilità.

## Dimostrazione di indecidibilità

Si supponga per assurdo che esista un algoritmo, implementato in uno pseudolinguaggio, che prende in ingresso un qualsiasi altro algoritmo a avente un ingresso finito d ed è in grado di stabilire se a termina in tempo finito (restituendo il valore true) o se non termina (restituendo in questo caso il valore false).

Essendo per la macchina sia a sia d sequenze indistinte di simboli, è possibile passare come secondo parametro di C lo stesso algoritmo a, ovvero eseguire C(a,a).

Sia ora loop un programma che non termina mai (ad esempio while true do done): è possibile costruire un altro algoritmo chiamato K che, prendendo in ingresso a, esegue loop non restituendo alcun valore se C(a,a) restituisce true, mentre restituisce true se C(a,a) restituisce false. Ovvero:

Quindi K termina restituendo il valore true solo se l'algoritmo a con ingresso a non termina, altrimenti K continua a eseguire loop ciclando all'infinito senza restituire alcun valore.

Passando all'algoritmo K lo stesso K, ovvero K(K), questo algoritmo termina, restituendo il valore true, solo se l'algoritmo K con input K non termina. Ovvero K(K) termina se e solo se K(K) non termina, il che è una contraddizione che prova essere assurda l'ipotesi iniziale sull'esistenza di un algoritmo C che, dato un qualsiasi algoritmo a e un suo input d, è in grado di stabilire se a(d) termina o non termina.

## Dimostrazione che il linguaggio dell'Halting Problem è un linguaggio non decidibile

Si indichi con $L_H$ il linguaggio dell'Halting problem e si supponga che $L_H$ sia decidibile. Allora per definizione esiste una macchina di Turing T che decide $L_H$ e che per un qualsiasi input x la computazione T(x) va

* nello stato di accettazione se x$\in$ $L_H$ ;
* nello stato di rigetto se x$\not \in$$L_H$ .

Da T si deriva una seconda macchina di Turing T' complementando gli stati di accettazione e di rigetto della macchina T, quindi la computazione di T'(x) va

* nello stato di accettazione se x$\not \in$$L_H$ ;
* nello stato di rigetto se x $\in$ $L_H.$

Da T' si deriva una terza macchina di Turing T'' che o accetta o non termina, quindi la computazione di T''(x) va

* nello stato di accettazione se T' accetta;
* non termina se T' rigetta.

Poiché l'insieme delle macchine di Turing Ť è numerabile allora T $\in$ Ť questo implica che $\exists$ n $\in$ N (insieme dei numeri naturali) tale che $T_n(n)$ = T''(n).

Se $T_n(n)$ accetta allora anche T'(n) dovrebbe accettare, ma se T'(n) accetta allora significa che n$\not \in$$L_H$ e se n$\not \in$$L_H$ allora $T_n(n)$ rigetta.

Se $T_n(n)$ rigetta allora anche T'(n) dovrebbe rigettare, ma se T'(n) rigetta allora n $\in$ $L_H$ e se n $\in$ $L_H$ allora $T_n(n)$ accetta.

In entrambi i casi esiste una contraddizione, quindi T'' non esiste e poiché T'' è ottenuta mediante semplici modifiche alla macchina T che decide $L_H$ questo porta a dire che $L_H$ non è decidibile.

## Relazioni con altri teoremi

Il teorema di Rice è una versione più generale del teorema che afferma che il problema della terminazione è indecidibile. Infatti esso afferma che, per ogni proprietà non banale delle funzioni parziali, è indecidibile il problema di determinare quali funzioni soddisfino questa proprietà e quali no.

