Problem ustavljanja (Haltingov problem): definicija in dokaz Alana Turinga
Haltingov problem: razumite Turingov dokaz, zakaj ni univerzalnega preverjalca ustavljanja programov — jasna razlaga, primeri in posledice za računalništvo.
Haltingov problem (problem ustavljanja) je osnovni problem v računalništvu: gre za vprašanje, ali obstaja algoritem, ki za poljuben program F in njegovo vhodno vrednost I odloči, ali bo F(I) na koncu ustavil ali pa bo tekla v neskončnost. Če bi tak algoritem obstajal, bi mu rekli, da “rešuje problem ustavljanja”.
Primeri za lažje razumevanje (v slogu Pythona):
while True: continue # teče v nedogled while False: continue # se takoj ustavi Vprašanje: ali obstaja splošen program P, ki za poljuben program F in vhod I vrne true, če F(I) ne ustavi (teče v nedogled), in false v nasprotnem primeru? Alan Turing je leta 1936 dokazal, da tak program ne more obstajati. Dokaz poteka z argumentom protiizjave (dokaz v nasprotju z domnevo) in konstruira protislovje.
Predpostavimo za protislovje, da obstaja program P(F, I), ki pravilno odloči problem ustavljanja (vrne True, če F(I) teče večno, sicer False). Na podlagi P konstruiramo dva pomožna programa Q in R:
def P(F, I): # domnevni program, ki odloči problem ustavljanja # vrne True, če F(I) teče večno; sicer False def Q(F): return P(F, F) def R(F): if Q(F): return # ustavi se else: while True: continue # teče v nedogled Razlaga:
- Q(F) samo pokliče P nad parom (F, F): preveri, ali program F, če mu damo svojo kodo kot vhod, teče v nedogled.
- R(F) uporabi odgovor Q(F): če Q(F) pravi, da F(F) teče v nedogled, se R(F) ustavi; sicer R(F) vstopi v neskončno zanko.
Sedaj preučimo, kaj se zgodi, če R pokličemo sam na sebi, torej R(R). Možni sta le dve možnosti:
- Predpostavimo, da se R(R) ustavi. Po definiciji R pa se R(R) ustavi natanko v primeru, ko Q(R) vrne True (Q pravi, da R(R) teče v nedogled). Torej dobimo: če se R(R) ustavi, potem Q(R) pravi, da R(R) teče v nedogled — to je protislovje.
- Predpostavimo, da R(R) teče v nedogled. Po definiciji R se to zgodi natanko tedaj, ko Q(R) vrne False (Q pravi, da R(R) se ne bo vrtel v nedogled). Torej dobimo: če R(R) teče v nedogled, potem Q(R) pravi, da R(R) se ne bo vrtel v nedogled — tudi to je protislovje.
Ne glede na to, katero možnost izberemo, pridemo do protislovja. Edina predpostavka, ki jo uporabljamo pri konstrukciji Q in R, je obstoj domnevnega odločevalca P. Ker je ta predpostavka nezdružljiva z logiko, sledi, da tak program P ne more obstajati. Torej problem ustavljanja ni rešljivi (ni odločen).
Pomembne posledice in dodatne opombe:
- Ta rezultat je splošen — velja tako za modele programov kot tudi za Turingove stroje. Alan Turing je dokaz objavil leta 1936 (Alan Turing).
- Haltingov problem je nerazsodljiv (undecidable): ne obstaja algoritem, ki bi za vse vhodne pare (program, vhod) odločil, ali program ustavi.
- Vendar je problem polodločen (recursively enumerable / semidecidable): obstaja algoritem, ki simulira F(I) in, če F(I) v resnici ustavi, ta algoritem na koncu tudi poroča o tem. Če pa F(I) nikoli ne ustavi, bo taka simulacija prav tako tekla v nedogled in nikoli ne bo dala odgovora. Torej lahko prepoznamo primere, kjer program zagotovo ustavi, ne moremo pa v splošnem prepoznati primerov, kjer ne ustavi.
- Posledice: haltingov problem postavlja temeljne meje avtomatskega preverjanja programov in formalnih dokazov. Ne obstaja univerzalno orodje, ki bi pravilno odločilo vse morebitne lastnosti obnašanja programov. Mnogo nadaljnjih rezultatov (na primer Riceov izrek) razširja neodločenost na številne druge lastnosti programov.
Ta poenostavljena razlaga ohranja bistvo Turingovega dokaza: z diagonalizacijo oziroma s konstrukcijo programa, ki "gleda samega sebe", pridemo do nesmiselne protislovnosti, če bi domnevali, da obstaja univerzalni odločevalec za ustavljanje. Zato tak univerzalni odločevalec ne more obstajati.
Vprašanja in odgovori
V: Kaj je Halting problem?
O: Problem zaustavitve je problem v računalništvu, ki obravnava računalniški program in določa, ali bo program tekel večno ali ne.
V: Kako vemo, ali program rešuje problem zaustavitve?
O: Pravimo, da program "rešuje problem ustavljanja", če lahko pogleda katerikoli drug program in pove, ali bo ta program tekel večno ali ne.
V: Ali lahko dokažemo, da tak program ne obstaja?
O: Da, tako, da pokažemo, da bi se v primeru obstoja takega programa zgodilo nekaj nemogočega. Ta dokaz je leta 1936 našel Alan Turing.
V: Kaj naredi P?
O: P je funkcija, ki ovrednoti drugo funkcijo F (klicano z argumentom I) in vrne true, če teče večno, in false v nasprotnem primeru.
V: Kaj počne Q?
O: Q pogleda drug program in nato odgovori na vprašanje, ali bo izvajanje istega programa na sebi povzročilo neskončno zanko ali ne. To stori tako, da uporabi P za vrednotenje dane funkcije F.
V: Kaj naredi R?
O: R pogleda drug program in vpraša Q za odgovor na ta program. Če Q odgovori "da, če zaženemo ta program in ga prisilimo, da pogleda na kopijo samega sebe, bo tekel večno", se R ustavi; če pa Q odgovori "ne, če zaženemo ta program in ga prisilimo, da pogleda na kopijo samega sebe, ne bo tekel večno", potem R vstopi v neskončno zanko in teče večno.
V: Kaj se zgodi, če prisilimo R, da pogleda samega sebe?
O: Zgodita se lahko dve stvari - ali se R ustavi ali teče v nedogled - vendar sta oba rezultata nemogoča glede na to, kar je bilo dokazano o tem, da programi, kot je P, ne obstajajo, zato je moralo nekje na poti do tega, da je R pogledal samega sebe, iti nekaj narobe.
Iskati