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.