• Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X

ricorsivita

Enciclopedia della Matematica (2013)
  • Condividi

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 54:

formula

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

• a0 = 1

• an = a ⋅ an−1

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(x1, ..., xn) = 0, dove p(x1, ..., xn) è 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.

Vedi anche
geometria In senso ampio e generico, ramo della matematica che studia lo spazio e le figure spaziali. Cenni storiciL’antichità - L’origine della g. è legata a concreti problemi di misurazione del terreno (nacque a scopi agrimensori nella zona del delta del Nilo); si trattava quindi essenzialmente di una g. empirica, ... algoritmo Matematica Termine, derivato dall’appellativo al-Khuwārizmī («originario della Corasmia») del matematico Muḥammad ibn Mūsa del 9° sec., che designa qualunque schema o procedimento sistematico di calcolo (per es. l’a. euclideo, delle divisioni successive, l’a. algebrico, insieme delle regole del calcolo ... insieme Fisica Nella meccanica statistica classica con i. statistico, o con il termine ensemble, introdotto da J.W. Gibbs, si indicano famiglie di stati di equilibrio macroscopico. Nello spazio delle fasi, cioè nello spazio delle coordinate pi, (i=1, 2, 3) e delle quantità di moto qi (i=1, 2, 3) di ciascuna ... complessità Caratteristica di un sistema (perciò detto complesso), concepito come un aggregato organico e strutturato di parti tra loro interagenti, in base alla quale il comportamento globale del sistema non è immediatamente riconducibile a quello dei singoli costituenti, dipendendo dal modo in cui essi interagiscono. Biologia Cellula, ...
Tag
  • RICORSIVAMENTE ENUMERABILE
  • TEORIA DELLA → COMPLESSITÀ
  • TEORIA DEGLI INSIEMI
  • FUNZIONE CALCOLABILE
  • INFORMATICA TEORICA
Altri risultati per ricorsivita
  • ricorsività
    Enciclopedia on line
    ricorsività La proprietà di essere ricorsivo, cioè ricorrente. Teoria della r., o della ricorsione, o computabilità, la disciplina che si occupa di fornire una caratterizzazione matematica del concetto di algoritmo. Teoria della ricorsività La motivazione originaria per lo studio della r. fu soprattutto ...
  • ricorsivita
    Dizionario delle Scienze Fisiche (2012)
    ricorsività [Der. di ricorsivo "proprietà di essere ricorsivo"] [ALG] Teoria della r.: teoria che si propone lo studio, nell'ambito dei numeri naturali, degli algoritmi ricorsivi e delle funzioni ricorsive (→ ricorsivo).
  • ricorsione
    Enciclopedia della Scienza e della Tecnica (2008)
    Mauro Cappelli Metodo per definire funzioni in modo tale che la funzione includa sé stessa nella propria definizione. Si tratta di una tecnica di programmazione molto potente e molto sfruttata in informatica, in quanto consente di suddividere il problema da risolvere in sottoproblemi analoghi all’originale ...
Vocabolario
ricorsività
ricorsivita ricorsività s. f. [der. di ricorsivo]. – In matematica e in logica matematica, la proprietà di essere ricorsivo, cioè ricorrente. Teoria della r., teoria matematica che si propone lo studio, nell’ambito dei numeri naturali,...
binormalità
binormalita binormalità s. f. [der. di binormale]. – Nella logica matematica, la condizione di ciò che è binormale, ed è una delle formulazioni equivalenti del concetto generale di ricorsività.
  • Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X
  • Ricerca
    • Enciclopedia
    • Vocabolario
    • Sinonimi
    • Biografico
    • Indice Alfabetico

Istituto della Enciclopedia Italiana fondata da Giovanni Treccani S.p.A. © Tutti i diritti riservati

Partita Iva 00892411000

  • facebook
  • twitter
  • youtube
  • instagram
  • Contatti
  • Redazione
  • Termini e Condizioni generali
  • Condizioni di utilizzo dei Servizi
  • Informazioni sui Cookie
  • Trattamento dei dati personali