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 ₁ ∩ L ₂ = ∅ 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.