funzioniricorsive
Mauro Cappelli
Classe delle funzioni computabili o algoritmiche, ossia delle funzioni n-arie f tali che esiste un algoritmo per computare il valore f(x1,...,x{[) per ogni n-pla di [...] 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, controsegno di x, fattoriale di x, somma di x e ...
Leggi Tutto
funzione annullatore
funzione annullatore nella teoria delle funzioniricorsive, funzione aritmetica che associa a ogni numero naturale il numero 0; è spesso indicata simbolicamente come Z(x) e si ha: [...] ∀x ∈ N, Z(x) = 0 (→ funzionericorsiva). ...
Leggi Tutto
funzioni, composizione di
funzioni, composizione di operazione tra funzioni impiegata in ambiti diversi della matematica.
□ In analisi, date due funzioni g: X → Y, ƒ: Y → Z, la composizione delle funzioni [...] ) rispetto all’operazione di composizione.
□ In logica, la composizione di funzioni è uno degli schemi, insieme alla ricorsione e alla minimalizzazione, che permette di definire una → funzionericorsiva a partire da due funzioniricorsive date. ...
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
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
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.