teoremi di indecidibilita
Enciclopedia della Scienza e della Tecnica (2008)
teoremi di indecidibilità
Silvio Bozzi
In logica matematica, risultati che affermano che una data teoria formalizzata T non è decidibile, vale a dire non ammette un algoritmo in grado di stabilire in [...] modo meccanico per ogni formula del linguaggio se è teorema o meno di T. Prototipo di questi risultati è il teorema di Gödel (1931), il quale afferma che l’aritmetica di Peano del primo ordine è indecidibile. Il risultato si può estendere a teorie ...
Leggi Tutto
CATEGORIA:
LOGICA
Logiche non standard
Enciclopedia della Scienza e della Tecnica (2007)
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 [...] è dimostrabile la consistenza dell'aritmetica, il che è impossibile per un ben noto corollario del teorema di Gödel.
Pochi anni dopo (1940) un teorema dimostrato da James Dugundji, evidenziando il carattere non-verofunzionale degli operatori modali ...
Leggi Tutto
CATEGORIA:
LOGICA MATEMATICA
Turing Alan Mathison
Dizionario delle Scienze Fisiche (1996)
Turing 〈tiùrin〉 Alan Mathison [STF] (Londra 1912 - Wilmslow, Cheshire, 1954) Lettore di matematica nell'univ. di Manchester (1948). ◆ [INF] Ipotesi di T.: v. automi, teoria degli: I 330 b. ◆ [INF] Macchina [...] di T.: modello meccanico di algoritmi, proposto da T. nel 1936: v. automi, teoria degli: I 330 b e Gödel, teorema di: III 56 f. ◆ [INF] Test di T.: v. intelligenza artificiale: III 233 b. ...
Leggi Tutto
Spielman
Enciclopedia della Matematica (2013)
Spielman
Spielman Daniel Alan (Philadelphia, Pennsylvania, 1970) matematico e informatico statunitense. Laureatosi all’università di Yale nel 1992, con una tesi su codici e loro efficienza nell’autocorrezione [...] applicata al Massachusetts Institute of Technology dove ha insegnato dal 1996 al 2005. Nel 2008 ha ricevuto il Premio Gödel per i suoi lavori sulla teoria degli algoritmi e nel 2010 il Premio Nevanlinna per gli studi sulle applicazioni della ...
Leggi Tutto
indecidibile
Dizionario delle Scienze Fisiche (1996)
indecidibile
indecidìbile [Comp. di in- neg. e decidibile "che non può essere deciso"] [ALG] [FAF] Teoria i.: quella per la quale non esiste nessun algoritmo mediante il quale sia possibile decidere [...] in un numero finito di passi, per ogni proposizione formulabile in essa, se sia vera o falsa; è tale, per es., l'intera aritmetica (v. Gödel, teorema di: III 53 c). ...
Leggi Tutto
Bernays, Paul
Enciclopedia on line
Logico e matematico svizzero (Londra 1888 - Zurigo 1977), dal 1922 prof. all'univ. di Gottinga, insegnò poi a Helsinki e Zurigo; condirettore della rivista Dialectica. Allievo e collaboratore di D. Hilbert, [...] di B., che sviluppa quello di J. L. von Neumann, è stato studiato anche da K. Gödel: è perciò noto come sistema di von Neumann-Bernays-Gödel, per differenziarlo dal sistema di Zermelo-Fraenkel. Gli ultimi contributi di B. concernono lo studio dell ...
Leggi Tutto
CATEGORIA:
BIOGRAFIE
Lolli
Enciclopedia della Matematica (2013)
Lolli
Lolli Gabriele (Camagna, Alessandria, 1942) matematico e logico italiano. Studioso di teoria della dimostrazione, è stato professore di logica matematica all’università di Torino e dal 2008 insegna [...] . Insiemi costruibili e modelli booleani (1974), Introduzione alla logica formale (1991), Incompletezza. Saggio su Kurt Gödel (1992), La crisalide e la farfalla (2000, sulla discriminazione delle donne nel mondo accademico scientifico), Filosofia ...
Leggi Tutto
non contraddittorieta
Enciclopedia della Matematica (2013)
non contraddittorieta
non contraddittorietà espressione equivalente a → coerenza. Un sistema formale S si dice non contraddittorio se in esso non è possibile dedurre logicamente una contraddizione. In [...] → negazione). Un importante risultato riguardo la non contraddittorietà dei sistemi formali è il cosiddetto secondo teorema di Gödel per il quale non è possibile dimostrare la non contraddittorietà dell’aritmetica formalizzata dagli assiomi di Peano ...
Leggi Tutto
aritmetizzazione
Enciclopedia della Matematica (2013)
aritmetizzazione
aritmetizzazione procedimento di associazione biunivoca di un numero naturale a ogni simbolo fondamentale, formula ben formata o successione di formule di una teoria formale. In tal [...] tra filosofi); tuttavia il processo di aritmetizzazione trova compimento solo nel xx secolo, attraverso l’opera di K. Gödel (→ Gödel, teorema di) ed è per questo anche detto gödelizzazione. Il procedimento di aritmetizzazione si basa sul teorema ...
Leggi Tutto
autoreferenzialita
Enciclopedia della Matematica (2013)
autoreferenzialita
autoreferenzialità proprietà di un enunciato o di una teoria che fanno riferimento a sé stessi. Per esempio, l’asserzione «questa frase ha cinque parole» è autoreferenziale perché [...] formule aritmetiche che non possono essere né dimostrate né confutate nell’ambito dell’aritmetica stessa). Per dimostrare ciò Gödel costruì, mediante un procedimento noto con il nome di gödelizzazione, una formula aritmetica G la cui interpretazione ...
Leggi Tutto