Il problema di arresto:
Il problema di arresto è il problema della determinazione, data la descrizione di un programma arbitrario per computer e un input, se il programma finirà in esecuzione o continuerà a funzionare per sempre. Più formalmente, chiede:
* Input: `
* `P` è una macchina Turing (o una rappresentazione di qualsiasi programma per computer per uso generale).
* `I` è l'input per la macchina Turing` P`.
* Output:
* "Sì" se la macchina Turing `p` si interrompe (termina l'esecuzione) quando viene dato l'input` io`.
* "No" se la macchina Turing `p` non si ferma (loop per sempre) quando viene data input` io`.
Perché è indecidibile:
Il problema di arresto è indecidibile, il che significa che esiste * no * Turing Machine (o algoritmo) che può risolvere correttamente il problema di arresto per * tutti * possibili input `
La prova viene in genere fatta per contraddizione. Supponiamo che ci sia * una macchina Turing `h` che risolve il problema di arresto. `H` prende`
Quindi, possiamo costruire un'altra macchina Turing `d` (spesso chiamato" diagonalizer ") che utilizza` h` come subroutine:
`` `
Turing Machine D (P):
1. Esegui H (P, P) // Esegui H con P come programma e input
2. Se H (P, P) restituisce "Sì" (P si interrompe sull'ingresso P):
Quindi loop per sempre.
3. Se H (P, P) restituisce "No" (P loop per sempre sull'ingresso P):
Quindi fermarsi.
`` `
Ora, cosa succede quando eseguiamo `d` con se stesso come input:` d (d) `?
* Scenario 1:Supponiamo `d (d)` Halts.
- Ciò significa che nel passaggio 1, `h (d, d)` restituito "sì" (perché `d` si ferma se e solo se` h (d, d) `dice che` d` si ferme sull'ingresso `d`).
- ma se `h (d, d)` restituiva "sì", allora `d` è stato progettato per lottare per sempre (nel passaggio 2). Ciò contraddice la nostra ipotesi che `d (d)` si fermi.
* Scenario 2:Supponi `d (d)` loop per sempre.
- Ciò significa che nel passaggio 1, `h (d, d)` restituito "no" (perché `d` loop per sempre se e solo se` h (d, d) `dice che` d` loops on input `d`).
- ma se `h (d, d)` restituiva "no", allora `d` è stato progettato per fermarsi (al passaggio 3). Ciò contraddice la nostra ipotesi che `d (d)` loop per sempre.
Poiché entrambi gli scenari portano a una contraddizione, la nostra ipotesi iniziale che esiste una macchina Turing `H` che risolve il problema di arresto deve essere falso. Pertanto, il problema di arresto è indecidibile.
in termini più semplici: Non puoi scrivere un programma che può sempre prevedere in modo affidabile se un altro programma alla fine si fermerà o funzionerà per sempre.
Significato:
L'indecidabilità del problema di arresto ha profonde implicazioni per l'informatica. Mostra che ci sono limiti fondamentali a ciò che i computer possono calcolare. Serve anche come base per dimostrare l'indecidabilità di molti altri problemi. Se riesci a dimostrare che risolvere un altro problema ti consentirebbe di risolvere il problema di arresto, allora anche quell'altro problema deve essere indecidibile.
Informazioni correlate
Programmazione © www.354353.com