* Lingua decidabile (lingua ricorsiva): Una lingua L è decidabile se esiste una macchina Turing che, per * ogni * stringa di input W, si ferma e risponde correttamente "sì" se w ∈ L e "no" se W ∉ L. Ciò significa che la TM si interrompe sempre, indipendentemente dal fatto che l'input sia nella lingua o meno.
* lingua riconoscibile (linguaggio ricorsivamente enumerabile): Una lingua L è riconoscibile se esiste una macchina Turing che, per * ogni * stringa di input W, si ferma e risponde "sì" se w ∈ L. Tuttavia, se w ∉ l, il tm può fermare e rispondere a "no" o può funzionare per sempre (loop indefinitamente). La chiave è che * * sempre * fornisce la risposta corretta ("Sì") se la stringa è nella lingua; È consentito solo non deterministico o non è in grado di fornire una risposta quando la stringa non è * nella lingua.
In termini più semplici:
* decidabile: La TM dà sempre una risposta definitiva (sì o no) in tempo finito.
* Riconoscibile: Il TM fornisce una risposta "sì" in tempo finito se l'input è nella lingua, ma potrebbe non dare una risposta (looping per sempre) se l'input non è nella lingua.
Ogni lingua decidebile è anche riconoscibile. Tuttavia, il contrario non è vero; Ci sono lingue riconoscibili che non sono decidibili. Il problema di arresto è un classico esempio di un linguaggio riconoscibile ma non decidabile. È possibile costruire un TM che riconosce le stringhe che rappresentano l'arresto di macchine Turing (simula la macchina e risponde "sì" se si ferma), ma nessuna TM può decidere se una macchina arbitraria di Turing si fermerà su un determinato input (perché ciò risolverebbe il problema di arresto stesso).
La differenza si riduce al fatto che la TM garantisce la terminazione per tutti gli input (decidabile) o garantisce solo una risposta "sì" in tempo finito per gli input nella lingua (riconoscibile). La differenza è fondamentale nella teoria della calcolo.
Programmazione © www.354353.com