Newsgroup: it.comp.ia
Titolo: Cos'e' il Teorema di Gödel ?


Ho tradotto con Systran di Altavista uno spezzone dell'articolo da te
indicato,
e ho trovato un'interessante questione filosofica che mi era stata accennata
anche da un
filosofo che ho incontrato una volta per caso....
"Che cos'e' il teorema di Gödel?
Il teorema di Gödel dichiara che per tutto il sistema convenzionale
costante, ci sono istruzione di aritmetica che sono unprovable all'interno
del sistema. Ciò ha condotto alcuno (Lucas 1963; Penrose 1989) per
concludere che gli esseri umani hanno abilità che non possono essere
duplicate da alcun sistema di calcolo. Per esempio, la nostra abilità " vede
che " la verità della frase di Gödel d'un sistema convenzionale è discussa
per essere non-algoritmica. Non mi occuperò dettagliatamente di questa
obiezione qui, poichè la risposta ad esso non è un' applicazione diretta
della struttura corrente. Noterò semplicemente che il presupposto che
possiamo vedere la verità delle frasi arbitrarie di Gödel richiede che
abbiamo la capacità di determinare la consistenza o la contraddizione di
tutto il dato sistema convenzionale e non c' è motivo di credere che abbiamo
questa abilità in generale. (per più su questo punto, vedere Putnam 1960,
Bowie 1982 ed i commenti su Penrose 1990.) "
Cosa significa esattamente questo teorema?
"Il teorema di Gödel dichiara che per tutto il sistema convenzionale
costante, ci sono istruzione di aritmetica che sono unprovable all'interno
del sistema. Ciò ha condotto alcuno (Lucas 1963; Penrose 1989) per
concludere che gli esseri umani hanno abilità che non possono essere
duplicate da alcun sistema di calcolo. Per esempio, la nostra abilità " vede
che " la verità della frase di Gödel d'un sistema convenzionale è discussa
per essere non-algoritmica..........."
Quali istruzioni artimentiche ?
Conoscete qualche libro che tratta questo argomento? mi interessa molto :-)
Scusate, sono ignorante in materia di IA  :-)
grazie in anticipo per le spiegazioni.
ciao.

Conoscete qualche libro che tratta questo argomento? mi interessa molto :-)
Qualunque libro adottato da un corso di Logica Matematica a Matematica o 
Informatica, oppure - se vuoi divertirti - leggiti [Douglas Hofstadter, Godel, 
Escher, Bach: un'eterna ghirlanda brillante (Adelphi)] che ti dice di tutto e 
di piu', con un sorriso.
-- 
God is Real, unless declared Integer.
ObjectZone - 
http://space.tin.it/computer/csadun/

di piu', con un sorriso.
Mi ci vorra' una settimana per comprendere il TdG.....  :-)
Il libro che mi hai indicato ne avevo gia sentito parlare, lo compro!
grazie per le spiegazioni     :-)
ciao

il suo mestiere lo stesso. :)
No, aspetta un attimo,
allora le reti neurali artificiali che tipo di sistema sono ?
allora le reti neurali biologiche che tipo di sistema sono ?
Continuiamo un'altro po', ti va  ?  :-)
ciao

allora le reti neurali biologiche che tipo di sistema sono ?
In che senso? :)


> Mi ci vorra' una settimana per comprendere il TdG.....  :-)
Se può servire, ci provo io, semplificando molto:
probabilmente, a scuola, ti hanno detto che la matematica (o la geometria),
si basa su 1 ragionamento di base:
- alcuni assunti (assiomi), sono "veri" senza poterli dimostrare
- tutto il resto, viene per dimostrazione logica da quegli assiomi.
Ora, il punto di vista di chi ti ha detto queste cose è: "se scelgo bene gli
assiomi, e non ne dimentico neanche uno, posso dimostrare tutto ciò che è
dimostrabile"
Godel, invece, ha dimostrato che questo punto di vista NON è vero: per
quanti assiomi prenda, per quanto a lungo io applichi la logica, per quanto
complessi possano essere i teoremi che riesco a dimostrare partendo da
quegli assiomi, ci sarà SEMPRE qualche cosa che rimarrà "fuori".
Ovvero: non potrò mai dimostrare tutto.
Sono riuscito a fare un minimo di luce? Spero di sì, anche perchè nel
tentativo ho storpiato non poco il teorema :-)))
--
Alessandro Monti

 In che senso? :)
