Il teorema di Gödel ovvero i teoremi limitativi dell’aritmetica

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 funzioni ricorsive primitive. Attraverso questo procedimento tecnico chiamato gödelizzazione – che Gödel stesso ammetterà di avere ripreso da ... Leggi Tutto

funzione calcolabile

Enciclopedia della Matematica (2017)

funzione calcolabile funzione calcolabile funzione per la quale esiste una procedura di calcolo (→ algoritmo) che permette di determinarne, in un numero finito di passi, il valore in corrispondenza di [...] rappresenta in maniera adeguata l’insieme delle funzioni calcolabili nel senso che ogni funzione calcolabile può essere definita come funzione ricorsiva e, viceversa, ogni funzione ricorsiva è una funzione calcolabile. La tesi di Church è avvalorata ... Leggi Tutto

TAGS: INSIEME DEI NUMERI NATURALI – PRINCIPIO DEL TERZO ESCLUSO – INSIEME DI DEFINIZIONE – MACCHINA DI → TURING – FUNZIONE ARITMETICA

regola ricorsiva

Enciclopedia della Matematica (2013)

regola ricorsiva regola ricorsiva regola che, nella propria formulazione, “richiama sé stessa”. Tale richiamo non è tuttavia una sorta di circolo vizioso perché una regola ricorsiva definisce un oggetto [...] delle pile degli argomenti della procedura. Il principio alla base delle regole ricorsive è applicato anche nella definizione di una importante classe di funzioni, le → funzioni ricorsive, le quali hanno il ruolo di tradurre in termini formali il ... Leggi Tutto

TAGS: FUNZIONE CALCOLABILE – FUNZIONI RICORSIVE – NUMERO NATURALE – INFORMATICA – FATTORIALE

successore

Enciclopedia della Matematica (2013)

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 → funzioni ricorsive di base a partire dalle quali è possibile costruire tutte le funzioni ricorsive primitive. Per esempio, la funzione addizione (Add) è una funzione ricorsiva primitiva che può essere ... Leggi Tutto

TAGS: FUNZIONE RICORSIVA PRIMITIVA – INSIEME TOTALMENTE ORDINATO – FUNZIONE SUCCESSORE – ORDINAMENTO TOTALE – TEORIA DEI NUMERI

Church, Alonzo

Dizionario di filosofia (2009)

Church, Alonzo Logico e matematico statunitense (Washington 1903 - Hudson, Ohio, 1995). Prof. di matematica (1947-61), poi di matematica e filosofia (1961-67) a Princeton, insegnò dal 1967 matematica [...] calcolabile da una macchina di Turing, da un algoritmo di Markov, ecc.) sono coestensive alla classe delle funzioni ricorsive. Tuttavia la tesi si può confermare con argomenti di carattere sperimentale ma non può essere dimostrata, perché la nozione ... Leggi Tutto

TAGS: LINGUAGGIO DI PROGRAMMAZIONE – FUNZIONI RICORSIVE – CALCOLO MECCANICO – TEORIA DEI TIPI – COMBINATORIA

annullatore

Enciclopedia della Matematica (2013)

annullatore annullatore particolare sottospazio costituito da funzionali che si annullano in relazione a un sottospazio di un dato spazio vettoriale. Più precisamente, se W è un sottospazio di uno spazio [...] formula: ☐ In aritmetica, l’aggettivo è a volte usato per indicare 0, elemento assorbente della moltiplicazione. ☐ La funzione annullatore, nella costruzione delle funzioni ricorsive è la funzione aritmetica che associa 0 a qualsiasi suo argomento. ... Leggi Tutto

TAGS: SPAZIO VETTORIALE QUOZIENTE – SOTTOSPAZIO VETTORIALE – FUNZIONE ARITMETICA – ELEMENTO ASSORBENTE – FUNZIONALI LINEARI

Kleene, Stephen Cole

Enciclopedia on line

Matematico e logico matematico statunitense (Hartford, Connecticut, 1909 - Madison, Wisconsin, 1994). Dal 1935 al 1979 prof. all'univ. di Wisconsin, a Madison; dal 1969 fu membro della National academy [...] of sciences degli USA. Sviluppò la teoria delle funzioni lambda-definibili e introdusse le funzioni parziali ricorsive per le quali dimostrò il teorema di recursione. Stabilì, per i predicati dell'aritmetica, una gerarchia a seconda del minimo numero ... Leggi Tutto

CATEGORIA: BIOGRAFIE

TAGS: INTUIZIONISMO – CONNECTICUT – RECURSIONE – WISCONSIN – HARTFORD

MOSTOWSKI, Andrzej

Enciclopedia Italiana - IV Appendice (1979)

MOSTOWSKI, Andrzej Logico matematico polacco, nato a Leopoli il 1° novembre 1913. Dal 1947 professore di matematica all'università di Varsavia; dal 1956 membro dell'Accademia polacca delle scienze. Nel [...] teorie dei modelli, di logiche polivalenti, di intuizionismo. Nel 1946 ha scoperto analogie tra la teoria delle funzioni ricorsive e quella degl'insiemi boreliani. Nel 1949 ha dimostrato l'insolubilità del problema della decisione per gli anelli ... Leggi Tutto

ORDINARE IL MONDO

XXI Secolo (2010)

Ordinare il mondo Paolo Zellini La matematica intesa come una razionalizzazione dell’esperienza, secondo la concezione del filosofo e matematico italiano Federigo Enriques (1871-1946), ha sempre cercato [...] di razionali con somma limitata. Analogamente vi sono diverse definizioni possibili, equivalenti tra loro, del concetto di algoritmo: le funzioni ricorsive, il λ-calcolo, il formalismo di Andrej A. Markov (1903-1979) e la macchina di Alan M. Turing ... Leggi Tutto

Turing, macchina di

Enciclopedia della Matematica (2013)

Turing, macchina di Turing, macchina di automa universale, elaborato dal logico inglese A.M. Turing, che fornisce una traduzione formale del concetto intuitivo di → calcolabilità. Sebbene introdotta [...] tutti questi formalismi descrivono tutte e sole le funzioni ricorsive. La tesi di → Church afferma appunto che l’insieme delle funzioni ricorsive coincide con quello delle funzioni calcolabili. Il funzionamento di una macchina di Turing è descritto ... Leggi Tutto

TAGS: FUNZIONI CALCOLABILI – LINGUAGGIO REGOLARE – MACCHINA DI TURING – FUNZIONI RICORSIVE – LETTURA/SCRITTURA