Pysähtymisongelma

Halting-ongelma on tietojenkäsittelytieteen ongelma. Ongelmassa tarkastellaan tietokoneohjelmaa ja selvitetään, jatkuuko ohjelma ikuisesti vai ei. Sanomme, että ohjelma "ratkaisee pysähtymisongelman", jos se voi katsoa mitä tahansa toista ohjelmaa ja kertoa, juokseeko tuo toinen ohjelma ikuisesti vai ei.

Esimerkiksi tällainen ohjelma:

while True: jatka;

kiertää ikuisesti, mutta ohjelma

while False: jatka;

pysähtyy hyvin nopeasti.

Onko olemassa ohjelmaa, joka ratkaisee pysähtymisongelman? Kävi ilmi, ettei sellaista ole. Todistamme tämän osoittamalla, että jos on olemassa ohjelma, joka ratkaisee pysähtymisongelman, tapahtuu jotain mahdotonta. Toistaiseksi käyttäydymme siis kuin olisi olemassa ohjelma, joka ratkaisee pysähtymisongelman. Tässä P on funktio, joka arvioi funktiota F (jota kutsutaan argumentilla I) ja palauttaa true, jos se toimii ikuisesti, ja false, jos ei.

def P(F, I): if F(I) runs forever: return True; else: return False;

P voi tarkastella mitä tahansa ohjelmaa ja selvittää, toimiiko se ikuisesti vai ei. Käytämme P:tä uuden ohjelman tekemiseen, jota kutsumme Q:ksi. Q tarkastelee toista ohjelmaa ja vastaa sitten seuraavaan kysymykseen: "Jos ajamme tämän ohjelman ja laitamme sen katsomaan kopiota itsestään, toimiiko se ikuisesti?". Voimme tehdä Q:n, koska meillä on P. Meidän tarvitsee vain käskeä Q:ta luomaan uusi ohjelma, joka on vanha ohjelma, joka katsoo itseään, ja sitten käyttää P:tä selvittääksemme, toimiiko uusi ohjelma ikuisesti vai ei.

def Q(F): return P(F, F);

Nyt luodaan toinen ohjelma R. R tarkastelee toista ohjelmaa ja kysyy Q:lta vastausta kyseiseen ohjelmaan. Jos Q vastaa "kyllä, jos ajamme tämän ohjelman ja laitamme sen katsomaan kopiota itsestään, se toimii ikuisesti", R pysähtyy. Jos Q vastaa "ei, jos ajamme tämän ohjelman ja panemme sen katsomaan kopiota itsestään, se ei pyöri ikuisesti", R menee loputtomaan silmukkaan ja pyörii ikuisesti.

def R(F): if Q(F): return; //lopeta else: while True: continue; //silmukka ikuisesti

Nyt tarkastellaan, mitä tapahtuu, jos R:n annetaan katsoa kopiota itsestään. Kaksi asiaa voi tapahtua: se joko pysähtyy tai toimii ikuisesti.

Jos R-ohjelman ajaminen ja sen laittaminen katsomaan kopiota itsestään ei toimi ikuisesti, Q vastasi "kyllä, jos ajamme tämän ohjelman ja laitamme sen katsomaan kopiota itsestään, se toimii ikuisesti". Mutta Q sanoi tämän katsoessaan R:ää itseään. Joten Q itse asiassa sanoi: "kyllä, jos ajamme R:n ja panemme sen katsomaan kopiota itsestään, se toimii ikuisesti". Joten: Jos R, joka toimii kopiossa itsestään, ei toimi ikuisesti, se toimii ikuisesti. Tämä on mahdotonta.

