INDECIDIBILITÀ DELL'HALTING PROBLEM (problema della fermata)
Esiste la possibilità di stabilire a priori (con un opportuno programma), presi comunque un programma P e una stringa di input v, se
P con input v converge o P con input v diverge?
La risposta è negativa; ciò è stato dimostrato nel 1936 da Turing. Per una
dimostrazione vedi qui. Per un inquadramento storico vedi qui.