Ricorsivita

ricorsivita

ricorsività in logica, caratteristica di un procedimento che riduce la complessità di un problema riportandolo a problemi via via più semplici cui il procedimento stesso viene applicato. Un procedimento ricorsivo è, quindi, un procedimento basato su una o più → regole ricorsive. Per esempio il seguente procedimento di calcolo della potenza 5⁴:

è un procedimento ricorsivo perché applica le seguenti regole per il calcolo di aⁿ (in cui la base a è un numero positivo fissato e l’esponente n è un numero naturale):

• a⁰ = 1

• aⁿ = a ⋅ aⁿ⁻¹

Esempi di ricorsività si ritrovano nelle definizioni di oggetti numerici (per esempio la successione di → Fibonacci è comunemente definita per ricorsione) così come in particolari oggetti geometrici. Un tipico esempio è la curva di → Peano o, più in generale, tutte le cosiddette → curve patologiche.

La teoria della ricorsività è una delle branche fondamentali della logica matematica e si pone come obiettivo quello di definire, in senso matematicamente rigoroso, il concetto intuitivo di → funzione calcolabile, per la quale cioè esista un procedimento (→ algoritmo) che calcoli, in un numero finito di passi, il valore della funzione in uscita in corrispondenza di ogni valore in ingresso. A tale scopo sono stati introdotti, negli anni Trenta del secolo scorso, diversi modelli di calcolo, fra cui l’insieme delle → funzioni ricorsive, il → lambda-calcolo e la macchina universale di → Turing, i sistemi di → Post. Tali modelli si sono rilevati equivalenti nel senso che l’insieme delle funzioni ricorsive coincide con l’insieme delle funzioni rappresentabili in ciascuno dei precedenti formalismi. Da qui l’ipotesi (→ Church, tesi di) che l’insieme delle funzioni ricorsive coincida con l’insieme delle funzioni effettivamente calcolabili. Strettamente connesse con il concetto di funzione ricorsiva sono le nozioni di insieme decidibile e semidecidibile (→ decidibilità). Un insieme A si dice decidibile o ricorsivo qualora esista un algoritmo per decidere, per un qualunque elemento a, se esso appartenga o meno ad A; in tale caso la funzione caratteristica dell’insieme è una funzione ricorsiva. Se invece, dato un elemento a, è possibile stabilire algoritmicamente, in un numero finito di passi, se esso appartiene all’insieme, mentre non è ugualmente decidibile la sua non appartenenza all’insieme, allora l’insieme è detto semidecidibile, o ricorsivamente enumerabile. Ogni insieme decidibile è semidecidibile, ma non viceversa. Mediante la tecnica della gödelizzazione (→ Gödel, numero di), i teoremi di un sistema formale possono essere identificati con un insieme di numeri naturali; perciò ha senso parlare di sistemi formali ricorsivamente enumerabili e ricorsivi. Mentre il requisito dell’enumerabilità è per lo più inglobato nella definizione stessa di sistema formale, la maggior parte dei sistemi formali con cui si ha a che fare non sono ricorsivi. Infatti nel 1936 A. Church dimostrò l’indecidibilità dell’aritmetica elementare e, in un secondo tempo, della logica dei predicati del primo ordine.

Oltre che in logica, la teoria della ricorsività ha trovato applicazioni anche in altri settori della matematica. Un esempio interessante è costituito dalla soluzione del decimo problema di Hilbert (→ Hilbert, problemi di). Per una equazione diofantea, cioè della forma p(x₁, ..., x_n) = 0, dove p(x₁, ..., x_n) è un polinomio a coefficienti interi, si pone il quesito: esiste un algoritmo che consenta di stabilire, data una qualsiasi equazione diofantea, se essa ha una soluzione intera? Utilizzando i concetti e le tecniche della teoria della ricorsività, a questa domanda è stata data una risposta negativa dal matematico russo J. Matijasevič nel 1970. Tra gli sviluppi della teoria vanno ricordate la cosiddetta teoria della ricorsività generalizzata e la teoria della complessità. La prima è nata dal tentativo di estendere a domini diversi da quello dei numeri naturali il concetto di funzione ricorsiva; questo nuovo punto di vista ha condotto a una migliore comprensione di alcuni risultati della teoria classica e all’individuazione di legami profondi fra la teoria della ricorsività e altre branche della logica, in particolare la teoria degli insiemi. Quanto alla teoria della → complessità, essa è stata stimolata dall’esigenza di applicazioni pratiche nell’ambito dell’informatica teorica o computer science e consiste in un tentativo di classificare le funzioni ricorsive in base al grado di difficoltà del loro computo.