funzionericorsivafunzionericorsiva 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 [...] base applicando solo gli schemi di composizione e ricorsione, sono dette funzioniricorsiveprimitive. Esempi di funzioniricorsiveprimitive sono l’addizione e la moltiplicazione fra numeri naturali, che si possono indicare rispettivamente con ...
Leggi Tutto
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 [...] iniziali mediante un numero finito di applicazioni delle regole di sostituzione e di induzione. Esempi di funzioniricorsiveprimitive sono le comuni funzioni aritmetiche elementari: predecessore di x: pr(1) = 0, pr(x′) = x; segno di x: sg(0) = 0 ...
Leggi Tutto
Logica matematica
Abraham Robinson
*La voce enciclopedica Logica matematica è stata ripubblicata da Treccani Libri, arricchita e aggiornata da un’introduzione di Gabriele Lolli e un saggio di Beppo [...] che ciò, di fatto, non si verifica, osserviamo che non è difficile ordinare effettivamente tutte le funzioniricorsiveprimitive di una variabile secondo una successione infinita, con eventuali ripetizioni, specificando il modo in cui ciascuna ...
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 [...] il comportamento in modo tale da permetterne il calcolo.
La speranza che la classe delle funzioniricorsiveprimitive contenga tutte (e sole) le funzioni calcolabili, cioè quelle per le quali esiste un procedimento che permetta di trovarne i valori ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Maria Conforti
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
I teoremi d’incompletezza di Gödel del 1931 sono i risultati più profondi e spettacolari [...] , perché dipende esclusivamente dalla sua struttura; in particolare, per questa codifica Gödel si serve di funzioniricorsiveprimitive. Attraverso questo procedimento tecnico chiamato gödelizzazione – che Gödel stesso ammetterà di avere ripreso da ...
Leggi Tutto
successore
successore di un elemento qualsiasi x di un insieme totalmente ordinato X (>), è l’elemento x′ ∈ X che è maggiore di x nell’ordinamento totale dell’insieme e tale che non vi siano altri [...] (n) = n + 1. La funzione successore è una delle → funzioniricorsive di base a partire dalle quali è possibile costruire tutte le funzioniricorsiveprimitive. Per esempio, la funzione addizione (Add) è una funzionericorsivaprimitiva che può essere ...
Leggi Tutto
minimalizzazione, operatore di
minimalizzazione, operatore di o schema della minimalizzazione, una delle regole attraverso le quali si costruiscono le funzioniricorsive. L’operatore di minimalizzazione, [...] delle funzioniricorsiveprimitive all’insieme delle funzioniricorsive generali. Le più comuni funzioni calcolabili sono infatti primitivericorsive e per costruirle a partire dalle funzioni base (funzione zero, funzione successore e funzioni di ...
Leggi Tutto
Ackermann
Ackermann Wilhelm (Schönebecke, Herscheid, Sassonia-Anhalt, 1896 ‐ Lüdenscheid, Renania Settentrionale-Vestfalia, 1962) logico e matematico tedesco. Fu allievo e collaboratore di D. Hilbert, [...] della coerenza dell’aritmetica. Attraverso la costruzione di una particolare funzione (→ Ackermann, funzione di), dimostrò che l’insieme delle funzioniricorsiveprimitive non satura il concetto intuitivo di calcolabilità: esiste almeno una ...
Leggi Tutto
INFORMATICA
Paolo Ercoli
Alberto Marini
Con il termine informatica, neologismo di origine francese, s'indica attualmente una nuova ed emergente disciplina, la quale si occupa di particolari rappresentazioni [...] struttura di dati non primitiva con strutture primitive si procede a funzioni proposte come totalità delle funzioni calcolabili, cioè con le funzioni definibili con il cosiddetto "λ-calcolo" di A. Church e con le funzioni generali ricorsive ...
Leggi Tutto
STORIA DELLA MATEMATICA
Luigi Borzacchini
STORIA DELLA MATEMATICA
Il tempo della scienza senza tempo
La matematica è la più antica e la più immutabile delle discipline. Si può dire che la matematica [...] a innumerevoli soluzioni, tra cui le macchine di Turing, le funzioniricorsive, il λ-calcolo.
Anche negli algoritmi la semantica aveva un doppio regime: il significato di una primitiva del linguaggio algoritmico era built-in, dato dalle regole del ...
Leggi Tutto
ricorsivo
agg. [der. di ricorrere]. – In matematica e in logica matematica, sinon. di ricorrente (nel sign. 3 c); in partic., nella teoria della ricorsività, funzioni r. primitive, quelle che si possono ottenere dalle funzioni iniziali mediante...
corso2
córso2 s. m. [lat. cŭrsus -us, der. di cŭrrĕre «correre»]. – 1. a. ant. L’atto, l’esercizio del correre: In picciol c. mi parieno stanchi Lo padre e’ figli (Dante); alla lotta e al corso Io t’educai le membra (Parini); veloce nel c.;...