Ho scritto una grande cavolata!  scusa...  :-)
Il nostro cervello e' un sistema fisico che elabora Sistemi Formali. ok?
Elabora qualunque tipo di sistema formale? Solo alcuni? Che limiti ha?
Le reti neurali artificiali (software) sono equiparabili come algoritmo a un
S.F.?
Se si, allora come S.F. non possono *ne* raggiungere *ne* superare il
cervello
avendo quei limiti imposti dal TdG, mentre il cervello invece elabora S.F. a
N livelli.
Un S.F. non puo' elaborare un S.F di grado superiore al suo, giusto?
Occorrono per forze delle NN hardware per raggiungere le capacita di
elaborare S.F. a N livelli come fa appunto il ns cervello.
(correggimi se sbaglio)
ciao.  :-)
Davide U.

 tentativo ho storpiato non poco il teorema :-)))
:-)))
...penso di si, pero ho ancora il problema del *tutti* (vedi sopra)....
:-)
Grazie  :-)
ciao.

certo per dimostrazione)
"teorema" in logica significa solo "sequenza di simboli". Il T. di Pitagora 
fornisce sia una sequenza di simboli *che* un'interpretazione di quei simboli 
in termini di misura e dimensioni della geometria euclidea. 
Se leggi c1^2 + c^2 = i^2 interpretando c1 come "cristiano", ^2 come "domani", 
c2 come "alessandro", + come "e", = come "avranno" e i^2 come "un sacco di 
soldi", il teorema non vale piu' (almeno per me ;-).
-- 
God is Real, unless declared Integer.
ObjectZone - 
http://space.tin.it/computer/csadun/

(correggimi se sbaglio)
Qui entra in gioco un'altra idea: dato un s.f., e data una nozione di 
computazione (ad esempio, MdT ed automi a stati finiti sono entrambi s.f., con 
attaccate diverse nozioni di computazione), ci sono computazioni veloci (tipo 
verificare se un assioma e' un teorema) e computazioni lente. O *inerentemente* 
lente. Quindi, di tutto cio' che e' computabile, un sacco di cose sono lente. 
Il nome dell'idea e' "complessita' computazionale" - che permette di dire se, 
ad esempio, un certo algoritmo di backpropagation per NN e' o meno 
"inerentemente lento" (nel qual caso anche implementarlo in hardware non 
garantisce nulla). 


 certo per dimostrazione)
Non lo so come ha fatto. L'avrà preso dal mondo delle idee, come suggeriva
Platone.
Comunque poi l'ha dimostrato, prendendo per veri alcuni assiomi.
Nota, però, che non capisco molto il tono di questa risposta. Avevo provato
a semplificare molto più del dovuto, pensando di fare un favore per aiutare
a capire l'idea di base. Se hai dei dubbi così profondi e hai la curiosità
di capire a fondo il teorema di Godel, se sei in graado di fare critiche
così precise e quasi-formali, studiati direttamente il teorema così come
formulato da Godel o nelle varie forme proposte successivamente. Con il
formalismo matematico non c'è più il rischio di equivoci (almeno spero) o di
avere informazioni distorte dalle povere menti obnubilate che animano di
tanto in tanto questo NG (parlo per me, si intende).
--
Alessandro Monti

 N livelli.
La MDT ha un numero finito di stati. Il cervello (e le reti neurali, in
prima approssimazione), lavorano nel campo del continuo, perciņ non hanno un
numero finito di stati.
Anche assumendo i limiti imposti dalla teoria dei quanti, il cervello
assumerebbe un numero di stati finito sģ, ma talmente elevato da fare
impallidire qualsiasi MdT mai formalizzata :-)
--
Alessandro Monti

 certo per dimostrazione)
