Linguaggio ricorsivamente enumerabile

Un insieme A è detto ricorsivamente enumerabile quando esiste una funzione di enumerazione f di cui A è il codominio.

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.

Senza perdita di generalità limitiamoci a considerare l'insieme delle funzioni computabili unarie e aventi 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 intere, in questo caso, cioè, integer corrisponde all'insieme dei numeri naturali, da 0 a più infinito).

Voci correlate

[modifica | modifica wikitesto]
Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky Grammatica formale Linguaggio Automa minimo
Tipo-0 (illimitato) Ricorsivamente enumerabile Macchina di Turing
(illimitato) Ricorsivo Decider
Tipo-1 Dipendente dal contesto Dipendente dal contesto Automa lineare
Tipo-2 Libera dal contesto Libero dal contesto Automa a pila ND
Tipo-3 Regolare Regolare A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme proprio della categoria immediatamente sovrastante.