Stop problemet

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. november 2021; checks kræver 4 redigeringer .

Halting -problemet er et af problemerne i teorien  om algoritmer [1] , som uformelt kan angives som:

Beskrivelsen af ​​proceduren og dens indledende inputdata er givet. Det er påkrævet at bestemme: Vil udførelsen af ​​proceduren med disse data nogensinde ende; eller at proceduren vil køre hele tiden uden at stoppe.

Alan Turing beviste i 1936 , at stopproblemet er uafgørligt på en Turing-maskine . Der er med andre ord ingen generel algoritme til at løse dette problem. [2]

Det stoppende problem er centralt for beregningsbarhedsteorien, fordi det er det første eksempel på et problem, der ikke kan løses algoritmisk.

Med hensyn til funktioner kan problemet let beskrives som følger:

For enhver funktion F(G, start_state), der kan bestemme, om en anden funktion stopper, kan du altid skrive en funktion G(start_state), der, når den overføres til F, vil have det modsatte resultat af udførelse, som F forudsiger.

Til mange andre opgaver[ hvad? ] kan man bevise deres algoritmiske uafgørlighed ved at forsøge at reducere dem til det stoppende problem. Dette gøres i henhold til ordningen "tværtimod": lad der være et bestemt problem, for hvilket det er nødvendigt at fastslå dets uløselighed. Så antager vi, at det er løseligt, og forsøger, ved at bruge dette faktum, at skrive en algoritme til at løse stopproblemet for dette problem. Hvis dette lykkes, så kommer vi til en selvmodsigelse, fordi man ved, at der ikke er nogen algoritme til at løse standsningsproblemet. Det betyder, at antagelsen var forkert, og det oprindelige problem er også uløseligt.

Bevis

Overvej et sæt algoritmer, der tager et naturligt tal som input og også giver et naturligt tal som output. Lad os vælge et Turing-komplet programmeringssprog. Hver algoritme kan skrives som en endelig sekvens af tegn på dette sprog. Lad os bestille mængden (dette er muligt, da det er et sæt af endelige sekvenser af elementer i et endeligt sæt og derfor kan tælles ), og hver algoritme vil modtage sit eget serienummer. Lad os kalde analysatoren en hypotetisk algoritme, der modtager et par naturlige tal som input , og:

Stoppeproblemet kan omformuleres som følger: Findes der en Analyzer?

Sætning. Analysator findes ikke.

Lad os bevise det ved modsigelse. Lad os sige, at analysatoren eksisterer. Lad os skrive Diagonalizer-algoritmen, som tager et tal som input , sender et par argumenter til analysatoren og returnerer resultatet af sit arbejde. Med andre ord stopper Diagonalizer, hvis og kun hvis algoritmen med nummer ikke stopper efter at have modtaget nummeret som input . Lad være  ordenstallet for diagonalisatoren i sættet . Kør Diagonalizer ved at give dette nummer til den . Diagonalisatoren stopper, hvis og kun hvis algoritmen med tallet (det vil sige det selv) ikke stopper, når den modtager et tal som input (som vi har givet til den). Det følger af denne modsigelse, at vores antagelse er forkert: Analysatoren eksisterer ikke, hvilket skulle bevises.

Se også

Noter

  1. ↑ N.K. Vereshchagin, A. Shen Forelæsninger om matematisk logik og teorien om algoritmer. Del 3. Beregnbare funktioner Arkiveret 12. november 2015 på Wayback Machine
  2. ↑ Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem  // Proceedings of the London Mathematical Society - London Mathematical Society , 1937. - Vol. s2-42, Iss. 1. - S. 230-265. — ISSN 0024-6115 ; 1460-244X - doi:10.1112/PLMS/S2-42.1.230 (i denne publikation introducerer Turing definitionen af ​​en Turing-maskine , formulerer hængeproblemet og viser, at det ligesom opløsningsproblemet er uløseligt).

Links