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 il problema della decisione per le teorie formali (formulato da E. Schröder nel 1895 e ripreso da ...
Leggi Tutto
ricorsionericorsione in logica, uno dei tre schemi per la costruzione di una → funzione ricorsiva a partire dalle funzioni base (annullatore, successore e proiettori), insieme allo schema della composizione [...] e allo schema della minimalizzazione. Una funzione ƒ di n + 1 variabili ƒ(x1, ..., xn, y) è definita (o costruita) per ricorsione a partire da una funzione di n argomenti h(x1, ..., xn) e da una funzione di n + 2 argomenti F(x1, ..., xn, z, y) ...
Leggi Tutto
funzione ricorsiva primitiva
funzione ricorsiva primitiva in logica, → funzione ricorsiva ottenuta a partire dalle funzioni base applicando solo gli schemi della composizione e della ricorsione. Esempi [...] di funzioni primitive sono l’addizione, la moltiplicazione, l’elevazione a potenza con esponente naturale, il fattoriale e molte fra le funzioni solitamente utilizzate. Esistono tuttavia delle funzioni ...
Leggi Tutto
procedura ricorsiva
procedura ricorsiva particolare procedura che ha la caratteristica di poter richiamare sé stessa per la ripetizione di particolari azioni come la lettura, la scrittura, la stampa. [...] Insieme alla funzione ricorsiva rappresenta il tipico costrutto costitutivo dello schema della → ricorsione. ...
Leggi Tutto
Ackermann, funzione di
Ackermann, funzione di esempio di → funzione ricorsiva che non è ricorsiva primitiva (→ funzione ricorsiva primitiva). Hilbert formulò l’ipotesi che ogni funzione calcolabile fosse [...] , che A(2,1) = 5:
La funzione è calcolabile; tuttavia si può dimostrare che non è ottenibile soltanto per composizione e ricorsione di funzioni di base. Per definirla si deve ricorrere a un procedimento basato sull’applicazione di un operatore di ...
Leggi Tutto
minimalizzazione, operatore di
minimalizzazione, operatore di o schema della minimalizzazione, una delle regole attraverso le quali si costruiscono le funzioni ricorsive. L’operatore di minimalizzazione, [...] tutte e sole quelle che si ottengono dalle funzioni base con l’applicazione dei tre schemi costruttivi, di composizione, ricorsione e minimalizzazione. L’operatore µ di minimalizzazione agisce su una funzione di n + 1 variabili e individua il più ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. Teoria della ricorsivita
Piergiorgio Odifreddi
Teoria della ricorsività
La teoria della ricorsività affronta lo studio delle funzioni con lo [...] del minimo', cioè se ogni suo sottoinsieme non vuoto ha un primo elemento. In tal caso è possibile stabilire l'isomorfismo per ricorsione primitiva (associando a 0 il primo elemento e a S(x) il successore dell'elemento associato a x), e il principio ...
Leggi Tutto
funzione ricorsiva
funzione ricorsiva in logica, funzione aritmetica, cioè di dominio e codominio N, definita a partire da alcune funzioni base e attraverso alcune regole costruttive che ne garantiscono [...] di m argomenti (funzione m-aria) e h1 h2, ..., hm sono m funzioni ricorsive n arie, la funzione
è ricorsiva.
• Schema della ricorsione: consiste nel formare una nuova funzione ricorsiva di n + 1 argomenti ƒ(x1, ..., xn, y) a partire da una funzione ...
Leggi Tutto
Church, tesi di
Church, tesi di tesi elaborata dal logico statunitense A. Church; afferma che ogni funzione calcolabile è una funzione ricorsiva e, viceversa, ogni funzione ricorsiva è una funzione calcolabile. [...] secondo gli schemi di una funzione ricorsiva, cioè partendo dalle funzioni base e applicando gli schemi di composizione, ricorsione e minimalizzazione. La tesi di Church afferma, pertanto, che il modello di calcolo fornito dalle funzioni ricorsive ...
Leggi Tutto