Stoppproblemreduktionen är ett kraftfullt verktyg för att bevisa att ett givet problem (eller algoritm) är
obeslutbar , vilket betyder att det inte finns någon allmän algoritm som alltid kan avgöra om den givna probleminstansen kan lösas av någon annan algoritm. Det * säger inte * direkt om en algoritm * är * beräkningsbar, utan snarare om bestämning av * en egenskap om * algoritmen är beräkningsbar.
Så här fungerar minskningen:
1. Förstå stoppproblemet:
*Stoppningsproblemet frågar:Med tanke på en algoritm (program) *H *och en ingång *i *för den algoritmen, kommer *H *Hax (slutlig körning) när den körs med ingång *i *?
* Stoppproblemet är obeslutbart . Det finns ingen algoritm, `stopp (h, i)`, som alltid kan återlämna korrekt "sant" om *h *stoppar på *i *, och "falsk" om *h *slingor för alltid.
2. Reduktionstekniken (bevis efter motsägelse):
För att bevisa att ett problem * p * är obeslutbart gör du följande:
1. Antag, för motsägelse, att * p * är avgörande. Detta innebär att vi antar att det finns en algoritm `SOLVEP (InputForp)` som alltid korrekt returnerar lösningen för alla instanser av problem *p *.
2. Konstruera en minskning: Du måste visa hur du använder den hypotetiska `Solvep ()` algoritmen för att lösa stoppproblemet. Med andra ord skapar du en algoritm `stopp (h, i)` som använder `Solvep ()` som en subroutine. Denna algoritm `stoppar (H, i)` bör fungera enligt följande:
`` `
Stoppar (h, i):
1. Förvandla stoppprobleminstansen (h, i) till ett exempel på problem p, låt oss kalla det `inputforp`. Detta är det avgörande steget:du skapar "inputforp" på ett sätt som *lösningen på problem P på denna ingång direkt avslöjar om H stoppar i *. Specifikationerna för hur du gör denna omvandling beror helt på problemet *p *.
2. ResultP =SOLVEP (InputForp) // Ring vår hypotetiska lösare för problem P.
3. Baserat på resultp, bestäm om H stoppar i och returnerar sant eller falskt i enlighet därmed.
`` `
3. Visa att din minskning innebär en lösning på stoppproblemet: Förklara tydligt hur resultatet av `SOLVEP (InputForp)` berättar direkt om algoritm *H *stoppar på ingången *i *.
4. Motstånd: Eftersom stoppproblemet är känt för att vara obeslutbart, och du har visat att en hypotetisk `Solvep` kan användas för att lösa det, har du nått en motsägelse.
5. Slutsats: Därför måste vårt första antagande (att * p * är avgörande) vara falsk. Därför är problem * p * obeslutbart.
Nyckelidéer och utmaningar:
* Transformation är nyckeln: Den svåraste delen är att hitta en omvandling från (h, i) till ett exempel av *p *så att lösningen på *p *direkt avslöjar om *h *stoppar på *i *. Detta kräver smarthet och förståelse för både stoppproblemet och problemet *p *.
* Bevis i motsägelse: Du är inte * direkt * som bevisar att * p * är obeslutbar. Du visar att om * p * * var * avgörande skulle det leda till en omöjlighet (lösa stoppproblemet).
* Generalisering: Målet är att bevisa att det *inte kan *existera en algoritm som löser *p *för *alla möjliga ingångar *. Din reduktion måste vara giltig för alla godtyckliga algoritmer *H *och ingång *i *.
Exempel:Tomhetsproblemet för Turing -maskiner
Tomhetsproblemet för Turing -maskiner frågar:Med tanke på en Turing -maskin *M *, accepteras språket av *m *tomt (dvs. accepterar *m *någon *ingång)? Låt oss visa att detta är obeslutbart.
1. Anta att tomhet är avgörande: Antag att det finns en algoritm `isEmpty (m)` som returnerar `sant 'om språket som accepteras av * m * är tomt och" falsk "annars.
2. reduktion: Vi skapar en algoritm `stopp (h, i)` som använder `isEmpty ()`:
`` `
Stoppar (h, i):
1. // Konstruera en ny Turing Machine M_HI
// - m_hi tar alla ingångar w.
// - m_hi simulerar först H på I.
// - om h stoppar i, accepterar m_hi w.
// - om H inte stoppar på i, så slingrar M_HI för alltid.
M_hi =constructtm (h, i)
2. Resultat =isEmPty (m_hi)
3. Om resultat ==sant:
returnera falsk // h stoppar inte på i
annan:
returnera sant // h stoppar på i
`` `
3. Varför detta fungerar:
*Om *h *stoppar på *i *, kommer `m_hi` att acceptera *varje *ingång` w`. Således är det språk som accepteras av `m_hi 'inte tomt (det är faktiskt σ*, uppsättningen av alla strängar). Därför kommer `isEmpty (m_hi)` att returnera 'falska', och 'stoppar (h, i)' returnerar 'sant'.
*Om *h *inte *stoppar på *i *, kommer `m_hi` att slinga för evigt på *varje *ingång` w`. Således är det språk som accepteras av `m_hi 'tomt. Därför kommer `isEmpty (m_hi)` att återvända 'true', och 'stoppar (h, i)' returnerar 'falsk'.
4. Motstånd: Vi har skapat en algoritm `stopp (h, i)` som använder `isEmpty ()` för att lösa stoppproblemet. Men stoppproblemet är obeslutbart, så detta är en motsägelse.
5. Slutsats: Därför är tomhetsproblemet för Turing -maskiner obeslutbart.
Viktiga anteckningar:
* Reduktionen visar att problemet * p * är * minst lika hårt som * stoppproblemet. Eftersom stoppproblemet är obeslutbart, så är *p *.
* Reduktioner används ofta för att bevisa obeslutbarhet, men de kan också användas för att bevisa NP-kompletitet i samband med beräkningskomplexitet.
* Algoritmen `constructTM (H, i)` I exemplet ovan är en teoretisk konstruktion. I praktiken skulle du faktiskt inte "bygga" en fysisk Turing -maskin. Poängen är att * i princip * Det är möjligt att beskriva en sådan maskin.
Sammanfattningsvis är minskningen av stoppproblem en kraftfull bevisningsteknik som hjälper oss att förstå beräkningsgränserna. Genom att visa att att lösa ett visst problem skulle innebära en lösning på stoppproblemet (som vi vet är omöjligt) kan vi dra slutsatsen att problemet är obeslutbart.
