Pysähtymisongelma

Wikipediasta
Siirry navigaatioon Siirry hakuun

Pysähtymisongelma koskee syötteenä annetun, mielivaltaisen ohjelman pysähtymistestausta. Ongelmassa pitää määrittää, pysähtyykö ohjelman suoritus koskaan annetulla syötteellä. 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).[1]

Pseudokoodi[muokkaa | muokkaa wikitekstiä]

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:

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

"TEE_PÄINVASTOIN" annetaan parametriksi itselleen, jonka sisältämä pysähtymistestausfunktio testaa pysähtyykö sille annettu kone saadessaan oman koodinsa syötteenään. Todistuksen kannalta tämän ohjelman olennainen osa on ehtolause. Jos funktio palauttaa toden, tulisi "TEE_PÄINVASTOIN"-ohjelman pysähtyä, mutta tällöin päädytäänkin ikuiseen silmukkaan, eikä "TEE_PÄINVASTOIN" siis pysähdykään. Kyseinen ristiriita on todistus siitä, että toimivaa pysähtymistestausfunktiota ei voi olla olemassa nykyisin tunnetuilla laskennan malleilla.

Todistus diagonaalimenetelmällä[muokkaa | muokkaa wikitekstiä]

Jokainen Turingin kone on muunnettavissa lähdekoodinsa perusteella yksilölliseksi merkkijonoksi ja siten (usein valtavaksi) luonnolliseksi luvuksi, joka voidaan syöttää mille tahansa Turingin koneelle. Luonnoliset luvut voi käydä järjestyksessä läpi luoden niistä äärettömän taulukon, joka käsittää kaikki mahdolliset Turingin koneet ja niiden syötteet, ja johon voi merkitä mikä kone pysähtyy milläkin syötteellä.[2] Se voisi havainnoillistamisen vuoksi näyttää vaikkapa seuraavalta:

Turingin koneet
1 2 3 4 5 ...
1 Jatkaa Pysähtyy Jatkaa Pysähtyy Jatkaa ...
2 Pysähtyy Pysähtyy Pysähtyy Pysähtyy Pysähtyy ...
3 Jatkaa Jatkaa Jatkaa Jatkaa Jatkaa ...
4 Pysähtyy Jatkaa Pysähtyy Jatkaa Pysähtyy ...
5 Pysähtyy Pysähtyy Jatkaa Jatkaa Pysähtyy ...
... ... ... ... ... ... ...

Jokainen rivi listaa yhden Turingin koneen ja sen pysähtymisjoukon, eli millä syötteillä se lopulta pysähtyy.

Cantorin diagonaaliargumentin nojalla voidaan ottamalla kaikki arvot järjestyksessä vasemmasta ylänurkasta alaoikealle edeten (punaiset ruudut) ja kääntämällä niiden arvot päinvastaiseksi luoda uusi pysähtymisjoukko D joka poikkeaa kaikista mahdollisista listatuista riveistä.[2] Havainnollistus:

Olematon rivi D
1 2 3 4 5 ...
D Pysähtyy Jatkaa Pysähtyy Pysähtyy Jatkaa ...

Oletetaan että on olemassa Turingin kone, joka kykenee erottamaan kuuluuko jokin syöte joukkoon D vai ei (se kuuluu jos ja vain jos sen kuvaama kone jatkaa ikuisesti saatuaan oman numeronsa syötteenä) ja toimimaan sitten sen perusteella; tämä kyky on pysähtymisongelman ratkaisevan Turingin koneen edellytys. Jos tämmöiseen kykenevä kone on olemassa, voidaan luoda kone jonka pysähtymisjoukko on D. Diagonaaliargumetin nojalla tämmöisen pysähtymisjoukon omaavaa konetta ei kuitenkaan ole, joten pysähtymisongelman ratkaisevaa Turingin konetta eli algoritmia ei myoskään ole.[2]

Lähteet[muokkaa | muokkaa wikitekstiä]

  1. Halting Problem – Brilliant brilliant.org. Viitattu 3.7.2018. (englanniksi)
  2. a b c Martin Davis: ”Turing suunnittelee yleiskäyttöisen laskijan - Turing soveltaa Cantorin diagonaalimenetelmää”, Tietokoneen historia Leibnizista Turingiin. Suomentanut Risto Vilkko. Vantaa: Dark Oy, 2003. ISBN 951-884-364-3. suomi