Matematico e logico-matematico statunitense (Washington 1903 - Hudson, Ohio, 1995), prof. di matematica (1947-61), poi di matematica e filosofia (1961-67) a Princeton, dal 1967 di matematica e filosofia [...] di Post. La tesi di Ch. e l'affermazione inversa (cioè ogni funzionericorsiva è effettivamente calcolabile) precisano la nozione di procedimento effettivo di calcolo nel caso di funzioni di numeri naturali. La tesi di Ch. non si può né dimostrare ...
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 funzioniricorsive primitive sono le comuni funzioni aritmetiche elementari: predecessore di x: pr(1) = 0, pr(x′) = x; segno di x: sg(0) = 0 ...
Leggi Tutto
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 [...] concetto di operazione effettiva (realizzabile cioè mediante a.). Su questa linea si sviluppano il concetto di funzionericorsiva, la definizione delle funzioni mediante l’operatore di astrazione lambda e i sistemi di combinatori di H.B. Curry. Dall ...
Leggi Tutto
Logico e matematico statunitense (Augustów, Polonia, 1897 - New York 1954); prof. (1944) all'univ. di New York. Nel 1921 diede la prima dimostrazione della completezza sintattica del calcolo proposizionale [...] . Importante la sua teoria dei sistemi formali e degli insiemi ricorsivamente numerabili, di quegli insiemi, cioè, che o sono vuoti o sono codominî di una funzionericorsiva. Nel 1947 dimostrò l'impossibilità di risolvere il problema della ...
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 [...] due regole di derivazione. Sia f0(x), f1(x), f2(x), ... la successione di funzioniricorsive ottenute in tal modo. Si consideri la funzione F(x)=fx(x)+1. Questa funzione è computabile in senso intuitivo, dal momento che, fissato un numero naturale n ...
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 [...] "à la justifier". La situazione cambiò, segnando un progresso, con l'apparizione dei concetti di 'algoritmo' e di 'funzionericorsiva'. Infatti, nel 1940, Alonzo Church se ne avvalse per precisare regole appropriate di selezione in modo da garantire ...
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 [...] non è maggiorato nemmeno da una funzionericorsiva primitiva. Per dimostrare la convergenza dell un principio d'uniformità, così che se f: α→α′ è una funzione strettamente crescente si può definire una α-dimostrazione ‒ l'immagine reciproca di Π ...
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 [...] su di esse (ricorsione primitiva e ricerca del minimo, che definiremo più avanti). Egli aveva dunque concepito la nozione di funzionericorsiva nel senso moderno, e un analogo di quella che si chiama tesi di Church, cioè l'asserzione che la nozione ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. L'intuizionismo di Brouwer
Anne L. Troelstra
L'intuizionismo di Brouwer
Nella dissertazione Over de Grondslagen der Wiskunde (I fondamenti della [...] (m,k) e k realizza B(m).
Qui ∙ è l'operazione di applicazione tra un numero e il codice di una funzionericorsiva parziale. Kleene stabilì la correttezza di questa interpretazione: se HA ⊦A, allora esiste un numero n che realizza A. In particolare ...
Leggi Tutto
Parte dell’analisi matematica che si occupa della ricerca di algoritmi per la risoluzione numerica di problemi quali l’approssimazione di funzioni e l’integrazione di equazioni differenziali ordinarie [...] ambo i membri dell’equazione differenziale y′= f[x, y(x)], ottenendo l’equazione integrale:
Si consideri ora la successione di funzioni {yn(x)} così definita ricorsivamente:
Si dimostra che questa successione converge rapidamente in I verso la ...
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...
piazza
s. f. [lat. platĕa «via larga, piazza» (dal gr. πλατεῖα, propriam. femm. di πλατύς «largo»); cfr. platea, che risale a una variante lat. platēa con e lunga]. – 1. a. Area libera, più o meno spaziosa, di forma quadrata, rettangolare,...