Sluta problem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 november 2021; kontroller kräver 4 redigeringar .

Halting -problemet är ett av problemen i teorin  om algoritmer [1] , som informellt kan uttryckas som:

Beskrivningen av proceduren och dess initiala indata ges. Det krävs för att fastställa: kommer utförandet av proceduren med dessa data någonsin att sluta; eller att proceduren kommer att köras hela tiden utan att stanna.

Alan Turing bevisade 1936 att stoppproblemet är obestämbart på en Turing-maskin . Det finns med andra ord ingen generell algoritm för att lösa detta problem. [2]

Det stoppande problemet är centralt för beräkningsbarhetsteorin eftersom det är det första exemplet på ett problem som inte kan lösas algoritmiskt.

När det gäller funktioner kan problemet enkelt beskrivas på följande sätt:

För varje funktion F(G, start_state) som kan avgöra om en annan funktion stoppar, kan du alltid skriva en funktion G(start_state) som, när den skickas till F, kommer att få motsatt resultat av exekvering som F förutsäger.

För många andra uppgifter[ vad? ] kan man bevisa deras algoritmiska obestämbarhet genom att försöka reducera dem till stoppproblemet. Detta görs enligt schemat "tvärtom": låt det finnas ett visst problem för vilket det krävs för att fastställa dess olösbarhet. Sedan antar vi att det är lösbart och försöker, med hjälp av detta faktum, skriva en algoritm för att lösa stoppproblemet för detta problem. Om detta lyckas kommer vi att komma till en motsägelse, eftersom det är känt att det inte finns någon algoritm för att lösa stoppproblemet. Det betyder att antagandet var fel och att det ursprungliga problemet också är olösligt.

Bevis

Betrakta en uppsättning algoritmer som tar ett naturligt tal som indata och även ger ett naturligt tal som utdata. Låt oss välja något Turing-komplett programmeringsspråk. Varje algoritm kan skrivas som en ändlig sekvens av tecken på detta språk. Låt oss beställa mängden (detta är möjligt, eftersom det är en uppsättning ändliga sekvenser av element i en ändlig mängd och därför räknebara ), och varje algoritm kommer att få sitt eget serienummer. Låt oss kalla analysatorn för en hypotetisk algoritm som tar emot ett par naturliga tal som indata och:

Stoppproblemet kan omformuleras enligt följande: Finns det en analysator?

Sats. Analysatorn finns inte.

Låt oss bevisa det genom motsägelse. Låt oss säga att analysatorn finns. Låt oss skriva Diagonalizer-algoritmen, som tar ett tal som indata , skickar ett par argument till analysatorn och returnerar resultatet av sitt arbete. Med andra ord, Diagonalizern stannar om och endast om algoritmen med nummer inte stannar efter att ha tagit emot numret som inmatning . Låt vara  ordningsnumret för diagonalisatorn i uppsättningen . Kör Diagonalizer genom att skicka detta nummer till den . Diagonalisatorn kommer att stanna om och bara om algoritmen med numret (det vill säga den själv) inte stannar när den tar emot ett nummer som indata (som vi skickade till den). Det följer av denna motsägelse att vårt antagande är felaktigt: Analysatorn existerar inte, vilket skulle bevisas.

Se även

Anteckningar

  1. ↑ N.K. Vereshchagin, A. Shen Föreläsningar om matematisk logik och teorin om algoritmer. Del 3. Beräkningsbara funktioner Arkiverad 12 november 2015 på Wayback Machine
  2. ↑ Turing A. On Computable Numbers, with a 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 denna publikation introducerar Turing definitionen av en Turing-maskin , formulerar hängproblemet och visar att det, liksom upplösningsproblemet , är olösligt).

Länkar