Stopprobleem

Het stopzettingsprobleem is een probleem in de computerwetenschap. Het probleem is het kijken naar een computerprogramma en uitzoeken of het programma voor altijd gaat draaien of niet. We zeggen dat een programma "het stopprobleem oplost" als het naar een ander programma kan kijken en kan vertellen of dat andere programma voor altijd zal draaien of niet.

Bijvoorbeeld, een programma als dit:

terwijl True: doorgaan;

zal voor eeuwig blijven, maar het programma...

terwijl False: doorgaan;

stopt heel snel.

Is er een programma dat het stopzettingsprobleem oplost? Het blijkt dat die er niet is. We bewijzen dit door te laten zien dat als er een programma is dat het stopprobleem oplost, er iets onmogelijks gebeurt. Voorlopig doen we dus alsof er echt een programma is dat het stopprobleem oplost. Hier is P een functie die functie F (aangeroepen met argument I) zal evalueren en waar zal terugkomen als het voor altijd loopt en anders vals is.

def P(F, I): als F(I) voor eeuwig loopt: teruggeven Waar; anders: teruggeven Vals;

P kan naar elk programma kijken en uitzoeken of het voor altijd zal lopen of niet. We gebruiken P om een nieuw programma te maken dat we Q zullen noemen. Wat Q wel doet is naar een ander programma kijken en dan de volgende vraag beantwoorden: "Als we dit programma draaien en het naar een kopie van zichzelf laten kijken, zal het dan voor altijd draaien?" We kunnen Q maken omdat we P hebben. Het enige wat we hoeven te doen is Q te vertellen dat hij een nieuw programma moet maken dat het oude programma naar zichzelf laat kijken, en dan P te gebruiken om uit te vinden of het nieuwe programma voor eeuwig draait of niet.

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

Nu maken we een ander programma R. R kijkt naar een ander programma en vraagt Q naar zijn antwoord op dat programma. Als Q antwoordt "ja, als we dit programma draaien en het naar een kopie van zichzelf laten kijken zal het voor altijd draaien", dan stopt R. Als Q antwoordt "nee, als we dit programma draaien en het naar een kopie van zichzelf laten kijken zal het niet eeuwig draaien", dan komt R in een oneindige lus terecht en draait het voor eeuwig.

def R(F): als Q(F): terugkeren; //termineren anders: terwijl True: doorgaan; //loop voor altijd

Nu kijken we wat er gebeurt als we R naar een kopie van zichzelf laten kijken. Er kunnen twee dingen gebeuren: het zal of stoppen of voor altijd blijven lopen.

Als het draaien van R en het laten kijken naar een kopie van zichzelf niet voor eeuwig draait, dan antwoordde Q "ja, als we dit programma draaien en het laten kijken naar een kopie van zichzelf zal het voor eeuwig draaien". Maar Q zei dit toen hij naar R zelf keek. Dus wat Q eigenlijk zei is: "ja, als we R draaien en het naar een kopie van zichzelf laten kijken zal het voor altijd draaien". Dus: Als R die op een kopie van zichzelf draait niet voor eeuwig draait, dan draait hij wel voor eeuwig. Dit is onmogelijk.

Als het draaien van R en het laten kijken naar een kopie van zichzelf voor altijd loopt, dan antwoordde Q "nee, als we dit programma draaien en het laten kijken naar een kopie van zichzelf zal het niet voor altijd lopen". Maar Q zei dit toen hij naar R zelf keek. Dus wat Q eigenlijk zei is: "nee, als we R draaien en het naar een kopie van zichzelf laten kijken zal het niet eeuwig blijven draaien". Dus: Als R op een kopie van zichzelf loopt, dan loopt het niet voor altijd. Dit is ook onmogelijk.

Wat er ook gebeurt, we krijgen een onmogelijke situatie. We hebben iets verkeerds gedaan, en we moeten uitzoeken wat het was. De meeste dingen die we deden waren niet verkeerd. We kunnen niet zeggen "een programma te laten kijken naar een kopie van zichzelf is verkeerd", of "kijken naar wat een ander programma zei en dan in een lus gaan als het een ding zei, en stoppen als het een ander ding zei" is verkeerd. Het heeft geen zin om te zeggen dat we die dingen niet mogen doen. Het enige wat we gedaan hebben dat er verkeerd uitziet is dat we doen alsof er een programma als P bestaat. En aangezien dit het enige is dat fout kan zijn, en er moet iets mis zijn, is dit het. Dit is het bewijs dat een programma als P niet bestaat. Er is geen programma dat het stopprobleem oplost.

Dit bewijs werd door Alan Turing in 1936 gevonden.

Vragen en antwoorden

V: Wat is het Halting-probleem?

A: Het Halting-probleem is een probleem in de informatica waarbij gekeken wordt naar een computerprogramma en bepaald wordt of het programma eeuwig zal lopen of niet.

V: Hoe weten wij of een programma het haltingprobleem oplost?

A: Wij zeggen dat een programma "het stopprobleem oplost" als het naar een willekeurig ander programma kan kijken en kan zeggen of dat andere programma voor eeuwig zal draaien of niet.

Vraag: Is er een manier om te bewijzen dat zo'n programma niet bestaat?

A: Ja, door aan te tonen dat als zo'n programma zou bestaan, er iets onmogelijks zou gebeuren. Dit bewijs is gevonden door Alan Turing in 1936.

V: Wat doet P?

A: P is een functie die een andere functie F (aangeroepen met argument I) evalueert en waar teruggeeft als hij eeuwig doorloopt en anders onwaar.

V: Wat doet Q?

Antwoord: Q bekijkt een ander programma en beantwoordt dan de vraag of het uitvoeren van ditzelfde programma op zichzelf al dan niet zal resulteren in een oneindige lus. Het doet dit door met P een evaluatie te maken van de gegeven functie F.

V: Wat doet R?

A: R kijkt naar een ander programma en vraagt Q om zijn antwoord op dat specifieke programma. Als Q antwoordt "ja, als we dit programma uitvoeren en het naar een kopie van zichzelf laten kijken, zal het voor eeuwig draaien", dan stopt R; als Q echter antwoordt "nee, als we dit programma uitvoeren en het naar een kopie van zichzelf laten kijken, zal het niet voor eeuwig draaien", dan gaat R een oneindige lus in en draait voor eeuwig.

V: Wat gebeurt er als u R naar zichzelf laat kijken?

Antwoord: Er kunnen twee dingen gebeuren - of R stopt of loopt voor altijd door - maar beide resultaten zijn onmogelijk volgens wat bewezen is over programma's als P die niet bestaan, dus moet er ergens iets mis zijn gegaan in de aanloop naar het laten kijken van R naar zichzelf.