• Autore:   Elia Argentieri
  • Ultima modifica:   6 mag 2022 18:07
  • Redazione:   25 gen 2022 22:35
  • Sorgente di questa pagina
  • Tempo di lettura:   2 minuti

Oggi vedremo un altro insieme speciale che chiameremo K₀ che fonda la sua origine nel cosidetto problema della fermata che confuta l’affermazione di Hilbert secondo la quale tutti i problemi matematici avrebbero una caratterizzazione esatta.

Tutti i formalismi Turing-equivalenti soffrono del problema della fermata, ovvero nessuna costruzione realizzata con qualsiasi formalismo T-equivalente riesce a decidere se un dato algoritmo termina su un dato input, senza eseguire o simulare l’algoritmo stesso.

Se esistesse tale algoritmo, potremmo farci anticipare dallo stesso se un dato algoritmo con un dato input termina ed evitare completamente la computazione qualora questa dovesse divergere.

Problema della fermata

Dati \(x,y. \varphi_y(x) \downarrow ?\) cioè \(P_y(x)\) si ferma?

Riprendiamo l’insieme K che abbiamo formalizzato ieri:

$$K = \{x | \varphi_x(x) \downarrow\}$$

È possibile formalizzare anche il problema della fermata in termini di insiemi:

$$ K_0 = \{(x,y) | \varphi_y(x) \downarrow \} = \{(x,y) | \exists z.T(y,x,z)\} $$
dove T è il predicato di Kleene che abbiamo già incontrato nel teorema di forma normale.

Ricordo che il predicato di Kleene \(T(y,x,z)\) è una funzione calcolabile totale (ricorsiva primitiva) e risulta vero se e solamente se z è la codifica di una computazione terminante di \(M_x\) con dato iniziale y.

Non decidibilità del problema della fermata

Teorema: \(K_0\) non è ricorsivo (decidibile).

Dimostrazione: si ha che \(x \in K \iff (x,x) \in K_0\) , quindi se \(K_0\) fosse ricorsivo lo sarebbe anche \(K\) , ma abbiamo già dimostrato che non è questo il caso.

Notiamo la presenza dell’insieme \(K\) nella dimostrazione e la relazione che intercorre tra \(K \text{ e } K_0\) . La tecnica usata nella dimostrazione per collegare i due insiemi si basa sul concetto di riducibilità, che introdurrò prossimamente.