Halting problem

U teoriji izračunljivosti, halting problem ili problem zaustavljanja je problem odlučivanja koji se može izraziti na sledeći način: Ako je dat opis računarskog programa, odrediti da li će program završiti sa izvršavanjem ili će nastaviti da se izvršava do u beskonačnost. Ovo je ekvivalentno problemu odlučivanja, za dati program i ulaz, da li će program ikada stati za taj ulaz, ili će se izvršavati beskonačno dugo.

Alan Tjuring je 1936. godine dokazao da opšti algoritam za rešavanje halting problema za sve moguće parove program-ulaz ne može da postoji. Stoga se kaže da je halting problem neodlučiv na Tjuringovim mašinama.

B. Džek Koupland (2004) pripisuje sam izraz halting problem Martinu Dejvisu.

Formalni iskaz

Halting problem je problem odlučivanja o svojstvima računarskih programa na fiksiranom Tjuring-kompletnom modelu izračunavanja. Problem se sastoji u određivanju da li će dati program za dati ulaz ikad završiti sa izračunavanjem. U ovom apstraktnom okviru ne postoje ograničenja koja se tiču resursa to jest memorije ili vremena izvršavanja programa; on može da se izvršava proizvoljno dugo i da iskoristi proizvoljnu količinu memorije pre nego što se zaustavi. Pitanje je samo da li će program ikada završiti sa izračunavanjem za dati ulaz.

Na primer, pseudokodom, ispisan program

while True: continue

se ne zaustavlja već se izvršava zauvek u beskonačnoj petlji. Sa druge strane program

print "Здраво свете!"

se zaustavlja vrlo brzo.

Halting problem je čuven jer se radi o jednom od prvih problema za koje je dokazano da su algoritamski neodlučivi. To znači da ne postoji algoritam koji može da se primeni na bilo koji proizvoljni program i ulaz, takav da određuje da li se program zaustavlja za taj ulaz.

Predstavljanje halting problema kao skupa

Konvencionalno predstavljanje problema odlučivanja je u vidu skupova objekata koji poseduju dato svojstvo. Halting skup

program i se zaustavlja za ulaz x}

predstavlja halting problem.

Ovaj skup je rekurzivno prebrojiv, što znači da postoji izračunljiva funkcija koja ispisuje sve parove (i, x) koje ovaj skup sadrži. Međutim, komplement ovog skupa nije rekurzivno prebrojiv.

Postoje brojne ekvivalentne formulacije halting problema; svaki skup čiji je Tjuringov stepen jednak stepenu halting problema predstavlja takvu formulaciju. Primeri ovakvih skupova su:

• { i | program i se zaustavlja za ulaz 0 }
• { i | postoji ulaz x takav da se program i zaustavlja za ulaz x }.

Vidi još

• Mašina koja uvek staje

Spoljašnje veze

• Scooping the loop snooper - poetski dokaz neodlučivosti halting problema.