Esiste un sottoinsieme di programmi che evita il problema dell'arresto

Il problema non è sull'input (ovviamente, con l'input illimitato, puoi avere tempo di esecuzione illimitato solo per leggere l'input), è sul numero di stati interni.

Quando il numero di stati interni è limitato, teoricamente puoi risolvere il problema di interruzione in tutti i casi (basta emularlo fino a raggiungere l'arresto o la ripetizione di uno stato), quando non lo è, ci sono casi in cui non è 'risolvibile. Ma anche se il numero di stati interni è in pratica limitato, è anche così enorme che i metodi che si basano sulla limitatezza del numero di stati interni sono inutili per provare la cessazione di qualsiasi programma tranne banale.

Esistono modi più pratici per controllare la fine dei programmi. Ad esempio, esprimili in un linguaggio di programmazione che non ha ricorsione né goto e le cui strutture di loop hanno un limite sul numero di iterazioni che deve essere specificato all'entrata del ciclo. (Si noti che il limite non deve essere realmente correlato al numero effettivo di iterazioni, un modo standard per provare la fine di un ciclo è di avere una funzione che si dimostra stia diminuendo rigorosamente da una iterazione all'altra e la condizione di ingresso assicurati sia positivo, potresti mettere la prima valutazione come vincolata).

Prima di tutto, considera cosa succederebbe se avessimo un rilevatore di arresto. Sappiamo dall'argomento diagonale che esiste almeno un programma che farebbe sì che un rivelatore non si fermi o non dia una risposta sbagliata. Ma questo è un programma bizzarro e improbabile.

C'è un altro argomento, tuttavia, che un rivelatore di arresto è impossibile, e questo è l'argomento più intuitivo secondo il quale un rivelatore di arresto sarebbe magico. Supponiamo che tu voglia sapere se l'ultimo teorema di Fermat è vero o falso. Basta scrivere un programma che si arresta se è vero e gira per sempre se è falso, e quindi eseguire il rilevatore di interruzione su di esso. Non esegui esegui il programma , esegui il rilevatore di interruzione sul programma . Un rilevatore di interruzioni ci consentirà di risolvere immediatamente un numero enorme di problemi aperti nella teoria dei numeri semplicemente scrivendo programmi.

Quindi, puoi scrivere un linguaggio di programmazione che è garantito per produrre programmi il cui arresto può essere sempre determinato? Sicuro. Non può avere loop, condizioni e usare arbitrariamente molta memoria. Se sei disposto a vivere senza loop, o senza istruzioni "if", o con una quantità di storage strettamente limitata, allora sicuro, puoi scrivere una lingua la cui fermata è sempre determinabile.

Ti consiglio di leggere Gödel, Escher, Bach . È un libro molto divertente e illuminante che, tra le altre cose, tocca il teorema di incompletezza di Gödel e il problema dell'arresto.

Per rispondere alla tua domanda in poche parole: il problema dell'arresto è decidibile fintanto che il tuo programma non contiene un ciclo while (o una delle sue numerose possibili manifestazioni).

Per ogni programma che lavora su una quantità limitata di memoria (inclusa la memorizzazione di tutti i tipi), il problema dell'arresto può essere risolto; un programma indecidibile è destinato a prendere sempre più memoria in fuga.

Ma anche così, questa intuizione non significa che possa essere usata per problemi del mondo reale, dal momento che un programma di arresto, lavorando su pochi kilobyte di memoria, può richiedere più tempo della durata residua dell'universo per battuta d'arresto.

Rispondere (parzialmente) alla tua domanda "Esiste un sottoinsieme di programmi che evita il problema dell'arresto": sì, infatti c'è. Tuttavia, questo sottoinsieme è incredibilmente inutile (si noti che il sottoinsieme di cui sto parlando è un sottoinsieme ristretto dei programmi che si fermano).

Lo studio della complessità dei problemi per "la maggior parte degli input" è chiamato complessità del caso generico . Si definisce un sottoinsieme dei possibili input, si dimostra che questo sottoinsieme copre "la maggior parte degli input" e fornisce un algoritmo che risolve il problema per questo sottoinsieme.

Ad esempio, il problema dell'arresto è risolvibile in tempo polinomiale per la maggior parte degli input (in effetti, nel tempo lineare, se capisco il documento correttamente).

