Decidibilità linguistica
Si chiama una lingua Decidable o Recursive se c'è una macchina di Turing che accetta e si ferma su ogni stringa di input w. Ogni lingua decidibile è Turing-Accettabile.
Un problema decisionale P è decidibile se la lingua L di tutti i casi sì P è decidibile.
Per una lingua decidibile, per ogni stringa di input, la TM si ferma allo stato di accettazione o di rifiuto come illustrato nel diagramma seguente:
Esempio 1
Scopri se il seguente problema è decidibile o meno:
Un numero 'm' è primo?
Soluzione
Numeri primi = {2, 3, 5, 7, 11, 13, ………… ..}
Dividi il numero ‘m’ da tutti i numeri tra "2" e "√m" a partire da "2".
Se uno qualsiasi di questi numeri produce un resto zero, allora va allo "stato Rifiutato", altrimenti va allo "stato Accettato". Quindi, qui la risposta potrebbe essere "Sì" o "No".
Hence, it is a decidable problem.
Esempio 2
Dato un linguaggio regolare L e stringa w, come possiamo verificare se w ∈ L?
Soluzione
Prendi il DFA che accetta L e controlla se w è accettato
Alcuni problemi più decidibili sono:
- DFA accetta la lingua vuota?
- È L 1 ∩ L 2 = ∅ per gli insiemi regolari?
Note -
Se una lingua L è decidibile, quindi il suo complemento L' è anche decidibile
Se una lingua è decidibile, allora c'è un enumeratore per essa.