Problem zaustavitve

Iz MaFiRaWiki

Problem zaustavitve se glasi: za dani Turingov stroj T in vhodni podatek p ugotovi, ali se T ustavi, ko ga poženemo na vhodnem podatku p.

Problem je nerešljiv, kar je dokazal Alan Turing. To pomeni, da ne obstaja tak Turingov stroj H, ki bi za vhodni podatek sprejel primerno zakodiran par (T,p) in bi po končnem številu korakov odločil, ali se stroj T ustavi pri vhodnem podatku p.

Dokaz nerešljivosti poteka s protislovjem, osnovna ideja gre takole. Denimo, da bi tak stroj H obstajal. Tedaj bi lahko sestavili stroj S, ki najprej požene H, ki mu kot vhodni podatke poda opis stroja T (se pravi samega sebe). Če H trdi, da se S ustavi, potem S divergira, če pa H trdi, da se S ne ustavi, potem se S ustavi. Torej S v vsakem primeru "prevara" H, kar je v protislovju s predpostavko, da H za vsak stroj pravilno napove, ali se bo ta ustavil.

Primer v Mathematici

Ker je programiranje Turingovih strojev nepraktično, podajmo zgornjo idejo dokaza v Mathematici. Denimo, da bi obstajala funkcija h[t_,p_], ki sprejme funkcijo t in vhodni podatek p ter vrne True, če se t[p] ustavi in False sicer. Tedaj bi definirali

h[t,p]::usage="Funkcija h[t,p] vrne vrednost
    True, če Mathematica vrednost t[p] izračuna in 
    False, če se računanje t[p] ne ustavi."
s[p_] := If [h[s,0], While[True, Print["Divergiram!"]], Print["Koncam."]]

Če je h[s,0] enak True, bi se moral s[0] ustaviti, vendar se ne. Če je h[s,0] enak False, mi moral s[0] divergirati, vendar se ustavi. To je protislovje, zato h ne obstaja.

Osebna orodja