Peatumisprobleem (inglise keeles halting problem) on arvutiteaduse klassikaline otsustamise probleem. Küsimus on lihtne: kas eksisteerib algoritm, mis suudab võtta mistahes programmi F ja sisendi I ning otsustada täpselt, kas F(I) peatub (st lõpetab töö) või jookseb lõpmatusse tsüklisse? Kui sellist algoritmi oleks, siis ütleksime, et peatumisprobleem on otsustatav (decidable).

Näited lihtsatest programmidest (pseudokood):

while True: continue; # jookseb igavesti

while False: continue; # peatub kohe (ei sisene tsüklisse)

Tõestuse idee (Turingi enda argument)

Oletame vastupidist: et olemas on programm H, mis otsustab peatumisprobleemi. Me võtame tavapärase jaotuse: H(F, I) tagastab true, kui programm F koos sisendiga I peatub, ja false, kui F(I) ei peatu (st jookseb igavesti). See on otsustaja, mis ütleb täpselt, kas antud programm peatub.

Kui meil on selline H, saame ehitada uue programmi R, mis kasutab H-d enda sisendina antud programmi kohta otsustamiseks ja käitub seejärel vastupidiselt H-i ennustusele. Pseudokoodina võime defineerida:

def R(F):
    if H(F, F):
        while True: continue # kui H ütleb, et F(F) peatub, siis R läheb lõpmatusse tsüklisse
    else:
        return # kui H ütleb, et F(F) ei peatu, siis R peatub

Nüüd vaatame, mis juhtub, kui anname R iseendale sisendiks, st vaatleme R(R). On kaks võimalust:

  • Kui H(R, R) ütleb true (st H ennustab: R(R) peatub), siis R vastavalt oma definitsioonile läheb lõpmatusse tsüklisse — st R(R) ei peatu. See on vastuolu H-i ennustusega.
  • Kui H(R, R) ütleb false (st H ennustab: R(R) ei peatu), siis R kohaselt peatub. Jällegi vastuolu H-i ennustusega.

    • Kokkuvõttes põhjustab eeldus, et H eksisteerib, loogilise vastuolu: H peab nii ennustama, et R(R) peatub kui ka mitte-peatub samaaegselt. See näitab, et sellist üldist otsustajat H ei saa olemas olla. Seega peatumisprobleem on otsustamatu (undecidable).

    Mõningad täpsustused ja tagajärjed

    • Tõestusmeetod: tegemist on vastuväite (contradiction) ja diagonaaltehnika kombinatsiooniga: ehitatakse programm, mis käitub vastupidiselt oletatavale otsustajale, kasutades programmi enda koodi kui sisendit (eneseviide).
    • Formaalselt: ei eksisteeri üldist algoritmi H(P, I), mis alati lõpeks ja annaks õige vastuse "jah" täpselt siis, kui programm P sisendil I peatub.
    • Poolotsustatavus (semi-decidability): kuigi peatumisprobleem on otsustamatu, on see poolotsustatav (recursively enumerable): kui programm P(I) tõepoolest peatub, saab seda näidata, käivitades P(I) ja ootades, kuni see peatub. Kuid kui P(I) ei peatu, siis otsa ei näe ja ei saa kindlalt väita, et see ei peatu — pole üldist lõpetavat testi mitte-peatumise tõestamiseks.
    • Mõju: peatumisprobleemi mittevastuvõtmine näitab fundamentaalseid piire, mida arvutid ja algoritmid ei saa ületada. Selle tulemusel tekivad mitu teist mittetõestatavat/otsustamatut probleemi (näiteks paljud programmeerimiskeelte omadusi käsitlevad küsimused), ning on loodud mitmeid teoreetilisi tööriistu (nt Rice'i teoreem), mis võimaldavad näidata teiste probleemide otsustamatust.

    See fundamentaalne tulemus avastati ja vormistati Alan Turingi poolt 1936. aastal, mille järel halting-probleemist on saanud üks arvutiteooria keskseid näiteid piiridest, mida arvutus suuteline on lahendada.