Insieme ricorsivo

Nella teoria della calcolabilità un insieme ricorsivo (o insieme decidibile) è intuitivamente un insieme di numeri naturali, per cui è possibile costruire un algoritmo che in un tempo finito (ma a priori non predeterminato) sia in grado, dato un qualunque numero naturale, di stabilire se esso appartiene o no all'insieme.

Più formalmente si dice che un insieme è ricorsivo se la sua funzione caratteristica è ricorsiva.

Definizione formale

Un insieme $S$, sottoinsieme dei naturali ($S\subseteq \mathbb {N}$), si dice ricorsivo se la sua funzione indicatrice

$\mathbf {1} _{S}\colon \mathbb {N} \to \left\{0,1\right\}$

con

$\mathbf {1} _{S}(x)=\left\{{\begin{matrix}1&{\mbox{se}}\ x\in S\\0&{\mbox{se}}\ x\notin S\end{matrix}}\right.$

è ricorsiva e totale (la totalità è implicita nella notazione che abbiamo dato, che prevede che qualunque sia l'input, l'output sia sempre $0$ oppure $1$).

Proprietà

Insieme complemento

Se un insieme $S$ è ricorsivo, allora anche il suo complemento ${\bar {S}}=\mathbb {N} -S$ (stiamo considerando $\mathbb {N}$ come universo) è ricorsivo.

Unione ed intersezione

Se $A$ e $B$ sono insiemi ricorsivi, allora anche $A\cap B$ e $A\cup B$ sono ricorsivi.

Ricorsivamente enumerabile

L'insieme $A$ è ricorsivo se e solo se $A$ e il suo complemento ${\bar {A}}$ sono entrambi ricorsivamente enumerabili (Teorema di Post).

Immagine funzione ricorsiva totale

Se l'insieme $A$ è un insieme ricorsivo, ed è anche il dominio di una funzione $f:A\to B$ funzione ricorsiva e totale, allora anche $B$ è ricorsivo.

Esempi di insiemi ricorsivi

• l'insieme vuoto $\varnothing$
• l'insieme dei numeri naturali $\mathbb {N}$
• qualsiasi sottoinsieme finito di $\mathbb {N}$
• l'insieme dei numeri primi, l'insieme dei numeri pari (e quindi anche quello dei numeri dispari)
• un linguaggio ricorsivo è un insieme ricorsivo nell'insieme di tutte le parole possibili sull'alfabeto del linguaggio formale.

Limitazioni: insiemi non ricorsivi

Ricordiamo che ogni volta che utilizziamo la funzione $\varphi$, ci riferiamo ad una enumerazione delle funzioni ricorsive in cui la funzione $\varphi _{i}$ corrisponde alla $i+1$-esima funzione ricorsiva. Cioè detta $f$ la $i+1$-esima funzione ricorsiva, abbiamo:

$\varphi _{i}(y)=f(y)$

Il problema della fermata

L'insieme

${\mathit {K}}=\lbrace \left\langle x,y\right\rangle |\varphi _{x}(y){\mbox{ è definita}}\rbrace$

non è ricorsivo ma ricorsivamente enumerabile.

Insieme degli insiemi ricorsivi

L'insieme che contiene tutti gli insiemi ricorsivi, non è ricorsivo (e non è neanche ricorsivamente enumerabile).

Altri insiemi non ricorsivi

Molti dei seguenti sono riconducibili al problema della fermata, cioè per dimostrare che non sono ricorsivi si può usare la tecnica di riduzione all'assurdo, per mostrare che se fossero ricorsivi allora anche l'insieme ${\mathit {K}}$ che rappresenta il problema della fermata lo sarebbe.

• $\lbrace x|\varphi _{x}(x){\mbox{ è definita}}\rbrace$
• $\lbrace x|\varphi _{x}(c){\mbox{ è definita}}\rbrace$, dove $c$ è una qualunque costante
• $\lbrace x|\varphi _{x}{\mbox{ è costante}}\rbrace$ (indecidibilità della costanza di una funzione)
• $\lbrace \left\langle x,y,z\right\rangle |\varphi _{x}(y)=z\rbrace$ (indecidibilità del valore di una funzione)
• $\lbrace \left\langle x,y\right\rangle |\varphi _{x}=\varphi _{y}\rbrace$ (indecidibilità dell'eguaglianza di due funzioni)
• se $x$ rappresenta la grammatica libera dal contesto $d_{x}$, $\lbrace x|d_{x}{\mbox{ è ambigua}}\rbrace$ (problema di decidere se una grammatica libera dal contesto è ambigua)
• l'insieme delle equazioni diofantee che ammettono radici intere

Voci correlate

• Funzione ricorsiva
• Insieme ricorsivamente enumerabile