title: Linguaggio ricorsivo
text: # Linguaggio ricorsivo
  
  In matematica, logica e informatica teorica, i linguaggi decidibili o ricorsivi sono una classe di linguaggi formali che corrisponde alla classe dei problemi decidibili. Esistono due definizioni principali equivalenti per questa classe:
  
  * Un linguaggio ricorsivo è un linguaggio per il quale esiste una macchina di Turing che, data una qualsiasi stringa di input, termina accettando la stringa se essa appartiene al linguaggio, e termina rifiutando la stringa in caso contrario.
  * Un linguaggio ricorsivo è un sottoinsieme ricorsivo dell'insieme di tutte le possibili stringhe sull'alfabeto del linguaggio.
  
  Tutti i linguaggi ricorsivi sono ricorsivamente enumerabili. Sono ricorsivi tutti i linguaggi regolari, liberi dal contesto e dipendenti dal contesto. È degno di nota il fatto che questa categoria non abbia un corrispondente diretto nella classificazione di Chomsky.
  
  ## Proprietà di chiusura
  
  L'insieme dei linguaggi ricorsivi è chiuso rispetto alle seguenti operazioni:
  
  * star di Kleene
  * omomorfismo (purché non si utilizzi la stringa vuota ε)
  * concatenazione
  * unione
  * intersezione
  * complemento
  * (per via di 5 e 6) differenza
  