Stopprobleem


Het stopprobleem, ook bekend als het 'halting problem', is het beslissingsprobleem uit de wiskunde en informatica, om te bepalen of een algoritme bij een eindige invoer in een eindig aantal stappen eindigt of dat het eindeloos blijft doorgaan. Het is een bekend voorbeeld van een wiskundig probleem dat onbeslisbaar is, en een van de eerste als dusdanig herkende problemen. Dit werd bewezen door Alan Turing in 1936.

Definitie


Het stopprobleem is informeel gedefinieerd het volgende beslissingsprobleem:

Gegeven een programma \({\displaystyle M}\) en een invoerwaarde \({\displaystyle x}\), bepaal of \({\displaystyle M}\) met invoer \({\displaystyle x}\) na een eindig aantal stappen wel of niet stopt.

Om het stopprobleem formeel te definiëren, moeten we afspreken wat we onder het begrip programma verstaan. Oorspronkelijk werd het stopprobleem voor turingmachines geformuleerd, maar analoog kan het ook voor andere turingvolledige formalismes worden gedefinieerd.

De invoer van een turingmachine bestaat uit een rij symbolen, een tekenreeks. Om turingmachines als invoer voor andere turingmachines op te kunnen vatten, moeten we ze eerst coderen, of programmeren. We kunnen bijvoorbeeld alle Turingmachines op een rij zetten, en dan het volgnummer in deze rij als de code voor de turingmachine gebruiken. Als \({\displaystyle w}\) een code voor een turingmachine is, dan schrijven we \({\displaystyle M_{w}}\) voor de turingmachine die door \({\displaystyle w}\) gecodeerd wordt. Bovendien schrijven we \({\displaystyle \langle x,y\rangle }\) voor de code van het paar \({\displaystyle (x,y)}\). Het stopprobleem kan nu formeel als volgt worden gedefinieerd:

\({\displaystyle h(\langle w,x\rangle )={\begin{cases}1&{\text{als turingmachine }}M_{w}{\text{ stopt in een eindig aantal stappen met }}x{\text{ als invoer}}\\0&{\text{anders}}\end{cases}}}\)

Beslissingsproblemen worden ook vaak gedefinieerd als de verzameling van positieve invoerwaardes, dus alternatief luidt de definitie van het stopprobleem:

\({\displaystyle H=\{\langle w,x\rangle \mid {\text{Turingmachine }}M_{w}{\text{ stopt in een eindig aantal stappen met }}x{\text{ als invoer}}\}}\)

Onbeslisbaarheid


Alan Turing bewees in 1936 dat het stopprobleem onbeslisbaar is. Dat betekent dat er geen turingmachine bestaat die in alle gevallen correct beslist, of een turingmachine met een bepaalde invoerwaarde in een eindig aantal stappen stopt of niet.


Het was voor zijn bewijs, of beter gezegd voor het geven van een definitie van het algoritme, dat Turing het later beroemd geworden idee van de turingmachine bedacht.

Bronnen











Categorieën: Paradox | Theoretische informatica




Staat van informatie: 25.09.2021 06:16:09 CEST

oorsprong: Wikipedia (Auteurs [Geschiedenis])    Licentie: CC-BY-SA-3.0

Veranderingen: Alle afbeeldingen en de meeste ontwerpelementen die daarmee verband houden, zijn verwijderd. Sommige pictogrammen werden vervangen door FontAwesome-Icons. Sommige sjablonen zijn verwijderd (zoals 'artikel heeft uitbreiding nodig') of toegewezen (zoals 'hatnotes'). CSS-klassen zijn verwijderd of geharmoniseerd.
Specifieke Wikipedia-links die niet naar een artikel of categorie leiden (zoals 'Redlinks', 'links naar de bewerkpagina', 'links naar portals') zijn verwijderd. Elke externe link heeft een extra FontAwesome-Icon. Naast enkele kleine wijzigingen in het ontwerp, werden mediacontainer, kaarten, navigatiedozen, gesproken versies en Geo-microformats verwijderd.

Belangrijke opmerking Omdat de gegeven inhoud op het gegeven moment automatisch van Wikipedia wordt gehaald, was en is een handmatige verificatie niet mogelijk. Daarom garandeert LinkFang.org niet de juistheid en actualiteit van de verkregen inhoud. Als er informatie is die momenteel verkeerd is of een onjuiste weergave heeft, aarzel dan niet om Neem contact op: E-mail.
Zie ook: Afdruk & Privacy policy.