Халтинг проблем

У теорији израчунљивости, халтинг проблем или проблем заустављања је проблем одлучивања који се може изразити на следећи начин: Ако је дат опис рачунарског програма, одредити да ли ће програм завршити са извршавањем или ће наставити да се извршава до у бесконачност. Ово је еквивалентно проблему одлучивања, за дати програм и улаз, да ли ће програм икада стати за тај улаз, или ће се извршавати бесконачно дуго.

Алан Тјуринг је 1936. године доказао да општи алгоритам за решавање халтинг проблема за све могуће парове програм-улаз не може да постоји. Стога се каже да је халтинг проблем неодлучив на Тјуринговим машинама.

Б. Џек Коупланд (2004) приписује сам израз халтинг проблем Мартину Дејвису.

Формални исказ

Халтинг проблем је проблем одлучивања о својствима рачунарских програма на фиксираном Тјуринг-комплетном моделу израчунавања. Проблем се састоји у одређивању да ли ће дати програм за дати улаз икад завршити са израчунавањем. У овом апстрактном оквиру не постоје ограничења која се тичу ресурса то јест меморије или времена извршавања програма; он може да се извршава произвољно дуго и да искористи произвољну количину меморије пре него што се заустави. Питање је само да ли ће програм икада завршити са израчунавањем за дати улаз.

На пример, псеудокодом, исписан програм

while True: continue

се не зауставља већ се извршава заувек у бесконачној петљи. Са друге стране програм

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

се зауставља врло брзо.

Халтинг проблем је чувен јер се ради о једном од првих проблема за које је доказано да су алгоритамски неодлучиви. То значи да не постоји алгоритам који може да се примени на било који произвољни програм и улаз, такав да одређује да ли се програм зауставља за тај улаз.

Представљање халтинг проблема као скупа

Конвенционално представљање проблема одлучивања је у виду скупова објеката који поседују дато својство. Халтинг скуп

програм i се зауставља за улаз x}

представља халтинг проблем.

Овај скуп је рекурзивно пребројив, што значи да постоји израчунљива функција која исписује све парове (i, x) које овај скуп садржи. Међутим, комплемент овог скупа није рекурзивно пребројив.

Постоје бројне еквивалентне формулације халтинг проблема; сваки скуп чији је Тјурингов степен једнак степену халтинг проблема представља такву формулацију. Примери оваквих скупова су:

• { i | програм i се зауставља за улаз 0 }
• { i | постоји улаз x такав да се програм i зауставља за улаз x }.

Види још

• Машина која увек стаје

Спољашње везе

• Scooping the loop snooper - поетски доказ неодлучивости халтинг проблема.