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 formaleModifica

Un insieme  , sottoinsieme dei naturali ( ), si dice ricorsivo se la sua funzione indicatrice

 

con

 

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

ProprietàModifica

Insieme complementoModifica

Se un insieme   è ricorsivo, allora anche il suo complemento   (stiamo considerando   come universo) è ricorsivo.

Unione ed intersezioneModifica

Se   e   sono insiemi ricorsivi, allora anche   e   sono ricorsivi.

Ricorsivamente enumerabileModifica

L'insieme   è ricorsivo se e solo se   e il suo complemento   sono entrambi ricorsivamente enumerabili (Teorema di Post).

Immagine funzione ricorsiva totaleModifica

Se l'insieme   è un insieme ricorsivo, ed è anche il dominio di una funzione   funzione ricorsiva e totale, allora anche   è ricorsivo.

Esempi di insiemi ricorsiviModifica

Limitazioni: insiemi non ricorsiviModifica

Ricordiamo che ogni volta che utilizziamo la funzione  , ci riferiamo ad una enumerazione delle funzioni ricorsive in cui la funzione   corrisponde alla  -esima funzione ricorsiva. Cioè detta   la  -esima funzione ricorsiva, abbiamo:

 

Il problema della fermataModifica

L'insieme

 


non è ricorsivo ma ricorsivamente enumerabile.

Insieme degli insiemi ricorsiviModifica

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

Altri insiemi non ricorsiviModifica

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   che rappresenta il problema della fermata lo sarebbe.

  •  
  •  , dove   è una qualunque costante
  •   (indecidibilità della costanza di una funzione)
  •   (indecidibilità del valore di una funzione)
  •   (indecidibilità dell'eguaglianza di due funzioni)
  • se   rappresenta la grammatica libera dal contesto  ,   (problema di decidere se una grammatica libera dal contesto è ambigua)
  • l'insieme delle equazioni diofantee che ammettono radici intere

Voci correlateModifica

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica