funzionericorsivaprimitivafunzionericorsivaprimitiva in logica, → funzionericorsiva ottenuta a partire dalle funzioni base applicando solo gli schemi della composizione e della ricorsione. Esempi [...] di funzioniprimitive sono l’addizione, la moltiplicazione, l’elevazione a potenza con esponente naturale, il fattoriale e molte fra le funzioni solitamente utilizzate. Esistono tuttavia delle funzioniricorsive che non sono ricorsiveprimitive: è il ...
Leggi Tutto
funzione definita ricorsivamentefunzione definita ricorsivamentefunzione di dominio N i cui valori sono determinabili attraverso passi successivi di calcolo, tali che, assegnato il suo valore iniziale, [...] e si risolve soltanto quando si raggiunge il passo iniziale. Per esempio:
Una funzione definita ricorsivamente può così essere calcolata tramite un algoritmo ricorsivo (→ calcolo ricorsivo; → funzionericorsiva; → funzionericorsivaprimitiva). ...
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
Dimostrazione, teoria della
Jean-Yves Girard
La teoria della dimostrazione nasce negli anni Venti del Novecento come strumento di realizzazione del programma di David Hilbert per la fondazione della [...] della dimostrazione di partenza e quella senza tagli che si ottiene non è maggiorato nemmeno da una funzionericorsivaprimitiva. Per dimostrare la convergenza dell'algoritmo di eliminazione dei tagli occorre quindi ricorrere a un'induzione su ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Giorgio Strano
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
Negli anni Trenta del Novecento i logici riescono a dare uno statuto matematico alla [...] logico tedesco Wilhelm Ackerman esibisce una funzione, oggi chiamata funzione di Ackerman, intuitivamente calcolabile ma non ricorsivaprimitiva poiché “cresce più in fretta” di ogni altra funzionericorsivaprimitiva. Solo nel 1934, raccogliendo un ...
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
Ackermann, funzione di
Ackermann, funzione di esempio di → funzionericorsiva che non è ricorsivaprimitiva (→ funzionericorsivaprimitiva). Hilbert formulò l’ipotesi che ogni funzione calcolabile fosse [...] e ricorsione. Tale affermazione si rivelò infondata quando nel 1928 Ackermann definì una nuova funzione calcolabile, ma non ricorsivaprimitiva, poiché per ottenerla è necessario un ulteriore procedimento, detto di minimalizzazione. Questa ...
Leggi Tutto
predecessore
predecessore o precedente, di un numero naturale n non nullo indica il numero che viene immediatamente prima di n nell’usuale ordinamento di N: 0, 1, 2, 3… Per esempio il predecessore di [...] , per convenzione, che il predecessore di 0 sia 0 stesso (p(0) = 0). La funzione p(n) è una → funzionericorsivaprimitiva. Essa può essere definita usando le funzioni di base proiezione (indicata con il simbolo P12(m, n)), che associa a ogni coppia ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. La probabilita
Eugenio Regazzini
La probabilità
Evoluzione della nozione di probabilità
La grande difficoltà in cui si dibattevano i cultori [...] chiarezza formale, Kolmogorov considera un insieme Ω di enti primitivi, deno minati 'casi elementari' e una classe E di con l'apparizione dei concetti di 'algoritmo' e di 'funzionericorsiva'. Infatti, nel 1940, Alonzo Church se ne avvalse per ...
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.;...