Pysähtymisongelma: Turingin todistus, määritelmä ja esimerkit
Tutustu pysähtymisongelmaan: Turingin todistus, selkeä määritelmä ja konkreettiset esimerkit, jotka havainnollistavat, miksi pysähtymisongelmaa ei voi algoritmisesti ratkaista.
Pysähtymisongelma on keskeinen ongelma tietojenkäsittelytieteessä. Perusmuodossaan kysytään: annettuna ohjelma ja sen syöte, pystymmekö ennustamaan etukäteen, pysähtyykö ohjelma vai pyöriikö se ikuisesti? Käytännössä haluaisimme ohjelman P, joka saa syötteenään mitä tahansa ohjelmaa F ja sen syötettä I ja palauttaa totuusarvon siitä, toimiiko F syötteellä I ikuisesti vai ei.
Määritelmä ja esimerkit
Esimerkiksi seuraava ohjelma pyörii ikuisesti:
while True: continue Mutta tämä ohjelma pysähtyy heti:
while False: continue Oletetaan kuvitteellisesti, että on olemassa ohjelma P, joka ratkaisee pysähtymisongelman tarkasti. Alkuperäisessä tekstissä P on määritelty palauttamaan true, jos annettu ohjelma toimii ikuisesti annetulla syötteellä, ja false, jos se pysähtyy. Kirjoitetaan tämä pseudokoodina:
def P(F, I): if F(I) runs forever: return True else: return False Tällainen P voisi siis tarkastella mitä tahansa ohjelmaa ja kertoa varmasti, jatkuuko sen suoritus ikuisesti vai pysähtyykö se.
Itseviittaus ja ristiriidan rakentaminen
Käytämme P:tä rakentamaan uusia ohjelmia, jotka käyttävät P:n vastausta hyväkseen. Ensiksi määrittelemme Q:n, joka kysyy P:ltä, pyöriikö annettu ohjelma kun sille annetaan kopio itsestään syötteenä:
def Q(F): return P(F, F) Q(F) palauttaa siis true juuri silloin, kun F(käytettynä itsellään) pyörii ikuisesti.
Seuraavaksi rakennamme R:n, joka käyttäytyy päinvastoin kuin Q:n ennustus: R katsoo Q:n vastausta ohjelmasta F ja tekee sen mukaan
def R(F): if Q(F): return # lopeta eli pysähdy else: while True: continue # pyöri ikuisesti R siis pysähtyy, jos Q(F) sanoo, että F(F) pyörii ikuisesti; ja se pyörii ikuisesti, jos Q(F) sanoo, että F(F) ei pyöri ikuisesti.
R:n suorittaminen itsellään johtaa ristiriitaan
Kun nyt annamme R:lle syötteenä sen oman koodinsa, eli tarkastelemme R(R):ää, syntyy kaksijakoinen vaihtoehto:
- Oletetaan ensin, että R(R) ei pyöri ikuisesti (eli se pysähtyy). Tällöin Q(R) oli määritelmän mukaan todennut true (koska Q(R) = P(R, R) kertoo, että R(R) pyörii ikuisesti). Mutta jos Q(R) oli true, R(R) olisi pysähtynyt (R:n koodin mukaan), eli samasta oletuksesta seuraa, että R(R) sekä pyörii ikuisesti että pysähtyy—ristiriita.
- Oletetaan seuraavaksi, että R(R) pyörii ikuisesti. Tällöin Q(R) on false (koska P(R, R) ilmoittaa, ettei R(R) pyöri ikuisesti). Mutta jos Q(R) on false, niin R(R) koodin mukaan se pysähtyy—jälleen ristiriita.
Kummassakaan tapauksessa tilanne ei voi olla johdonmukainen, joten alkuperäinen oletus siitä, että P olemassa ja toimii oikein kaikilla ohjelmapareilla (F, I), johtaa loogiseen ristiriitaan.
Päätelmä ja merkitys
Täten päädymme siihen, että ei voi olla yhtään yleistä ohjelmaa P, joka päättää pysähtymisongelman kaikilla mahdollisilla ohjelma- ja syötepareilla. Toisin sanoen pysähtymisongelma on ratkaisematon (undecidable). Tämä johtopäätös perustuu ristiriidan rakentamiseen itseviittauksen avulla—tekniikka on läheistä sukua diagonalisaatio-ajatukselle.
Tämän tuloksen esitti ensimmäisenä Alan Turing vuonna 1936. Turingin todistus on perusta monille myöhemmille tuloksille laskettavuusteoriassa ja osoittaa rajoituksia sille, mitä algoritmit yleisesti voivat ratkaista.
Lisähuomioita
- Usein todistuksessa käytetään varianttia, jossa P ilmoittaa, pysähtyykö vai ei (eli palauttaa true jos pysähtyy). Seuraava rakentelu mukautetaan sen mukaan—perusidea itseviittauksesta ja ristiriidasta pysyy samana.
- Pysähtymisongelman päätteleminenkelvottomuus tarkoittaa, että on olemassa ohjelmia, joiden käyttäytymistä emme voi etukäteen täysin ennustaa algoritmisesti kaikissa tapauksissa. Tämä ei estä pysähtymisen analysointia tietyissä rajoitetuissa luokissa ohjelmia, mutta yleisratkaisua ei ole.
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.
Etsiä