Tuttavia, questo risultato è piuttosto inutile a causa di tre note a margine: in primo luogo, parliamo di macchine di Turing con un singolo nastro, piuttosto che programmi di computer reali su computer reali. Per quanto ne so, nessuno sa se lo stesso vale per i computer del mondo reale (anche se i computer del mondo reale potrebbero essere in grado di calcolare le stesse funzioni delle macchine di Turing, il numero di programmi consentiti, le loro lunghezze e se potrebbero fermarsi) completamente diverso).

In secondo luogo, devi fare attenzione a cosa significa "molti input". Significa che la probabilità che un programma casuale di "lunghezza" n possa essere controllato da questo algoritmo tende a 1 come n tende all'infinito. In altre parole, se n è abbastanza grande, un algoritmo casuale di lunghezza n può quasi sicuramente essere controllato da questo algoritmo.

Quali programmi possono essere controllati con l'approccio descritto nel documento? In sostanza, tutti i programmi che si arrestano prima di ripetere uno stato (dove 'stato' corrisponde approssimativamente a una riga di codice in un programma).

Anche se quasi tutti i programmi possono essere controllati in questo modo, nessuno dei programmi che possono essere controllati in questo modo sono molto interessanti e di solito non saranno progettati dagli umani, quindi questo non ha alcun valore pratico.

Indica anche che la complessità del caso generico probabilmente non sarà in grado di aiutarci con il problema dell'arresto, poiché quasi tutti i programmi interessanti sono (apparentemente) difficili da controllare. O, in alternativa, in frasi: quasi tutti i programmi non sono interessanti, ma facili da controllare.

C'è, e in effetti ci sono programmi nella vita reale che risolvono il problema di fermare per altri problemi tutto il tempo. Fanno parte del sistema operativo su cui viene eseguito il computer. L'indecidibilità è un'affermazione strana che dice solo che non esiste un programma simile che funzioni per TUTTI gli altri programmi.

Una persona ha affermato correttamente che la prova di arresto sembra essere l'unico programma per il quale non può essere risolto, poiché si ripercuote all'infinito come uno specchio. Questa stessa persona ha anche dichiarato che se ci fosse una macchina ferma, sarebbe stata magica perché ci avrebbe svelato dei problemi di matematica dicendoci in anticipo se l'algoritmo del risolutore si fermasse.

L'assunto in entrambi i casi è che la macchina ferma non viene tracciata perché non vi è alcuna prova che tratti. Tuttavia, in realtà in realtà traccia / esegue il programma su cui viene eseguito con l'input fornito.

La prova logica almeno è semplice. Se non fosse necessario tracciare almeno il primo passaggio, non sarebbe necessario l'input insieme al programma su cui è eseguito. Per fare qualsiasi uso delle informazioni, deve almeno tracciare il primo passo prima di provare ad analizzare dove sta andando quel percorso.

I difficili problemi di matematica menzionati nella risposta principale sono quelli in cui non è possibile eseguire l'avanzamento rapido per capire la risposta, il che significa che il problema dell'arresto dovrebbe continuare a tracciare fino a quando alcuni pattern erano riconoscibili.

Quindi l'unica argomentazione pratica per ottenere dal problema dell'arresto è che una macchina di arresto non può determinare il risultato di un risolutore di problemi ottimizzato più veloce di quello che il risolutore di problemi può completare.

Dare una dimostrazione formale per questo ragionamento è più difficile, e anche se credo che potrei, tentare di spiegarlo a qualcuno in un mondo accademico si tradurrà in loro a lanciare una scimmia come capriccio e oscillare dal lampadario. È meglio non discutere con quelle persone.

ecco la risposta, è sì, nel lontano 1967, dal link

Il problema dell'arresto può essere almeno teoricamente risolto per i sistemi a stati fi niti è stato già discusso da Minsky nel 1967 [4]: "... qualsiasi macchina a stato finito, se lasciata completamente a se stessa, cadrà alla fine in un modello ripetitivo perfettamente periodico. La durata di questo pattern ripetuto non può superare il numero di stati interni della macchina ... "

(e quindi se ti attacchi a macchine di turing finite, allora puoi costruire un oracolo)

Ovviamente, quanto tempo ci vuole è un'altra domanda