Linguaggio ricorsivamente enumerabile
Da Wikipedia, l'enciclopedia libera.
Un insieme A è detto ricorsivamente enumerabile quando esiste una funzione di enumerazione f tale che A è l'insieme delle immagini di f (cioè A è il codominio di f). Essendoci una corrispondenza biunivoca tra l'insieme delle funzioni calcolabili e l'insieme dei programmi in un qualsiasi linguaggio di programmazione, un insieme è quindi ricorsivamente enumerabile se è possibile generare i suoi elementi attraverso un programma per calcolatore (per la tesi di Church-Turing è indifferente il linguaggio di programmazione scelto). Un insieme ricorsivamente enumerabile è anche detto semidecidibile in quanto è possibile stabilire (in un tempo non quantificabile) se un elemento generico appartiene ad A, ma non è possibile stabilire la non appartenenza di un elemento.
[modifica] Esempio
Senza perdita di generalità ammettiamo che l'insieme delle funzioni computabili siano unarie e abbiano come dominio e codominio l'insieme dei numeri naturali. Prendiamo in considerazione il linguaggio di programmazione Pascal.
L'insieme
A = { x | x è un numero pari }
è ricorsivamente enumerabile in quanto è possibile definire il seguente programma (e la corrispondente funzione).
var a : integer;
begin
read(a);
if a mod 2 = 0 then
write(a)
else
write("2");
end.
il programma precedente dato in input un valore intero maggiore o uguale a 0 restituisce sempre un elemento di A (si assume che non ci siano limiti fisici per la rappresentazione delle variabili integer, in questo caso cioè integer corrisponde all'insieme dei numeri naturali).
[modifica] Voci correlate
| Teoria degli automi: linguaggi formali e grammatiche formali | |||
|---|---|---|---|
| gerarchia di Chomsky |
Grammatiche | Linguaggi | automa minimo |
| Tipo-0 | (illimitato) | Ricorsivamente enumerabile | Macchina di Turing |
| (illimitato) | Ricorsivo | Decider | |
| Tipo-1 | Sensibile al contesto | Sensibile al contesto | Lineare-limitato |
| Tipo-2 | Libero dal contesto | Libero dal contesto | Automa a pila |
| Tipo-3 | Lineare (o Regolare) | Lineare (o Regolare) | A stati finiti |
| Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante. | |||