Non significa nulla. In fisica quantistica TUTTO si basa sulla probabilita':
la casualita' della fisica (principio di indeterminazione di Heisemberg).
Addirittura la luce e' possibile vederla come un'onda di materia o un'onda
eletromagnetica. Ma siamo in grado di calcolare comunque femomeni di
diffrazione, rifrazione eccetera...

 S.F.?
Le reti neurali artificiali non sono paragonabili a quelle naturali perche'
il nostro cervello e' una sorta di calcolatore parallelo nel quale ogni
neurone e' un processore. Fai un po' tu i conti... non e' possibile emulare
una rete simile.

tanto in tanto questo NG (parlo per me, si intende).
Chiedo scusa se nel post precedente ti ho risposto con un tono un po' da
"scemo".
Hai fatto piu' del dovuto e te ne sono grato, qualcosa ho capito e qualcosa
no.
Forse il mio problema e' che ho una cultura matematica un po' scarsa
e faccio un po' fatica a capire i concetti e la matematica del vostro
livello.
(P.s. chiedo troppo se mi dai qualche consiglio per un libro di matematica?
vorrei fare un ripasso veloce in modo da capire un pochino i concetti che mi
avete esposto,
non voglio arrivare al vostro livello ma almeno capire qualcosina di
logica-matematica
se e' questa la materia nella quale si trova il TdG, solo se secondo te, mi
potrebbe
servire per costruire un prg. di IA/sistemi esperti ecc...)
Ti ringrazio molto.
ciao.
Davide U.


mi puoi dire il tuo punto di vista?
ciao.
Davide U.

tanto in tanto questo NG (parlo per me, si intende).
Chiedo scusa se nel post precedente ti ho risposto con un tono un po' da
"idiota".


assioma e' sempre provabile - con una prova di un solo passo.
Mi puoi fare un'esempio di assioma ?
Mi puoi fare un'esempio di teoria costruita sulla base di quell'assioma ?
Che diff. c'e' in senso logico e matematico tra la teorema di pitagora
e il teorema di godel?
grazie
ciao.
Davide U.

 servire per costruire un prg. di IA/sistemi esperti ecc...)
No, non ti serve per IA/SE. Non necessariamente, almeno, cosě come non č
necessario che tu sia un ingegnere aereonautico se devi solo costruirti un
aquilone.
Ovvero: dipende da quali sono i tuoi obiettivi. Se vuoi arrivare ai massimi
livelli, allora prima o poi dovrai affrontare la teoria.
Per un libro...
Io il teorema di Godel l'ho studiato su una dispensa di qualche docente, ma
non ricordo di aver mai letto un libro in cui sia spiegato bene. In "Godel,
Escher, Bach" si trova un ampio commento al teorema (praticamente, tutto il
libro), ma non la dimostrazione formale.
Se serve e se sei delle parti di Milano, posso provare a guardare di quale
dispensa si trattasse, poi puoi procurartela nelle copisterie in cui č in
vendita. Il vantaggio č che non devi studiarti 400 pagine di libro che parla
ti *tutta* la logica formale, se ti interessa solo una cosa, ma solo una
ventina (o qualcosa di piů, non ricordo la lunghezza della dispensa).
--
Alessandro Monti

e il teorema di godel?
Il teorema di Pitagora parla di triangoli rettangoli, il teorema di Godel 
parla dei teoremi dei sistemi formali. :) 



In "MANUALE DI LOGICA Logica classica e del senso comune"
di Magnani, Gennari
Ed. Guerini scientifica
C'e' un intero capitolo (da pag 155 a 180) sul Teorema di Gödel.
Non so' dirti se il libro e' buono o meno, se la trattazione del teorema e'
fatta bene o no. Una cosa posso dirtela : NON SONO pagato da nessuno!!Faccio
questa precisazione perche' e' gia' la seconda volta che cito questo libro e
non vorrei che qualcuno sospettasse...:-))
Ciao Luca

 wrote in message 8bfarn$m21$1...@nslave2.tin.it...

