Megállási (Halting) probléma — mi ez és miért megoldhatatlan?
Ismerd meg a megállási (Halting) probléma bizonyítását és miért nincs általános megoldás — egyszerű, érthető magyarázat programozóknak és érdeklődőknek.
A megállási (Halting) probléma a számítástechnika és az elméleti számítógép-tudomány egyik alapvető kérdése. Röviden: adott egy program és egy bemenet — meg tudjuk-e határozni, hogy a program a megadott bemenettel egyszeri futás után leáll-e (vagyis véges sok lépés után befejeződik), vagy örökké fut?
Konkrét példa
Például a következő program:
while True: continue;
örökké fut, míg ez:
while False: continue;
nagyon gyorsan befejeződik. A megállási probléma azt kérdezi, hogy van-e általános algoritmus, amely tetszőleges programra és tetszőleges bemenetre meg tudja mondani, hogy az adott futás leáll-e vagy sem.
A bizonyítás vázlata (ellentmondásos bizonyítás)
Kiderül, hogy nem létezik olyan általános algoritmus (program), amely minden program és bemenet esetén helyesen eldönti a megállást. Ezt Alan Turing bizonyította 1936-ban (Alan Turing), és a bizonyításnak több változata ismert; az egyik legegyszerűbb változat diagonális ellentmondáson alapul. A bizonyítás röviden:
- Tegyük fel ellentmondásra, hogy létezik egy P nevű program (vagy eljárás), amely dönteni tudja a megállási problémát: P(F, I) visszaadja True-t, ha a F program I bemenettel örökké fut, és False-t, ha a F(I) megszakad (az eredeti szöveg ide-oda fordította a logikát; fontos, hogy P megmondja: megáll-e vagy sem).
- Ebből definiáljuk Q-t: Q(F) meghívja P-et úgy, hogy ugyanazt a programot adja meg bemenetként is — tehát Q(F) = P(F, F). Q tehát megkérdi: „ha ezt a programot magával futtatjuk, örökké fog-e futni?”
- Ezután definiálunk egy R nevű programot, amely F-re a következőt csinálja: ha Q(F) azt mondja, hogy F(F) örökké fut, akkor R leáll; ha Q(F) szerint F(F) megáll, akkor R örökké fut (például végtelen ciklusba lép). Pseudokódban:
def Q(F):
return P(F, F)
def R(F):
if Q(F):
return # leáll
else:
while True: continue # örökké fut
Most vizsgáljuk meg, mi történik, ha R-t saját magával futtatjuk, azaz R(R)-t. Két eset lehetséges:
- Ha R(R) megszakad (nem fut örökké), akkor a definíció szerint Q(R) igazat mondott arról, hogy R(R) örökké fut — de ez ellentmondás, mert feltételeztük, hogy R(R) megáll.
- Ha R(R) örökké fut, akkor Q(R) hamisat mondott (vagyis azt, hogy R(R) nem fut örökké), de R(R) mégis örökké fut — ez is ellentmondás.
Minden eset ellentmondáshoz vezet, tehát a kiinduló feltételezés (hogy létezik ilyen P) hibás. Következés: nincs általános program, amely megoldja a megállási problémát minden lehetséges programra és bemenetre.
Formálisabb nézet és kiegészítő megjegyzések
- A megállási probléma eldönthetetlen: nincs olyan algoritmus, amely minden bemenetre helyes yes/no választ adna a „ez a program megáll-e ezen a bemeneten?” kérdésre.
- Tisztázás — részleges eldönthetőség: a megállási probléma azonban részben eldönthető (rekurzívan felsorolható, angolul: r.e. / recursively enumerable). Van ugyanis egyszerű „szimulációs” eljárás: párhuzamosan (vagy sorban, egy időosztással) végrehajtjuk a vizsgálandó program egyre több lépését; ha a program tényleg megáll, a szimuláció előbb-utóbb észleli ezt és bejelenti. Ezért van algoritmus, amely ha a program megáll, akkor ezt egyszer megtudja és leáll „igen”-nel; de ha a program örökké fut, a szimuláció soha nem fog „nem”-nel válaszolni (csak végtelen ideig fut). Tehát megállás felismerhető, de nem-megállás általánosan nem.
- Következmények: a megállási probléma bizonyítja, hogy vannak olyan, a programok viselkedésére vonatkozó tulajdonságok, amelyeket nem lehet algoritmikusan dönteni. Ebből általánosabb állítások következnek (pl. Rice-tétel): bármely nemtriviális, programkód által meghatározott tulajdonság eldöntése általában visszavezethető a megállási problémára, így eldönthetetlen.
- Gyakorlati hatás: a bizonyítás elméleti, de fontos gyakorlati következményei vannak: nincs univerzális, minden esetben pontos terminációs elemző, és a programellenőrző eszközök ezért heurisztikákat, közelítéseket és felső/korlátozott elemzési módszereket használnak. Sok feladatban (statikus analízis, biztosítási ellenőrzés) csak konzervatív (túl- vagy alábecsülő) megoldásokat kaphatunk.
- Kapcsolat más eredményekkel: a megállási probléma eldönthetetlensége összhangban van Gödel összefüggő megjegyzéseivel az axiomatikus rendszerek korlátairól; továbbá a Church–Turing-elv szerint a Turing-gépek által megfogalmazott problémaazonosság általános formában fogalmazza meg a számíthatóság határait.
Rövid történeti megjegyzés
Ezt az alapvető eldönthetetlenségi eredményt Alan Turing mutatta be 1936-ban, amikor bevezette a ma Turing-gépként ismert elméleti számítógép-modellt és megmutatta, hogy léteznek olyan problémák, amelyeket semmilyen algoritmus nem tud teljes általánossággal megoldani.
Összefoglalva: a megállási probléma megmutatja a számítás elméleti korlátait — nincs univerzális „megállási-orákulum”, amely minden program és bemenet esetén megmondaná a helyes választ — ugyanakkor léteznek gyakorlati eszközök és technikák, amelyek egyes esetekben hasznos és gyakran elegendő információt szolgáltatnak.
Kérdések és válaszok
K: Mi az a Halting probléma?
V: A Halting-probléma egy olyan probléma a számítástechnikában, amely egy számítógépes programot vizsgál, és meghatározza, hogy a program örökké fog-e futni vagy sem.
K: Honnan tudjuk, hogy egy program megoldja-e a megállási problémát?
V: Azt mondjuk, hogy egy program "megoldja a megállási problémát", ha képes bármely más programot megnézni és megmondani, hogy az a másik program örökké fog-e futni vagy sem.
K: Be lehet bizonyítani, hogy ilyen program nem létezik?
V: Igen, ha megmutatjuk, hogy ha létezne ilyen program, akkor valami lehetetlen történne. Ezt a bizonyítást Alan Turing találta meg 1936-ban.
K: Mit csinál P?
V: P egy olyan függvény, amely kiértékel egy másik F függvényt (amelyet I argumentummal hívunk meg), és igazat ad vissza, ha örökké fut, ellenkező esetben pedig hamisat.
K: Mit csinál Q?
V: A Q megvizsgál egy másik programot, majd válaszol arra a kérdésre, hogy ugyanennek a programnak a saját magán való futtatása végtelen ciklushoz vezet-e vagy sem. Ezt úgy teszi, hogy P segítségével kiértékeli a megadott F függvényt.
K: Mit csinál az R?
V: R megnéz egy másik programot, és megkérdezi a Q-t, hogy az adott programra vonatkozó választ adjon. Ha Q azt válaszolja, hogy "igen, ha lefuttatjuk ezt a programot, és rávesszük, hogy nézze meg önmaga másolatát, akkor örökké fog futni", akkor R megáll; ha azonban Q azt válaszolja, hogy "nem, ha lefuttatjuk ezt a programot, és rávesszük, hogy nézze meg önmaga másolatát, akkor R végtelen ciklusba lép, és örökké fog futni".
K: Mi történik, ha R-t rávesszük, hogy nézze meg önmagát?
V: Két dolog történhet - vagy leáll az R, vagy örökké fut - de mindkét eredmény lehetetlen a P-hez hasonló programok nem létezéséről szóló bizonyítékok szerint, tehát valami rosszul sült el valahol az út során, ami ahhoz vezetett, hogy az R-t rávegyük, hogy nézze meg önmagát.
Keres