Non capisco il problema di interruzione

Question

Non capisco il problema di interruzione

#1 da (5 voti)
#2 da (2 voti)
#3 da (2 voti)
#4 da (2 voti)

3

Ho appena trovato una risposta ad un'altra domanda che fa riferimento al problema di interruzione. Inizia con questo frammento:

def halts( code_block ):
    # Some magical code

def whistler():
    while halts(whistler): 
        sys.whistle( 1 )

e poi spiega come la routine halts non può essere definita correttamente perché essenzialmente equivale a essere logicamente equivalente a "questa frase è falsa". A parte la sintassi in stile Python, questa è fondamentalmente la spiegazione standard del problema dell'arresto e non ho mai capito il concetto. Ogni volta che guardo a quel tipo di esempio, penso "ma perché mai nel mondo qualcuno dovrebbe affrontare il problema in questo modo?"

Se volessi determinare una proprietà difficile di un pezzo di codice, come rispondere alla domanda se si fermasse o meno, non avrei mai inserito l'analisi nel codice da analizzare! Prima di tutto, ciò porta a contraddizioni come questo esempio e, in secondo luogo, l'aggiunta del codice di analisi modifica la natura della cosa analizzata. Cercherò quasi certamente di cercare la risposta alla domanda con strumenti esterni, non interni.

Quindi sì, capisco che non c'è modo di scrivere un'implementazione corretta di halts nell'esempio sopra. Ma limitiamoci unicamente al regno del codice che in realtà può essere scritto correttamente, anziché ipotetici. Qual è un esempio di codice che può essere effettivamente scritto ed eseguito, per il quale è impossibile determinare con un'analisi esterna se il codice finirà in un ciclo infinito o se terminerà?

theory

posta Mason Wheeler 07.06.2011 - 02:14

fonte

4 risposte

Leggi altre domande sui tag theory

Lo schema e la programmazione funzionale sono "Struttura e interpretazione dei programmi per computer" come la programmazione di Prolog e logica è a quale libro? [chiuso] Linux è una necessità per l'apprendimento della rete?

score 5 · Answer 1

Every time I look at that type of example, I think "but why in the world would anyone approach the problem in that way in the first place?"

If I wanted to determine a difficult property of a piece of code, such as answering the question of whether or not it halts, there's no way I would put the analysis inside the code to be analyzed!

Il trucco qui è che questa è una prova per contraddizione: supponiamo A, dimostri che implicherebbe un paradosso, concludi che l'ipotesi era sbagliata.

Quindi l'idea non è che noi "avremmo affrontato il problema in questo modo" o che noi "avremmo messo l'analisi all'interno del codice da analizzare" . L'idea è piuttosto: supponiamo che qualcuno abbia inventato un programma e abbia detto "Guarda, ho scritto un programma che dice se un determinato programma si fermerà o meno". "Oh davvero? Fammi vedere cosa succede se lo collego a se stesso?" Kaboom!

Non c'è bisogno di prendere effettivamente un esempio esistente: questo dimostra già che non esiste un modo in cui un programma possa esistere.

In una nota a margine, ciò non significa che non possiamo provare a scrivere una tale funzione halts . Significa semplicemente che è impossibile scrivere una funzione halts che funzioni per qualsiasi programma .

score 2 · Answer 2

If I wanted to determine a difficult property of a piece of code, such as answering the question of whether or not it halts, there's no way I would put the analysis inside the code to be analyzed! [...] I would almost certainly go about looking for the answer to the question with external tools, not internal ones.

Se il problema dell'arresto di Turing è davvero analogo ai teoremi di incompletezza di Gödel ... allora penso che quello che ti sta veramente dicendo è che non puoi mai risolvere il problema senza andando verso quel "livello" esterno di significato o rappresentazione.

Quindi non puoi creare un analizzatore che funzioni su se stesso, puoi solo fare un meta-analizzatore e un meta-meta-analizzatore per questo, e un meta-meta-analizzatore per quello, ecc. (E tu non riesco a fare analoghi reciproci.)

Ecco perché il "nidificazione" è parte del problema.

score 2 · Answer 3

What's an example of code that can actually be written and executed, for which it is impossible to determine by external analysis whether the code will end up in an infinite loop or whether it will terminate?

La congettura di Collatz, a volte chiamata il problema di Syracuse. link

Semplice e indecidibile.

Hai bisogno di più? Ecco una grande lista di problemi per cui potresti scrivere algoritmi potenzialmente corretti. Tuttavia, senza una prova che il tuo algoritmo termina, non lo sai mai sapere se è corretto.

link

score 2 · Answer 4

Stai affermando la risposta alla tua domanda senza rendertene conto.

So yes, I understand that there's no way to write a correct implementation of halts in the example above. But let's restrict ourselves solely to the realm of code that actually can be written correctly, instead of hypotheticals.

Questa è l'essenza del problema dell'arresto. Non c'è modo di scrivere la funzione halts . Non c'è #some magical code . Non può esistere. La prova del problema di interruzione è una restrizione sul regno del codice che può essere scritto.

What's an example of code that can actually be written and executed, for which it is impossible to determine by external analysis whether the code will end up in an infinite loop or whether it will terminate?

Questa è un'altra importante distinzione da fare. Il problema dell'arresto dice che non è possibile scrivere un programma che determina se il programma qualsiasi si fermerà.

È possibile scrivere un programma che determina se un programma particolare si interrompe.