decisione, problema della
decisione, problema della in logica, problema che concerne la possibilità di determinare la validità di un enunciato in un dato sistema logico. Per esempio, nel linguaggio degli [...] (ossia nel linguaggio dei predicati) come dimostrato nel 1936 da A. Church e in generale dal teorema di → Gödel, che afferma l’esistenza, per ogni sistema formale non contraddittorio contenente la teoria dei numeri, di proposizioni che non ...
Leggi Tutto
Grelling
Grelling Kurt (Berlino 1886 - Auschwitz 1942) matematico, logico e filosofo tedesco. Fu tra i promotori del gruppo di filosofi neopositivisti noto come Circolo di Berlino. Il suo nome è legato [...] smise di tenere attivo il Circolo di Berlino organizzando seminari e tenendo conferenze. Iniziò quindi a collaborare con K. Gödel e nel 1936 pubblicò l’articolo Gibt es eine Gödelsche Antinomie? (Esiste una antinomia gödeliana?) nel quale, difendendo ...
Leggi Tutto
insiemi, teoria degli
insiemi, teoria degli settore della matematica che studia gli insiemi, le loro proprietà e le operazioni tra essi. La prima trattazione sistematica della teoria degli insiemi si [...] l’ipotesi generale del continuo e nella possibilità di deciderla a partire dagli usuali assiomi della teoria. I risultati di K. Gödel del 1938 e di P. Cohen del 1963 hanno mostrato infatti che l’ipotesi del continuo è indipendente dagli altri assiomi ...
Leggi Tutto
ricorsivo
ricorsivo [agg. Der. di ricorrere: (→ ricorrente)] [LSF] Sinon. di ricorrente. ◆ [ALG] [INF] Algoritmo, o procedimento o procedura, r.: algoritmo che è formulato con esplicito riferimento a [...] funzioni iniziali mediante un numero finito di applicazioni delle regole di sostituzione e induzione: v. complessità di calcolo: I 663 b. ◆ [ALG] Insiemi r.: v. Gödel, teorema di: III 57 b. ◆ [INF] Paradigma r.: v. algoritmi, teoria degli: I 102 c. ...
Leggi Tutto
Matematico e logico-matematico statunitense, nato a Long Branch (New Jersey) il 2 aprile 1934. Ha conseguito il Ph. D. all'università di Chicago nel 1958; è professore di matematica all'università di Stanford [...] congettura (già formulata da G. Cantor nel 1878, e posta da D. Hilbert nel 1900 come primo problema matematico) K. Gödel nel 1940 aveva dimostrata la compatibilità con quegli assiomi. Il teorema di C. e il cosiddetto "metodo del forcing", da lui ...
Leggi Tutto
Informazione e computazione quantistica: teoria
Mario Rasetti
Al crocevia tra scienza e tecnologia
La nuova disciplina che va sotto il nome di informazione e computazione quantistica si sviluppa al [...] dall’algoritmo ma dalla natura – classica o quantistica – del sistema fisico con cui esso viene eseguito.
Fin da quando Kurt Gödel (1906-1978) enunciò i suoi teoremi d’incompletezza, si sa che l’universalità costringe a pagare un prezzo molto alto ...
Leggi Tutto
Kelley
Kelley John Leroy (Kansas City 1916 - Oakland, California, 1999) matematico statunitense. Si è occupato prevalentemente di analisi funzionale e topologia; il suo testo General topology (Topologia [...] anche alla teoria assiomatica degli insiemi, da lui costruita con un approccio innovativo a partire dalla teoria di → Neumann-Bernays-Gödel (teoria nbg), con una modifica all’assioma nbg0. Questa estensione della teoria nbg, in cui in tale assioma la ...
Leggi Tutto
Herbrand
Herbrand Jacques (Parigi 1908 - La Bérarde, Isère, 1931) matematico e logico francese. Morì giovanissimo all’età di 23 anni in un incidente alpinistico. A 17 anni fu ammesso, primo in graduatoria [...] Un mese più tardi, la sua morte prematura mise improvvisamente fine a una corrispondenza che aveva appena iniziato con K. Gödel. Tra i suoi importanti contributi, si ricordano il teorema di → deduzione, anche riportato in letteratura con il suo nome ...
Leggi Tutto
algebra combinatoria
algebra combinatoria o combinatoria algebrica, settore di studi che utilizza metodi combinatori, cioè di ordinamento e conteggio, per lo studio di problemi algebrici o, viceversa, [...] rapidamente di ogni funzione calcolabile. È un risultato non dissimile da quello a cui era giunto K. Gödel nel 1931, in un’epoca ben lontana dall’avvento dei moderni computer (→ Gödel, teorema di), ma mentre l’enunciato non dimostrabile formulato da ...
Leggi Tutto
Vienna, Circolo di (Wiener Kreis)
Vienna, Circolo di
(Wiener Kreis) Associazione di filosofi e scienziati che si riunirono attorno a Schlick, prof. di filosofia della natura presso l’univ. di Vienna, [...] divenuto successivamente il Circolo di Vienna. Tra i membri principali del circolo vanno ricordati: Schlick, Carnap, Feigl, Frank, K. Gödel, Hahn, V. Kraft, Neurath, Waismann. Il Circolo di V. fu in contatto, da un lato, soprattutto attraverso la ...
Leggi Tutto
godeliano
‹ġö-› agg. – Relativo al matematico Kurt Gödel (1906-1978) e alla sua opera: teoremi g., o prove di Gödel, le dimostrazioni, da lui formulate, dell’incompletezza di qualsiasi assiomatizzazione della teoria dei numeri, dell’impossibilità...
numero
nùmero s. m. [dal lat. numĕrus; cfr. novero]. – 1. Ciascuno degli enti astratti che rappresentano insiemi di unità, ordinati in una successione infinita (serie naturale dei n.) nella quale ogni elemento conta un’unità in più rispetto...