Jos R-ohjelman ajaminen ja sen laittaminen katsomaan kopiota itsestään kestää ikuisesti, Q vastasi "ei, jos ajamme tämän ohjelman ja laitamme sen katsomaan kopiota itsestään, se ei kestä ikuisesti". Mutta Q sanoi tämän katsoessaan R:ää itseään. Joten Q itse asiassa sanoi: "ei, jos ajamme R:n ja panemme sen katsomaan kopiota itsestään, se ei pyöri ikuisesti". Joten: Jos R:n suorittaminen kopion itsensä päällä toimii ikuisesti, se ei toimi ikuisesti. Tämäkin on mahdotonta.

Tapahtuipa mitä tahansa, saamme mahdottoman tilanteen. Teimme jotain väärin, ja meidän on selvitettävä, mitä se oli. Useimmat asiat, joita teimme, eivät olleet väärin. Emme voi sanoa, että "ohjelman laittaminen katsomaan kopiota itsestään on väärin" tai että "toisen ohjelman katsominen ja sen jälkeen silmukkaan meneminen, jos se sanoo jotain, ja lopettaminen, jos se sanoo jotain muuta" on väärin. Ei ole järkevää sanoa, että emme saa tehdä näitä asioita. Ainoa asia, jonka teimme ja joka näyttää siltä, että se voisi olla väärin, on se, että teeskentelimme, että P:n kaltainen ohjelma on ylipäätään olemassa. Ja koska tämä on ainoa asia, joka voisi olla väärin, ja jonkin täytyy olla väärin, se on se. Tämä on todiste siitä, että P:n kaltaista ohjelmaa ei ole olemassa. Ei ole olemassa ohjelmaa, joka ratkaisee pysähtymisongelman.

Alan Turing löysi tämän todisteen vuonna 1936.

Kysymyksiä ja vastauksia

K: Mikä on Halting-ongelma?

V: Halting-ongelma on tietojenkäsittelytieteen ongelma, jossa tarkastellaan tietokoneohjelmaa ja määritetään, toimiiko ohjelma ikuisesti vai ei.

K: Mistä tiedämme, ratkaiseeko ohjelma Halting-ongelman?

V: Sanomme, että ohjelma "ratkaisee pysähtymisongelman", jos se voi tarkastella mitä tahansa toista ohjelmaa ja kertoa, juokseeko tuo toinen ohjelma ikuisesti vai ei.

K: Voiko jotenkin todistaa, ettei tällaista ohjelmaa ole olemassa?

V: Kyllä, osoittamalla, että jos tällainen ohjelma olisi olemassa, tapahtuisi jotain mahdotonta. Tämän todisteen löysi Alan Turing vuonna 1936.

K: Mitä P tekee?

V: P on funktio, joka arvioi toista funktiota F (jota kutsutaan argumentilla I) ja palauttaa totuuden, jos se toimii ikuisesti, ja muutoin väärän.

K: Mitä Q tekee?

V: Q tarkastelee toista ohjelmaa ja vastaa sitten kysymykseen, johtaako saman ohjelman suorittaminen itsessään äärettömään silmukkaan. Se tekee tämän käyttämällä P:tä annetun funktion F evaluointiin.

K: Mitä R tekee?

V: R tarkastelee toista ohjelmaa ja kysyy Q:lta vastausta kyseiseen ohjelmaan. Jos Q vastaa "kyllä, jos ajamme tämän ohjelman ja laitamme sen tarkastelemaan kopiota itsestään, se toimii ikuisesti", R pysähtyy; jos Q kuitenkin vastaa "ei, jos ajamme tämän ohjelman ja laitamme sen tarkastelemaan kopiota itsestään, se ei toimi ikuisesti", R menee äärettömään silmukkaan ja toimii ikuisesti.

K: Mitä tapahtuu, kun R:n laitetaan katsomaan itseään?

V: Kaksi asiaa voi tapahtua - joko R pysähtyy tai pyörii ikuisesti - mutta molemmat tulokset ovat mahdottomia sen mukaan, mitä on todistettu siitä, että P:n kaltaisia ohjelmia ei ole olemassa, joten jonkin on täytynyt mennä pieleen jossakin matkan varrella, joka johti siihen, että R saatiin katsomaan itseään.