Megállási probléma

A Halting-probléma a számítástechnika egyik problémája. A probléma lényege, hogy egy számítógépes programot vizsgálva kiderítjük, hogy a program örökké fog-e futni vagy sem. Azt mondjuk, hogy egy program "megoldja a megállási problémát", ha képes bármelyik másik programot megnézni, és megmondani, hogy az a másik program örökké fog-e futni vagy sem.

Például egy ilyen program:

while True: continue;

örökké fog cikázni, de a program

while False: continue;

nagyon gyorsan megáll.

Van olyan program, amely megoldja a megállási problémát? Kiderült, hogy nincs. Ezt a tényt úgy bizonyítjuk, hogy megmutatjuk, hogy ha van olyan program, amely megoldja a megállási problémát, akkor valami lehetetlen történik. Egyelőre tehát úgy teszünk, mintha valóban létezne olyan program, amely megoldja a megállási problémát. Itt P egy olyan függvény, amely kiértékeli az F függvényt (amelyet I argumentummal hívunk meg), és igazat ad vissza, ha örökké fut, és hamisat, ha nem.

def P(F, I): ha F(I) örökké fut: return True; else: return False;

P bármelyik programot megnézheti, és megtudhatja, hogy örökké fog-e futni vagy sem. A P segítségével készítünk egy új programot, amelyet Q-nak fogunk hívni. A Q az, hogy megnéz egy másik programot, majd válaszol a következő kérdésre: "Ha lefuttatjuk ezt a programot, és rávesszük, hogy nézze meg önmaga másolatát, örökké fog futni?". El tudjuk készíteni Q-t, mert van P. Csak annyit kell tennünk, hogy megmondjuk Q-nak, hogy hozzon létre egy új programot, amely a régi program, amely önmagát nézi, majd P segítségével kiderítjük, hogy az új program örökké fut-e vagy sem.

def Q(F): return P(F, F);

Most készítünk egy másik programot R. R megnéz egy másik programot, és megkérdezi Q-t, hogy a válaszát a programra adja-e. 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 leáll. Ha Q azt válaszolja, hogy "nem, ha lefuttatjuk ezt a programot, és rávesszük, hogy nézze meg önmaga másolatát, akkor nem fog örökké futni", akkor R végtelen ciklusba lép, és örökké fut.

def R(F): if Q(F): return; //véget ér máskor: while True: continue; //örökké hurkolás

Most megnézzük, mi történik, ha az R-t rávesszük, hogy nézze meg önmaga másolatát. Két dolog történhet: vagy leáll, vagy örökké fut.

Ha az R futtatása és az önmaga másolatának megnézése nem fut örökké, akkor Q azt válaszolta, hogy "igen, ha lefuttatjuk ezt a programot, és rávesszük, hogy nézze meg önmaga másolatát, akkor örökké fog futni". De Q ezt akkor mondta, amikor magát az R-t nézte. Tehát Q valójában azt mondta: "igen, ha lefuttatjuk az R-t, és rávesszük, hogy nézze meg önmaga másolatát, akkor örökké fog futni". Tehát: Ha az R önmaga másolatán futva nem fut örökké, akkor örökké fut. Ez lehetetlen.

Ha az R futtatása és az önmaga másolatának megnézése örökké tart, akkor Q azt válaszolta, hogy "nem, ha lefuttatjuk ezt a programot, és rávesszük, hogy nézze meg önmaga másolatát, akkor nem fog örökké futni". De Q ezt akkor mondta, amikor magát az R-t nézte. Tehát Q valójában azt mondta: "nem, ha lefuttatjuk az R-t, és rávesszük, hogy nézze meg önmaga másolatát, akkor nem fog örökké futni". Tehát: Ha az R önmaga másolatán futva örökké fut, akkor nem fut örökké. Ez szintén lehetetlen.

Bármi is történik, lehetetlen helyzetbe kerülünk. Valamit rosszul csináltunk, és ki kell derítenünk, mi volt az. A legtöbb dolog, amit tettünk, nem volt rossz. Nem mondhatjuk azt, hogy "rossz, ha egy programot ráveszünk, hogy megnézze saját maga másolatát", vagy hogy "rossz, ha megnézzük, mit mondott egy másik program, majd egy ciklusba lépünk, ha az mondott valamit, és megállunk, ha az mondott valamit". Nincs értelme azt mondani, hogy ezeket a dolgokat nem szabad megtennünk. Az egyetlen dolog, amit tettünk, ami úgy tűnik, hogy helytelen lehet, az az, hogy úgy tettünk, mintha egyáltalán létezne egy olyan program, mint P. És mivel ez az egyetlen dolog, ami rossz lehet, és valaminek rossznak kell lennie, ez az. Ez a bizonyíték arra, hogy a P-hez hasonló program nem létezik. Nincs olyan program, amely megoldja a megállási problémát.

Ezt a bizonyítást Alan Turing találta meg 1936-ban.

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.