Problem zaustavljanja
From Wikipedia, the free encyclopedia
U teoriji izračunljivosti, problem zaustavljanja je problem odluke koji se neformalno može iskazati na sljedeći način:
- Za dani opis programa i konačnog ulaza, odluči završuje li program ili se izvršuje unedogled, za dani ulaz.
Alan Turing je 1936. dokazao da općenit algoritam za rješavanje problema zaustavljanja za sve moguće parove programa-ulaza ne može postojati. Kaže se da je problem zaustavljanja neodlučiv nad Turingovim strojevima. (vidi[1] za pripisivanje problema zaustavljanja Turingu.)