Il nostro cervello non elabora SF. Siamo noi che, per schematizzare,
possiamo modellare la realta' rappresentandola formalmente.
Al contrario il cervello umano inferisce attraverso meccanismi che logica
formale non contempla.
Ad esempio quando ci troviamo di fronte ad un nuovo oggetto dell'universo il
nostro cervello automaticamente associa l'entita' all'oggetto che ritiene
piu' simile.
Cioe' se ho una regola del tipo A->B ed ho un oggetto A', mutazione di A,
posso inferire A'->B con un certo grado di sicurezza.
Cioe', spesso, la mente umana e' poco formale: e' piu' fuzzy...

 ventina (o qualcosa di piů, non ricordo la lunghezza della dispensa).
Non ti disturbare, anche perche' sono di Cesena, per il momento vedo
se riesco a trovare qualcosa in Biblioteca o nelle Librerie che mi dia
un'infarinatura generale sulla TdG
Io possiedo tre Libri:
Mondi della Logica (introduttivo)  -> mi dice solamente che esiste la TdG,
ma non spiega cos'e.
Principi della Matematica (Russel) -> non c'e scritto un tubo della TdG,
non e' nemmeno accennata.
Filosofia della Matematica (Russel) -> non c'e scritto un tubo della TdG.
ueee, sono proprio uno sf....to!
ciao

 a e' un teorema, la cui prova e' "a"
......
Come faccio a distinguere il simbolo {a,....} dall' assioma {a},
cioe' il simbolo {a} e' lo stesso sia per l'assioma {a} e per il teorema a.
??
grazie.
(scusa ma sono ignorante in materia)
ciao

Ed. Guerini scientifica
grazie per le informazioni.
ciao

 c'e' sempre una possibilita che il mio sw possa superare questo limite?
Bho. Il teorema direbbe di no, ma anche questo teorema si basa su delle
premesse. Se vengono a mancare, chi può dirlo? Per esempio, mi risulta non
contempli la fuzzy logic, per cui potresti riuscire ad evitare il teorema se
usi quella in modo proficuo.
Oppure se scopri qualche errore (o una limitazione nella validità) in uno
qualsiasi dei teoremi che fanno da premessa, anche se sembra reggersi su
basi solide.
Nella pratica, però, costruire un SE che riesca a dimostrare TUTTI i teoremi
dimostrabili, sarebbe già un bel lavoro. (Non che non sia già stato fatto,
ovviamente.)
Poi, se ti avanza tempo e voglia, potresti dedicarti a quelli NON
dimostrabili :-)
Ciao
--
Alessandro Monti

cioe' il simbolo {a} e' lo stesso sia per l'assioma {a} e per il teorema a.
Questo e' facile: un assioma fa parte dell'insieme ..degli assiomi :), un 
teorema non necessariamente: quindi per vedere se un teorema X e' un assioma, 
guardi se compare nell'insieme etichettato "Assiomi". Tutto qui. :)
Quindi 'a' e' sia un assioma che un teorema, 'abc' no - e' solo un teorema.
Non e' detto, giusto per precisare, che gli assiomi siano necessariamente 
singoli simboli. Ad esempio, per il sf sopra, posso sostituire 
assiomi: { ac }
e questo nuovo sf avra', ad esempio, 'abcca' tra i suoi teoremi, la cui prova 
(una di quelle possibile) e' "ac -> abcc -> abcca".
-- 
God is Real, unless declared Integer.
ObjectZone - 
http://space.tin.it/computer/csadun/

ventina (o qualcosa di più, non ricordo la lunghezza della dispensa).
Ecco, pero' saltare al TdG senza saper nulla di logica formale e' come voler 
costruire una Ferrari senza saper avvitare un bullone..


(una di quelle possibile) e' "ac -> abcc -> abcca".
Ricapitolando:     assiomi: {a}   se un teorema X compare qui dentro vuol
dire
                                                      che e' stato
