Pysähtymisongelma
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
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
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 havainnollistamisen vuoksi näyttää vaikkapa seuraavalta:
| 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:
| 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
- ↑ Halting Problem – Brilliant brilliant.org. Viitattu 3.7.2018. (englanniksi)
- ↑ 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