Pysähtymisongelma

Wikipedia

Pysähtymisongelma koskee syötteenä annetun, mielivaltaisen ohjelman pysähtymistestausta. Ongelmassa pitää määrittää, kun on annettu ohjelma ja sen syöte, pysähtyykö ohjelman suoritus koskaan. Alan Turing todisti vuonna 1936, että ei voi olla olemassa algoritmia, joka ratkaisisi pysähtymisongelman kaikilla syötteillä. Pysähtymisongelma on mahdoton ratkaista nykyisillä laskennan malleilla (katso Turingin kone).

Kuvitellaan, että olisi olemassa ratkaisu, funktio, jolle annetaan syötteenä ohjelman koodi ja sen saama syöte:

PYSÄHTYYKÖ(ohjelma, syöte)

Voitaisiinkin tehdä ohjelma, joka käyttäisi edellä mainittua funktiota hyväkseen:

PYSÄHDY_ITSE(ohjelma)
{
   if(PYSÄHTYYKÖ(ohjelma, ohjelma))
       suorita_päättymätön_silmukka
   else
       pysähdy
}

"PYSÄHDY_ITSE" annetaan parametriksi pysähtymistestausfunktiolle. Todistuksen kannalta tämän ohjelman olennainen osa on ehtolause. Jos funktio palauttaa toden, tulisi ohjelman pysähtyä, mutta tällöin päädytäänkin ikuiseen silmukkaan, eikä ohjelma siis pysähdykään. Kyseinen ristiriita on todistus siitä, että toimivaa pysähtymistestausfunktiota ei voi olla olemassa.