dimostrato (?)
                                                     (quindi l'assioma e' un
teorema gia dimostrato?)
                              teorema    -   sarebbe una teoria da
dimostrare
                                                    che si basa sulle regole
e sui simboli di quel s.f.
Non so perche', ma mi si e' accesa una lampadina.  :-)
HOO CAAPIIIITOO !!!!   grazie!  :-)
il discorso m'interessa e mi studiero un po' di logica formale
ciao.
davide U


mi hai illuminato!
questa frase per me vale piu di cento parole.
grazie. :-)
ciao


sono totalmente d'accordo con te almeno su questo punto.
:-)
ciao
davide U

 costruire una Ferrari senza saper avvitare un bullone..
Proprio nulla no, ma neanche tutta.
Posso costruire almeno un go-cart senza essere un ingegnere meccanico,
presumo.
--
Alessandro Monti

 "teorema di incompletezza".
Ma questo teorema di cui non esiste una prova non e' un assioma?
..GG..

>(quindi l'assioma e' un teorema gia dimostrato?)
Se ti fa piacere pensarla così, si.
In effetti, se
a,b -> c
con a, b assiomi e c teorema,
sotto alcune condizioni accade che,
c -> a, b
dove stavolta c è l'assioma, a, b teoremi.
Occhio che devono esserci alcune condizioni, come la necessarietà e la
sufficienza, altrimenti tutto va a farsi friggere.
(ciò equivale a cambiare il sistema formale, anche se di poco)
--
Alessandro Monti

> Ma questo teorema di cui non esiste una prova non e' un assioma?
Per l'appunto. Dovresti aggiungerlo agli assiomi del tuo sistema formale.
Salvo poi scoprire che ce n'è un altro. E poi un altro.
In altre parole, non avrai mai un sistema formale "completo". Ti mancherà
sempre un assioma (infiniti, dunque), ed il tuo sistema formale sarà sempre
incompleto, di qui il nome del teorema di "incompletezza".
Come già detto, tutto cade se tu partissi con un sistema formale con già con
un numero infinito di assiomi, salvo scoprire che in questo caso il tuo
sistema non è un "sistema formale".
In sostanza: se hai un sistema formale, parti da un numero finito di
assiomi, ma vi sono cose vere e false non dimostrabili (non puoi dimostrare
che sono vere o false, ma devi aggiungerle come assiomi), quindi è
incompleto.
Se hai un numero infinito di assiomi, puoi (se scegli bene) avere un sistema
completo, ma non hai un sistema formale.
--
Alessandro Monti

 sono totalmente d'accordo con te almeno su questo punto.
Dai uno sguardo alla logica fuzzy e vedrai che e' molto ma molto simile al
nostro modo di vedere la realta'. Il problema della logica crisp e' che
spesso risulta poco efficace per modellizzare problemi concreti.
Se un agente deve comprendere: "rallenta un po'..." hai idea di come si
faccia ad esprimere tale enunciato utilizzando una logica crisp? Con la
fuzzy e' relativamente semplice assegnare dei pesi diversi a frasi che sono
molto vaghe (perche', in fondo, "un po'" non significa assolutamente nulla).

Mi sembra molto interessante il discorso che hai fatto, almeno per me.
lo faccio diventare un nuovo thread.
Vorrei sapere cosa ne pensano gli altri.
ciao

presumo.
Hm.. che prezzi fai? :)


Ma questo teorema di cui non esiste una prova non e' un assioma?
Alessandro ha gia' detto: :) puoi *aggiungere* il teorema agli assiomi, ma 
allora il tuo s.f. non e' piu' lo stesso. E questo nuovo s.f. ha a sua volta un 
(diverso) teorema non provabile, eccetera.


 Hm.. che prezzi fai? :)
Cinquantamila all'ora, bello.
E considera che non saprei da che parte iniziare, per cui il conto finale
sarebbe piuttosto salato. Perņ credo che riuscirei a costruirlo.
Ciao
--
Alessandro Monti