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 [...] 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 molto più deboli dell’aritmetica di Peano – quale il sistema Q di Robinson – e ...
Leggi Tutto
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 [...] nel linguaggio di PA, tale che né PA |– G né PA |–¬G.
In altre parole, esiste un enunciato formalmente indecidibile in PA.
Questo teorema è tutto incentrato sulla possibilità dell’aritmetica di rappresentare la propria sintassi. Il punto di partenza ...
Leggi Tutto
L'Universo matematico
John D. Barrow
(Astronomy Centre, University of Sussex, Brighton, Gran Bretagna)
Parte di questo saggio è stata pubblicata sotto il titolo Perché il mondo è matematico? Roma-Bari, [...] R, la cui complessità è superiore a quella del sistema del computer. Una domanda come
"R è una sequenza casuale?"
è indecidibile per il computer. La complessità delle proposizioni "R è casuale" e "R non è casuale" è troppo grande per essere tradotta ...
Leggi Tutto
Giuseppe Di Genio
Abstract
Viene esaminata, sulla scorta della dottrina e della giurisprudenza costituzionale, la portata normativa e scultorea del segreto di Stato, la cui dimensione oggettiva cattura [...] pubblico costituzionale, europeo ed internazionale, inteso anche come ordine pubblico materiale, che rende “l’indecidibile” non impossibile e maggiormente compatibile con la formula repubblicana dei diritti.
Il fondamento costituzionale del ...
Leggi Tutto
risolubile
risolùbile [agg. Der. del lat. resolubilis "che si può risolvere", dal part. pass. resolutus del lat. resolvere "sciogliere di nuovo"] [ALG] Equazione algebrica r. per radicali, o r. algebricamente: [...] di Ising in una e due dimensioni (v. modelli risolubili in meccanica statistica). ◆ [ALG] [FAF] Problema non r., o indecidibile: nella logica matematica, problema logico che in linea di principio non ammette una soluzione generale: è tale, per es ...
Leggi Tutto
decisione, problema della
In logica matematica, la ricerca di un procedimento effettivo che consenta di stabilire se una certa proprietà o relazione convenga o no a certi enti. Procedimento ‘effettivo’ [...] teorema di Church del 1936 che l’insieme dei teoremi della logica classica del primo ordine (o calcolo dei predicati) è indecidibile; data una qualunque espressione E del linguaggio della logica del primo ordine, non si è in grado di stabilire, in un ...
Leggi Tutto
INFORMATICA
Paolo Ercoli
Alberto Marini
Con il termine informatica, neologismo di origine francese, s'indica attualmente una nuova ed emergente disciplina, la quale si occupa di particolari rappresentazioni [...] di E. L. Post, conseguenza diretta dell'indecidibilità del problema dell'arresto della macchina di Turing. Questo problema indecidibile si enuncia dicendo che non esiste alcun procedimento effettivo il quale, date due sequenze di stringhe x1, ..., xn ...
Leggi Tutto
LOGICA POLIVALENTE
Claudio Pizzi
Viene chiamata polivalente qualunque logica che risulti completa rispetto a semantiche che ammettono più valori dei due valori di verità standard (di solito identificati [...] schiettamente matematiche la logica trivalente di S.C. Kleene (1952), ove i tre valori sono, intuitivamente, vero, falso e indecidibile. Le matrici qui sono costruite sull'idea che quando la verità o falsità di un componente è sufficiente a ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Giorgio Strano
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
L’ipotesi del continuo, formulata da Georg Cantor negli anni Settanta dell’Ottocento, [...] o refutare l’ipotesi di Cantor. Anche il primo teorema d’incompletezza fornisce un esempio di proposizione indecidibile in un sistema formale sufficientemente espressivo da ambire a esprimere l’aritmetica, ma questa indecidibilità può essere ...
Leggi Tutto
continuo, ipotesi del
continuo, ipotesi del o congettura di Cantor, assioma della teoria degli insiemi (→ Zermelo-Fraenkel, assiomi di) che si formula come segue: non esistono insiemi di cardinalità [...] scelta; in altri termini, questa teoria non può stabilire se l’ipotesi del continuo è vera o falsa. Indecidibile è stata dimostrata anche la cosiddetta ipotesi del continuo generalizzata che estende in modo naturale l’ipotesi precedente affermando ...
Leggi Tutto
indecidibile
indecidìbile agg. [der. di decidere, col pref. in-2]. – Propr., che non può essere deciso. In logica, è detto di ogni asserzione, proposizione, formula per la quale si dimostra che, in un dato sistema formalizzato, né essa né...
indecidibilita
indecidibilità s. f. [der. di indecidibile]. – L’essere indecidibile. In logica, condizione nella quale è impossibile decidere se una proposizione è vera o falsa.