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
LOGICA MATEMATICA (XXI, p. 398; App. II, 11, p. 226)
Alberto PASQUINELLI
Ludovico GEYMONAT
MATEMATICA Il recente sviluppo della l. m. è caratterizzato da un ulteriore consolidamento istituzionale e [...] McNaughton e J. C. Shepherdson, il grande impulso dato alla dottrina delle funzioniricorsive da K. Gödel, A. Church, H. B. Curry, J. B al posto delle variabili), e il frequente ricorso al metodo della deduzione naturale (o di dimostrazione ...
Leggi Tutto
Logico (Leopoli 1913 - Vancouver 1975), dal 1947 prof. all'univ. di Varsavia, dal 1956 membro dell'Accademia delle scienze polacca. È tra i più fecondi logici polacchi del secondo dopoguerra. Ha scoperto [...] analogie tra la teoria delle funzioniricorsive e quella degli insiemi boreliani (1946); ha dimostrato la insolubilità del problema della decisione per gli anelli e per gli anelli commutativi (1949); ha presentato un'originale formulazione del ...
Leggi Tutto
Matematica e logica matematica (Saint Louis 1919 - ivi 1985), dal 1976 prof. di matematica all'univ. della California a Berkeley. Si è interessata di logica matematica (funzioniricorsive e problemi di [...] decidibilità) e di teoria dei numeri. Di particolare importanza la scoperta (completata da J. V. Matijasević nel 1970) dell'indecidibilità del 10º problema di D. Hilbert: non esiste un metodo generale ...
Leggi Tutto
Intuizionismo
AArend Heyting
di Arend Heyting
Intuizionismo
sommario: 1. Concetti fondamentali. 2. Aritmetica elementare. 3. Il principio del terzo escluso. 4. I numeri reali. 5. Ineguaglianza e separazione [...] al metodo di costruzione di un numero naturale.
Una soluzione fu resa possibile dalla teoria delle funzioniricorsive. L'analisi ricorsiva è diventata un importante campo di ricerca, in cui sono stati ottenuti risultati molto fecondi dai matematici ...
Leggi Tutto
La grande scienza. Automi e linguaggi formali
Dominique Perrin
Automi e linguaggi formali
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. [...] f tale che f(x) è il minimo intero m per il quale g(x,m)=0.
È un risultato classico che le funzioniricorsive e le macchine di Turing, come pure molti altri formalismi, definiscono le stesse classi di oggetti computabili. Che esse corrispondano a ciò ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. I teoremi di incompletezza di Godel
Carlo Cellucci
I teoremi di incompletezza di Gödel
Nei giorni 5-7 settembre 1930 ebbe luogo a Königsberg [...] con quella più debole della coerenza (Rosser 1936) e da Stephen C. Kleene in termini della teoria delle funzioniricorsive (Kleene 1936). Nel 1939 apparve il secondo volume dell'opera di David Hilbert e Paul Bernays, Grundlagen der Mathematik ...
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
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...
definibilita
definibilità s. f. [der. di definibile]. – Possibilità di essere definito. In matematica e in logica matematica, la proprietà che ha un ente di essere calcolabile, per es. mediante funzioni ricorsive.