Punti chiave e l'importanza di Decidibilità

Question

Una lingua è decidibile se un TM riconosce la lingua ed entra in uno stato di accettare o rifiutare. Come un dev. Credo che questo sia importante in quanto significherebbe che potremmo determinare se un programma contiene buffer di overflow o deadlock. Inoltre, i seguenti problemi sono Un-decidibile:

• Ha un programma mai accedere una variabile non inizializzata.
• Fare due contesto grammatiche liberi descrivono la stessa langauge.
• Fa una differenza se i parametri a una subroutine sono passati per riferimento o con copia-risultato

In termini di Decidibilità cosa diresti sono i punti chiave per Decidibilità e perché è importante Decidibilità (in particolare per uno sviluppatore).

Nota: Bullet punti vanno bene nelle risposte - posso osservare in sugli argomenti me stesso. Voglio solo sapere quali sono i punti principali.

Answer 1

Forse questo appartiene nella cstheory scambio , ma io avere un andare a esso in ogni caso.

Il punto chiave è: alcuni problemi sono indecidibili, ossia non risolvibili da un algoritmo, per cui dovrebbero essere affrontati con altri metodi. Tra questi problemi sono molti "meta-problemi" in materia di linguaggi di programmazione, ad esempio il problema della la rilevazione di un virus .

Dopo aver deciso che un problema è indecidibile, ci sono diversi corsi possibili di intervento:

1. Alcuni problemi possono essere semi-decidibili, cioè non v'è una semirimorchi -Algoritmi che risolve alcuni casi, ma sempre passanti su altri casi. Quando si implementa un algoritmo di semi-, mettere un timer su di esso e no answer ritorno quando il tempo si esaurisca.
2. Risolvere solo alcune parti, si spera cruciali del problema semplificando esso.
3. 2 + chiedere all'utente per l'input quando il problema diventa troppo complesso.
4. Usa un euristica che ottiene la risposta corretta più del tempo.
5. Usa un linguaggio diverso, forse un non-Turing uno completo.

1 a 3 sono popolari per gli strumenti di ragionamento automatico, tra verificatori programma. 4 è quello che fanno i programmi antivirus. 5 è un buona scelta quando consentendo agli utenti di script di scrittura per automatizzare un sistema più grande ; invece di dare loro piena JavaScript / Schema / Lua / qualunque cosa, dare loro un sottoinsieme limitato che non consente illimitati ricorsione / loop.

Answer 2

Supponiamo di avere a scrivere del software che soddisfa la condizione:. "In fase di esecuzione nessuna funzione deve mai finire che si fa chiamare direttamente o indirettamente"

Questa condizione sarebbe indecidibile, ma una condizione più restrittiva può essere decidibile, per esempio qualcosa come: "No puntatori a funzione devono essere utilizzati e nessuna funzione devono contenere chiamate a se stessa direttamente o indirettamente"

Questo per evidenziare che a volte è possibile flessibilità commercio per decidibilit'a, in modo che certe proprietà richieste del sistema possono diventare esecutiva.

Se un linguaggio di programmazione è decidibile, allora sarà sempre possibile decidere se un programma è un programma valido per quella lingua oppure no.

Ma anche se un programma è un programma valido per la lingua, resta indecidibile se tale programma potrebbe incorrere in un buffer overflow o di una situazione di stallo.