Informatica
Fabrizio Luccio
Franco P. Preparata
Carl-Erik Fröberg
Piero Sguazzero
Piero Dell'Orco e Tomaso Poggio
Teoria della computazione di Fabrizio Luccio
SOMMARIO: 1. Origine e motivazioni. [...] il famoso teoremadiincompletezzadiGödel, che provava l'esistenza di formule indimostrabili nel calcolo dei predicati del primo ordine, attraverso la costruzione di una di tali formule.
La prova diGödel, basata sulla costruzione di una formula ...
Leggi Tutto
STORIA DELLA MATEMATICA
Luigi Borzacchini
STORIA DELLA MATEMATICA
Il tempo della scienza senza tempo
La matematica è la più antica e la più immutabile delle discipline. Si può dire che la matematica [...] dal numero nt e quindi ng era una funzione aritmetica di nt, ng = φ(nt). Gödel riuscì a determinare una formula d che rappresentava un punto (primo teoremadiincompletezza). Si tratta di una incompletezza essenziale: la possibile aggiunta di d ( ...
Leggi Tutto
lògica matemàtica Branca della logica, che utilizza un linguaggio simbolico e adotta un sistema di calcolo di tipo algebrico per esaminare le espressioni di un discorso deduttivo. Queste ultime possono [...] 1931 però K. Gödel dimostrò che in qualsiasi sistema formale coerente in grado di rappresentare l'aritmetica esistono formule di cui non si può dimostrare né la verità né la falsità (teoremadiincompletezza).
Abstract di approfondimento da Logica ...
Leggi Tutto
Metodo
GGerard Radnitzky
di Gerard Radnitzky
Metodo
sommario: 1. Introduzione. 2. Concetto e definizione di procedimento metodico, metodo e metodologia. a) Distinzione tra i vari livelli. b) Definizione [...] sostenitori. Con la dimostrazione, data da Gödel nel 1931, dell'incompletezza dei Principia mathematica e della teoria dei matematica (dal teoremadiGödel) consegue che la costruzione di una macchina di Turing capace di calcolare qualsiasi funzione ...
Leggi Tutto
Il termine complessità è oggi frequentemente usato, in campo scientifico, in contesti diversi. In quello dell'informatica, dell'analisi numerica e dell'ottimizzazione, corrisponde alla caratteristica quantitativa [...] neri. L'induzione ha incontestabilmente un valore euristico, ma non ha valore di prova assoluta.
Il teoremadiincompletezzadi K. Gödel mostra, d'altronde, che un sistema deduttivo formalizzato non può trovare in se stesso la dimostrazione assoluta ...
Leggi Tutto
metateoria
metateoria teoria che ha come oggetto di studio un’altra teoria, che ne costituisce la sua teoria oggetto, di cui indaga caratteristiche, formalizzazioni, sintassi e semantica. I risultati [...] programma hilbertiano, si rivelò però impossibile da realizzare nel momento in cui K. Gödel dimostrò il teoremadiincompletezza (→ Gödel, teoremadi). La distinzione netta fra teoria oggetto e metateoria, oltre che alle problematiche metamatematiche ...
Leggi Tutto
La seconda rivoluzione scientifica: introduzione. Fisica e filosofia della scienza all'alba del XX secolo
Don Howard
Fisica e filosofia della scienza all'alba del XX secolo
Simbiosi disciplinare
La [...] potente o più potente dell'aritmetica di Peano (nella formulazione di primo ordine) ammetteva necessariamente, come Kurt Gödel dimostrò in un corollario al suo primo teorema dell'incompletezza, modelli non isomorfici (Howard 1992). Tuttavia ...
Leggi Tutto
Logiche non standard
Claudio Pizzi
Alcune famiglie di logiche non standard sono costituite da logiche che sono estensioni assiomatiche di quella standard, mentre altre constano di logiche rappresentabili [...] un ben noto corollario del teoremadiGödel.
Pochi anni dopo (1940) un teorema dimostrato da James Dugundji, evidenziando diincompletezza rispetto a strutture relazionali sono sporadici a livello proposizionale, c'è un numero infinito di sistemi ...
Leggi Tutto
Hilbert
Hilbert David (Königsberg, Prussia Orientale, oggi Kaliningrad, Russia, 1862 - Göttingen, Bassa Sassonia, 1943) matematico tedesco. La sua opera ha segnato emblematicamente per la matematica [...] matematica. L’impostazione hilbertiana si manifestò inattuabile in seguito alla formulazione, a opera diGödel, del teoremadiincompletezza (→ Gödel, teoremadi), ma i metodi inaugurati da Hilbert (metodi diretti, in generale non costruttivi, e ...
Leggi Tutto
Computazione, teoria della
Fabrizio Luccio
La necessità del calcolo, pur riconosciuta dall'uomo in tutte le epoche storiche, ha condotto solo in tempi relativamente recenti a una sistemazione teorica [...] negativa nel 1931 con il famoso teoremadiincompletezzadi Kurt Gödel, che provava l'esistenza di formule indimostrabili nel calcolo dei predicati del primo ordine. Questo teorema è basato sulla costruzione di una di tali formule e lascia aperto il ...
Leggi Tutto
incompletezza
incompletézza s. f. [der. di incompleto]. – Condizione di ciò che è incompleto: i. di una serie, di un elenco, di una reazione chimica; non sono in grado di giudicare, per i. dei dati (o per i. d’informazione). In logica matematica,...
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à...