`som inmatning och utgångar" ja "om" p "stoppar på" i "och" nej "om" p "slingor för alltid på" i ".
Sedan kan vi konstruera en annan Turing Machine `D" (ofta kallad "diagonalizer") som använder `H` som en subroutine:
`` `
Turing Machine D (P):
1. Kör H (P, P) // Kör H med P som både programmet och ingången
2. Om h (p, p) returnerar "ja" (p stoppar på ingång p):
Sedan slinga för alltid.
3. Om h (p, p) returnerar "nej" (p slingor för evigt på input p):
Sedan stopp.
`` `
Vad händer nu när vi kör `d` med sig själv som input:` d (d) `?
* Scenario 1:Anta `d (d)` stopp.
- Detta innebär att i steg 1, `h (d, d)` returnerad "ja" (eftersom `d` stannar om och bara om` h (d, d) säger att `d` stannar på input 'd`).
- men om `h (d, d)` returnerade "ja", var `d` utformad för att slinga för evigt (i steg 2). Detta strider mot vårt antagande att `d (d)` stoppar.
* Scenario 2:Anta `d (d)` slingor för alltid.
- Detta innebär att i steg 1, `h (d, d)" returnerade "nej" (eftersom `d` slingor för alltid om och bara om` h (d, d) `säger att` d` slingor på input 'd`).
- men om `h (d, d)` returnerade "nej", var `d` utformad för att stoppa (i steg 3). Detta strider mot vårt antagande att `d (d)` slingor för alltid.
Eftersom båda scenarierna leder till en motsägelse måste vårt första antagande att det finns en Turing -maskin "H" som löser stoppproblemet vara falskt. Därför är stoppproblemet obeslutbart.
i enklare termer: Du kan inte skriva ett program som alltid kan förutsäga om ett annat program så småningom kommer att stoppa eller köra för alltid.
Betydelse:
Olyckan hos stoppproblemet har djupa konsekvenser för datavetenskap. Det visar att det finns grundläggande gränser för vad datorer kan beräkna. Det fungerar också som en grund för att bevisa obeslutbarhet av många andra problem. Om du kan visa att att lösa ett annat problem skulle göra det möjligt för dig att lösa stoppproblemet, måste det andra problemet också vara obeslutbart.
