Het stopprobleem:

Het stopprobleem is het probleem van het bepalen, gegeven een beschrijving van een willekeurig computerprogramma en een invoer, of het programma zal eindigen of voor altijd zal blijven draaien. Meer formeel wordt gevraagd:

* Invoer: `` waarbij:

* `P` is een Turing Machine (of een representatie van een computerprogramma voor algemene doeleinden).

* `I` is de invoer voor de Turingmachine `P`.

* Uitvoer:

* "Ja" als de Turingmachine `P` stopt (de uitvoering voltooit) wanneer invoer `I` wordt gegeven.

* "Nee" als de Turingmachine `P` niet stopt (voor altijd blijft herhalen) wanneer invoer `I` wordt gegeven.

Waarom het onbeslisbaar is:

Het stopprobleem is onbeslisbaar, wat betekent dat er *geen* Turingmachine (of algoritme) bestaat die het stopprobleem correct kan oplossen voor *alle* mogelijke invoer ``.

Het bewijs wordt doorgaans gedaan door middel van tegenspraak. Neem aan dat er *een* Turingmachine `H` bestaat die het stopprobleem oplost. `H` neemt `` als invoer en geeft "Ja" als uitvoer als `P` stopt op `I`, en "Nee" als `P` voor altijd doorloopt op `I`.

Vervolgens kunnen we een andere Turing Machine `D` construeren (vaak de "diagonalizer" genoemd) die `H` als subroutine gebruikt:

```

Turingmachine D(P):

1. Voer H(P, P) uit // Voer H uit met P als zowel het programma als de invoer

2. Als H(P, P) "Ja" retourneert (P stopt op ingang P):

Loop dan voor altijd.

3. Als H(P, P) "Nee" retourneert (P loopt eeuwig door op ingang P):

Stop dan.

```

Wat gebeurt er nu als we `D` uitvoeren met zichzelf als invoer:`D(D)`?

* Scenario 1:Stel dat `D(D)` stopt.

- Dit betekent dat `H(D, D)` in stap 1 "Ja" retourneerde (omdat `D` stopt als en slechts als `H(D, D)` zegt dat `D` stopt bij invoer `D`).

- Maar als `H(D, D)` "Ja" retourneert, dan is `D` ontworpen om voor altijd in een lus te blijven (in stap 2). Dit is in tegenspraak met onze veronderstelling dat 'D(D)' stopt.

* Scenario 2:Stel dat `D(D)` eeuwig doorloopt.

- Dit betekent dat `H(D, D)` in stap 1 "Nee" retourneerde (omdat `D` voor altijd doorloopt als en slechts als `H(D, D)` zegt dat `D` doorloopt op ingang `D`).

- Maar als `H(D, D)` "Nee" retourneert, dan is `D` ontworpen om te stoppen (in stap 3). Dit is in tegenspraak met onze veronderstelling dat `D(D)` eeuwig doorloopt.

Omdat beide scenario's tot een tegenstrijdigheid leiden, moet onze aanvankelijke aanname dat er een Turingmachine 'H' bestaat die het Halting-probleem oplost, onjuist zijn. Daarom is het stopprobleem onbeslisbaar.

In eenvoudiger bewoordingen: Je kunt geen programma schrijven dat altijd op betrouwbare wijze kan voorspellen of een ander programma uiteindelijk zal stoppen of voor altijd zal blijven draaien.

Betekenis:

De onbeslisbaarheid van het Halting-probleem heeft diepgaande gevolgen voor de informatica. Het laat zien dat er fundamentele grenzen zijn aan wat computers kunnen berekenen. Het dient ook als basis voor het bewijzen van de onbeslisbaarheid van veel andere problemen. Als je kunt aantonen dat het oplossen van een ander probleem je ook het Halting Probleem zou kunnen oplossen, dan moet dat andere probleem ook onbeslisbaar zijn.