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.