View Full Version : P != NP
:|
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_preliminary.pdf
ebbene... potremmo essere ad una svolta storica per il mondo dell'informatica.
non oso pensare i risvolti nel settore della crittografia: il minicrypt esisterebbe e molti algoritmi diverrebbero inutili poiché per avere uno schema crittografico forte basterebbe usare il one-time pad (cioé lo XOR) generando la chiave con un PRG crittografico.
aw my gawd.
DanieleC88
09-08-2010, 15:19
Sono molto curioso di sentire i pareri di qualcuno ferrato in materia... purtroppo le mie conoscenze (in particolare matematiche) sono troppo scarse per poter giudicare la dimostrazione come veritiera o no... Aspettiamo il Clay Institute of Mathematics. :D
Il mio cervello è esploso alla 10a riga :asd:
Ma come mai sta cosa proverebbe che non si può simulare il cervello umano?
Perchè noi siamo intuitivamente in grado di risolvere problemi NP?
Misteroh (cit.)
DanieleC88
09-08-2010, 16:19
Boh, forse perché il cervello umano non è deterministico? :D
banryu79
09-08-2010, 16:19
Ma come mai sta cosa proverebbe che non si può simulare il cervello umano?
In un thread di mesi fa in cui si parlava di non mi ricordo più cosa te l'avevo pure detto, tirando fuori il secondo teorema di incompletezza di Godel (per via delle sue implicazioni in problemi di questo tipo), e te mi avevi pure deriso dicendo che lo citavo a muzzo :asd:
(ovviamente sto scherzando, dato che non ho la più pallida idea di cosa si parli nel documento citato, e visto che ho provato a leggerlo mi sono reso conto che la sua comprensione è ben oltre le me attuali conoscenze)
Per gli interessati, i commenti sul paper postati su reddit e hacker news:
http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_np_originally_posted_in/
http://www.reddit.com/r/math/comments/cyt73/p_np/
http://news.ycombinator.com/item?id=1585850
In un thread di mesi fa in cui si parlava di non mi ricordo più cosa te l'avevo pure detto, tirando fuori il secondo teorema di incompletezza di Godel (per via delle sue implicazioni in problemi di questo tipo), e te mi avevi pure deriso dicendo che lo citavo a muzzo :asd:
(ovviamente sto scherzando, dato che non ho la più pallida idea di cosa si parli nel documento citato, e visto che ho provato a leggerlo mi sono reso conto che la sua comprensione è ben oltre le me attuali conoscenze)
Idem :asd:
Comunque mi sembra strano intuitivamente: secondo me gli uomini non "risolvono un problema NP", ma più che altro sono capaci di dire "intutivamente" se una data soluzione è una soluzione del dato problema, e quindi trovarne di altre "simili".
"intuitivamente" significa che non applichiamo davvero un algoritmo da cima a fondo, ma una serie di passi di "pattern matching" inverso, cioè risaliamo per sostituzione da una soluzione trovata faticosamente ad una nuova "simile".
Anche se dopo parecchio training l'operazione di trovare una nuova soluzione diventa naturale e quasi immediata, tra dimostrare l'appartenenza al contrario e trovare tutte le possibili soluzioni passa parecchio :read:
Specie quando sono infinite :asd:
D'altra parte una macchina NP risolve tutti i possibili rami insieme, e non conosco gente che lo sappia fare :D
Quindi IMHO l'AI rimane possibile.
:|
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_preliminary.pdf
ebbene... potremmo essere ad una svolta storica per il mondo dell'informatica.
non oso pensare i risvolti nel settore della crittografia: il minicrypt esisterebbe e molti algoritmi diverrebbero inutili poiché per avere uno schema crittografico forte basterebbe usare il one-time pad (cioé lo XOR) generando la chiave con un PRG crittografico.
aw my gawd.
Se non erro, se P=NP sarebbe stato molto peggio per l'informatica.
infatti, molti degli algoritmi di cifratura che si usano anche su internet basano la propria sicurezza sulla complessità di problemi NP come la fattorizzazione in primi
malocchio
09-08-2010, 23:46
Mi iscrivo... Mizzeca son un centinaio di pagine però...
L'intro è per me incomprensibile, capisco solo che la dimostrazione userà come strumento k-SAT.
L'inizio del primo capitolo sembra promettente.
7 pagine di bibliografia :muro:
banryu79
10-08-2010, 08:20
Per gli interessati, i commenti sul paper postati su reddit e hacker news:
http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_np_originally_posted_in/
Grazie :)
Ad un certo punto però ho cominciato ad interrogarmi sulla sanità mentale dei ricercatori quando ho cominciato, a metà pagina, a leggere scambi di commenti del tipo:
urish
This is R.J. Lipton's blog post from today about this. To the unfamiliar, this is the blog of one of the leading researchers in the field, who is one of those who received the original email.
keeto
Travelling salesmen are at the edge of their seats..
stuhacking
The dining philosophers have put down their forks.
captainAwesomePants
Wait, they had forks? I've been thinking about this completely wrong!
ramenmeal
chopsticks makes much more sense
plbogen
I think you are biased.
pork2001
When faced with tough meat, ordinary knives are useless. Instead I use Occam's Razor which slices it like butter.
captainAwesomePants
Well, that's usually the case, but sometimes I find it necessary to use a more complex device.
pork2001
Then try the new Swiss Army Logic Knife. It has multiple approaches to analysis and fits in your pocket. Not sold to sophomores, and illegal in many Southern States.
cowinabadplace
That's the problem. You stab it with your steely knives, but you just can't kill the beast.
Kontraption
Well they were missing a few forks, so they had to share.
paolog
Phew, at long last I'll be able to pack my knapsack.
...
E via di questo passo :asd:
infatti, molti degli algoritmi di cifratura che si usano anche su internet basano la propria sicurezza sulla complessità di problemi NP come la fattorizzazione in primi
Per la fattorizzazione esiste già l'algoritmo di Shor che da soluzioni in tempo polinomiale. Certo ci mancano i computer quantistici su cui lanciarlo ma si sa che è corretto.
DanieleC88
10-08-2010, 09:20
Certo ci mancano i computer quantistici su cui lanciarlo [...]
:fiufiu:
E via di questo passo :asd:
Sono un branco di simpatici (a volte) nerd :D
Un altro paio di commenti sul paper da parte di uno dei ricercatori più riconosciuti nel campo, sempre per gli interessati:
http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/
Teo@Unix
10-08-2010, 13:37
Ma come mai sta cosa proverebbe che non si può simulare il cervello umano?
Non so capire quel testo.....
però sul tentativo di rappresentare il cervello attraverso un fedele modello ci si lavora e i risultati ci sono: "progetto blue brain".
non so se io sia andato OT.... (probabilmente si) ma io credo che comunque interessarà a molti d'altronde si tratta di informatica unita alla psicologia, ovvero intelligienza artificiale.
non credo che l'obiettivo del progetto sia fuori portata:
http://www.ted.com/talks/henry_markram_supercomputing_the_brain_s_secrets.html
guardatelo, io l'americano così non riesco a capirlo bene se non qualche frase.
Però ho la traduzione fornita da un'amico :cool:
"La nostra missione è quella di costruire un modello computerizzato del cervello umano dettagliato e realistico. Nel corso degli ultimi quattro anni abbiamo dimostrato la fattibiltà del concetto simulando una piccola parte del cervello di un topolino, e adesso stiamo sviluppando ed ingrandendo il progetto per arrivare a simulare il cervello umano.
Perche stiamo facendo tutto ciò? Ci sono tre ragioni principali. La prima, è l'importanza di capire il funzionamento del cervello per progredire nella comprensione della società, ed penso che questo sia un passo fondamentale nell'evoluzione. La seconda ragione è che non possiamo continuare all'infinito a fare esperimenti sugli animali, e dobbiamo integrare tutti i dati e la conoscenza in un modello funzionale. E' come l'arca di Noè o un archivio. La terza ragione è che ci sono due miliardi di persone che soffrono di patologie mentali, ed i farmaci disponibili ad oggi funzionano prevalentemente in modo empirico. Penso che possiamo arrivare ad una soluzione concreta su come trattare patologie mentali.
Già allo stadio in cui siamo possiamo usare il modello computerizzato del cervello per esplorare alcuni aspetti fondamentali del suo funzionamento. Qui a TED, in anteprima, voglio illustrarvi il modo in cui stiamo verificando una delle molte teorie sul funzionamento del cervello. Questa teoria postula che il cervello crei, costruisca una propria versione dell'universo. E proietta questa versione dell'universo, come una bolla, tutt'intorno a noi.
Questo è stato argomento di dispute filosofiche per secoli. Ma, per la prima volta, possiamo veramente studiarlo per mezzo di una simulazione del cervello ponendo domande in maniera sistematica e rigorosa per verificare questa teoria. La ragione per cui la luna appare più grande all'orizzonte è semplicemente che la nostra bolla percettiva non si estende per 380.000 chilometri. Non è abbatanza grande. E così quello che facciamo è paragonare gli edifici all'interno della nostra bolla percettiva, e traiamo conclusioni. Decidiamo che uno è grande, anche se magari non è così grande,
e questo significa è che le decisioni sono ciò che sostiene la nostra bolla percettiva. La tiene in vita. Senza decisioni non ci è possibile vedere, pensare, o provare emozioni. Può essere che crediate che l'anestesia funzioni immergendovi in un sonno profondo, oppure bloccando i recettori in modo da non far sentire dolore, ma in realtà non funziona così. L'anaestesia crea un'interferenza nel cervello, in modo che i neuroni non possano capirsi l'un l'altro. Sono confusi e non ci consentono di prendere decisioni. Così, mentre cercate di decidere su cosa stia facendo il chirurgo mentre vi opera, il chirurgo se ne è già andato. E' a casa a bere il té. (Risate)
Quindi, quando trovate una porta e la aprite, quello che dovete obbligatoriamente fare per percepire, è prendere delle decisioni. Migliaia di decisioni circa le dimensioni della stanza, le pareti, l'altezza, gli oggetti presenti. Il 99 percento di quello che vedete non è quello che entra dagli occhi. E' quello che inferite della stanza. Ecco che si può dire, con certezza, "Penso, dunque sono". Ma non posso dire "tu pensi, quindi sei" perchè tu sei nella mia bolla percettiva.
Possiamo speculare e filosofare a questo proposito, ma non è necessario farlo per i prossimi cento anni. Possiamo porci una domanda molto concreta. "Può il cervello creare una tale percezione?" Ha la capacità di farlo? Ha il materiale per farlo? Ecco quello che vi voglio presentare oggi.
L'universo ha impiegato 11 miliardi di anni per costruire il cervello. Ha dovuto migliorarlo a poco a poco. Ha dovuto aggiungere i lobi frontali, in modo che si possano avere istinti, perchè questi erano necessari per sopravvivere. Ma il progresso più importante è stata la neo-corteccia cerebrale. E' il nuovo cervello che ci serviva. Era necessario ai mammiferi perchè dovevano far fronte all'allevamento della prole, alle interazioni sociali, a funzioni cognitive sofisticate.
Si può pensare che la neo-corteccia sia la soluzione definitiva prodotta dall'universo, per quel che ne sappiamo. E' il pinnacolo, il prodotto finale che l'universo ha prodotto. Ha avuto un tale successo evolutivo che, dal topo fino all'uomo, è cresciuta di un migliaio di volte in termini di numero di neuroni, per arrivare a questo quasi terrificante organo, a questa struttura. E non ha terminato il proprio percorso evolutivo. A tutti gli effetti, la neo-corteccia del cervello umano si sta evolvendo ad un'enorme velocità.
Se fate uno zoom sulla superficie della neo-corteccia scoprirete che è costituita da piccoli moduli processori G5, come in un computer Ma ce ne sono circa un milione Hanno avuto un tale successo nell'evoluzione che quello che abbiamo fatto è stato di moltiplicarli via via, aggiungendone sempre più al cervello fino a non trovare più spazio dentro al cranio Così, il cervello ha cominciato a ripegarsi su se stesso e questa è la ragione per cui la neo-corteccia è così convoluta. Non si sta facendo altro che stipare colonne per poter avere ulteriori colonne neo-corticali per eseguire funzioni sempre più complesse
Dunque potete pensare alla neo-corteccia come ad un enorme pianoforte un pianoforte con un milione di tasti. Ognuna di queste colonne corticali può produrre una nota. La stimolate e produce una sinfonia. Ma non è semplicemente una sinfonia di percezioni. E' una sinfonia del vostro universo, la vostra realtà. Ci vogliono anni per imparare a padroneggiare un pianoforte con un milione di tasti. Ecco perchè bisogna mandare i bambini a buone scuole, sperabilmente fino ad Oxford. Ma non è solo questione di educazione ma anche di genetica. Se siete fortunati, o sapete padroneggiare le vostre colonne corticali potete suonare una sinfonia fantastica.
C'è una nuova teoria sull'autismo chiamata teoria del "modo intenso", che postula che le colonne corticali siano "super colonne" altamente reattive ed super plastiche e così chi è autistico è in grado di creare ed imparare una sinfonia che per noi altri è inpensabile. Ma capirete anche che se c'è qualche disfunzione in una di queste colonne la nota può risultare stonata. La percezione, la sinfonia prodotta, sarà rovinata, e si mostreranno i sintomi della malattia.
Quindi, il Santo Graal per le neuroscienze è capire la struttura delle colonne corticali e non solo nell'interesse delle neuroscienze, ma forse anche per capire la percezione, la realtà, e perfino la realtà del mondo fisico. Quello che abbiamo fatto negli ultimi 15 anni è stato sezionare la neo-corteccia, in modo sistematico. E' un po' come andare a catalogare un pezzo di foresta. Quanti alberi ci sono? Di che forma sono gli alberi? Quanti ce ne sono per ogni tipo? come sono posizionati?
E' qualcosa di più di un catalogare perchè bisogna scoprire e descrivere le regole della comunicazione e le regole della connettività perche ai neuroni non piace connettersi con qualunque altro neurone. Scelgone con attenzione a chi si connettono. Si tratta di qualcosa di più che catalogare anche perchè bisogna costruire dei modelli digitali tridimensionali delle colonne. E noi l'abbiamo fatto per decine di migliaia di neuroni avbbiamo costruito dei modelli digitali di vari tipi dei neuroni che abbiamo trovato. Una volta fatto questo, si può realmente cominciare a costruire la colonna neocorticale.
Ecco, qui stiamo arrotolandone una sull'altra. Ma mentre lo fate, quello che scoprite è che i rami si intersecano in milioni di punti e ad ognuna di queste intersezioni si forma una sinapsi. La sinapsi è il luogo chimico in cui le colonne comunicano tra di loro. E queste sinapsi tutte insieme formano la rete o il circuito del cervello. Il circuito si può considerare come il tessuto del cervello. E quando si pensa al tessuto del cervello, come è fatta la struttura? Qual'è il disegno del tappeto? Potete capire che questo rappresenta una sfida fondamentale per qualsiasi teoria del cervello, ed in particolare per una teoria che dice che c'è una realtà che emerge da questo tappeto, da questo tipo di tappeto con un proprio disegno particolare.
Questo accade perchè il più importante segreto del disegno del cervello è la diversità. Ogni neurone è differente. E' lo stesso in una foresta. Ogni pino è diverso. Ci possono essere molti tipi diversi di alberi ma ogni pino è diverso. E nel cervello è lo stesso. non c'è un neurone nel mio cevello che sia uguale ad un altro, e non c'è un neurone nel mio cevello che sia uguale a uno dei vostri. E i vostri neuroni non saranno posizionati ed orientati esattamente allo stesso modo. Si possono avere più o meno neuroni. Così è molto improbabile che voi abbiate lo stesso tessuto, gli stessi circuiti.
Allora, come è possibile che creiamo una realtà tale che possiamo comprenderci vicendevolmente? Non serve fare speculazioni, Possiamo guardare alle dieci milioni di sinapsi. Possiamo prendere in esame il tessuto e cambiare i neuroni. Possiamo usare neuroni differenti, con differenti variazioni. Possiamo posizionarli in luogi differenti, e orientarli in diversi modi. Possiamo usarne di più o di meno, E quando facciamo tutto ciò scopriamo è che i circuiti in effetti cambiano Ma lo schema di come i circuiti sono disegnati non cambia. Così, il tessuto del cervello, benchè il vostro proprio cervello può essere più piccolo o più grande, può avere svariati tipi di neuroni, svariate morfologie. Abbiamo in comune lo stesso tessuto. Riteniamo che questo fatto sia specifico per ogni specie, il che potrebbe spiegare perchè non possiamo comunicare tra speci diverse.
Allora, facciamolo funzionare. Ma per fare ciò occorre dargli vita. Gli si dà vita con equazioni e formule. Le equazioni che descrivono i neuroni come dei generatori di elettricità furono scoperte da due premi Nobel di Cambridge. Abbiamo le formule che animano i neuroni. Abbiamo anche le formule che descrivono il modo in cui i neuroni raccolgono informazioni, e il modo in cui creano una piccola scarica elettrica per comunicare tra di loro. E quando si arriva alla sinapsi, quello che fanno in realtà, è di causare, letteralmente, uno shock alla sinapsi. E' come uno shock elettrico che libera dei composti chimici.
Abbiamo le equazioni che descrivono anche questo processo. Così possiomo descrivere la comunicazione tra i neuroni. E' solo una manciata di equazioni quella che serve per simulare l'attività della neo-corteccia. Però serve un computer molto potente. In realtà serve un computer portatile per eseguire i calcoli per un solo neurone. Allora servono 10.000 portatili. Bisogna andare all'IBM, e usare un supercomputer, perchè loro sanno come prendere 10.000 laptop e concentrarli nelle dimensioni di un frigorifero. Con questo computer Blue Gene. Possiamo caricare tutti i neuroni, ciascuno sul suo processore, dare l'avvio, e stare a vedere cosa succede. Portare il tappeto magico a fare un giro.
Qui lo attiviamo. E questo ci dà un'idea di ciò che succede nel vostro cervello quando c'é uno stimolo. E' una prima prospettiva. Quando guardate per la prima volta, vi viene da pensare: "Dio mio. Com'è che la realtà viene fuori da lì?" Però in effetti è possibile constuire una realtà particolare anche se non abbiamo istruito questa collona neo-corticale, Ma possiamo chiedere: "dov'è la rosa?" Possiamo chiedere "dove si trova nella corteccia, se la stimoliamo con una foto?" Dove è collocata nella neo-corteccia? Se abbiamo creato questo stimolo, deve trovarsi all'interno.
Possiamo ignorare i neuroni e le sinapsi, e concentrarci solo sull'attività elettrica. Perchè questo è ciò che viene creato. Si generano modelli di attività elettrica. Quando facciamo così per la prima volta vediamo queste strutture fantasmatiche: oggetti fatti di elettricità che compaiono dentro la colonna neo corticale. Sono proprio questi oggetti che contengono tutte le informazioni relative a qualsiasi cosa le abbia stimolate. E quando abbiamo fatto uno zoom su questa realtà, è come un universo vero e proprio.
Il prossimo passo è prendere queste coordiante cerebrali e proiettarle nello spazio percettivo. E facendo ciò si può entrare nella realtà che si è creata da questo pezzo di cervello per mezzo di questa macchina. Quindi, in sintesi, Penso che l'universo possa - possibilmente - aver evoluto un cervello per guardare a se stesso. che può essere un primo passo verso l'auto-coscienza. C'è ancora un sacco di cose da fare per verificare queste teorie, o qualsiasi altra teoria. Ma spero che voi siate almeno parzialmente convinti che non è impossibile costruire un cervello. Possiamo arrivarci in 10 anni, e se ce la facciamo, spediremo a TED, tra 10 anni, un ologramma per tenere la conferenza. Grazie. (Applausi)"
*
Bellissimo wall of text :D
E' proprio come la penso io.
Con la differenza che secondo me, come per emulare un programma non serve emulare i transistor che lo fanno girare, per emulare la mente non serve emulare il cervello.
E' solo che capire in astratto il modello che fa funzionare la mente potrebbe essere un compito troppo difficile per la mente stessa :D
Magari dopo che brute-forzano il problema si riesce a trovare un modo più economico di risolverlo... certo che trovare l'equivalente di miliardi di processori per i soli neuroni (e ci sono 4 volte tante cellule della glia (che non si sa a che servano)) mi sembra un tantino lontano nel tempo :asd:
Magari dopo che brute-forzano il problema si riesce a trovare un modo più economico di risolverlo...
E dire che basterebbe convertire Pi in binario... (http://everything2.com/title/Converting+Pi+to+binary%253A+Don%2527t+do+it%2521)
Teo@Unix
10-08-2010, 15:53
Molti non credono affatto che fra 10 anni saremo in grado di costruire una mente artificiale.
Ma non vedo il perchè, dato che sappiamo oramai tutto sul neurone. Che è l'elemento fondamentale e chiave del cervello.
E' nato un progetto al CERN (CERN Blue Brain Project 2010)
Certo rimangono ancora da capire molte interazioni tra questi, ma come hai letto nel testo, molte spiegazioni avverrano durante le simulazioni.
Inoltre il numero dei neuroni non sembra nemmeno contare più di tanto.
Guarda questo video, dove hanno usato una parte di un cervello di un topo, inoltre fa vedere una stanza per la simulazione detta prima con l'uso di 10.000 uP uno per neurone. :D
http://www.youtube.com/watch?v=RLCT3wU4fek
oppure questa ragazzina sta recuperando tutte le funzioni svolte da un emisfero, il quale è stato asportato.
http://www.facebook.com/l.php?u=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DTSu9HGnlMV0%26feature%3Drelated&h=dedd8
tutto questo per dire quanto il numero dei neuroni non sembra contare come sembrava fino a qualche anno fa.
Ora sono oltre modo OT. :p
La chiave sta nel fatto che non sappiamo come siamo stati creati noi e non conosciamo pienamente il nostro funzionamento... ammesso che di "creazione" si possa parlare.
Noi abbiamo inventato le macchine, noi c'abbiamo fatto una teoria sopra e sempre noi le abbiamo programmate.
Tuttavia c'è qualcosa che evidentemente sfugge, il reverse-engineering del mondo nel suo complesso non è detto che porti a capire come funzioni in realtà (anche se è notevole il fatto che ci siamo creati un modello e siamo riusciti più o meno a far tornare molte cose all'interno di questo modello).
Ho una teoria riguardo al "creazionismo", ma è solo una mia congettura.
[FANTASIA MODE ON]
Per come la vedo io è una gerarchia, in cui un essere a livello X può creare esseri a livello X-1 ma non al suo stesso livello, dove per livello intendiamo livello di intelligenza (per intelligenza prendiamo l'ampia definizione di Hofstadter).
Lo stesso essere umano quando concepisce una creatura non concepisce una creatura della sua stessa età e con il suo stesso progresso mentale (qui entra in gioco l'evoluzione).
Può essere vista come una forzatura ma a conti fatti è molto simile a ciò che dice Goedel con il suo teorema di incompletezza.
[FANTASIA MODE OFF]
Inoltre c'è da considerare una cosa... bene o male gli esseri umani sono strutturati nello stesso modo, per cui di fatto non basta creare una architettura simile a quella nostra per ottenere una macchina che si comporti nel nostro stesso modo.
In particolare mi viene da pensare che ogni essere umano ha dentro di se un "programma" che lo porta a comportarsi in una maniera piuttosto che in un'altra a prescindere dal suo essere fisico. Chiamatela "mente" o "anima" ma di fatto è un qualcosa non dipendente strettamente dal corpo.
Roger Penrose (http://it.wikipedia.org/wiki/Roger_Penrose) ha teorizzato che in realtà il funzionamento del cervello, in particolare la coscienza di se, abbia a che fare molto con la meccanica quantistica.
Tornando sulla Terra bisogna anche tenere conto che la matematica non perdona, e la teoria della computabilità rimane sempre lì dov'è... esistono funzioni non calcolabili, ovvero la nostra potenza di calcolo (non velocità attenzione) è limitata (e questo varrà anche quando avremo a disposizione computer quantistici e/o biologici).
banryu79
10-08-2010, 17:21
In particolare mi viene da pensare che ogni essere umano ha dentro di se un "programma" che lo porta a comportarsi in una maniera piuttosto che in un'altra a prescindere dal suo essere fisico. Chiamatela "mente" o "anima" ma di fatto è un qualcosa non dipendente strettamente dal corpo.
Se si vuole modellare la mente umana, ci sono degli aspetti da considerare.
Intanto credo sia importante distinguere il fatto che, un conto è tentare di modellare il cervello, che è un oggetto fisico, e misurabile, e un conto è modellare la mente, che, parrebbe, non è qualcosa di *strettamente* fisico, materiale, ma si può immagina come uno o più processi di "alto livello" (ma anche questo è discutibile, ho trovato fonti che sostengono che il processo/processi più che altro sono la riflessione costante nella mente del vissuto, dell'esperito, ovvero la manifestazione di ciò che chiamiamo io; mentre la mente di per se è solo un contenitore).
Sta di fatto però, che la mente umana non è solo dotata di razionalità, ma comprende anche l'emozione, che da sempre ha un ruolo importantissimo nello sviluppo dell'intelligenza.
Il "circuito" dell'emozione non è confinato al solo cervello, ma dipende strettamente da tutto il corpo (e dunque il corpo umano è importantissimo per permettere lo sviluppo di una mente umana).
Questo lo dice la teoria del cervello emotivo (LeDoux, Jhosep).
Se lasciamo fuori questa "fetta" enorme, non stiamo modellando la mente umana, ma qualcos'altro.
E il corpo umano, anche questo, non lo puoi modellare come un unico oggetto: proprio come ci sono tante menti, una diversa dall'altra, ci sono tanti corpi, uno diverso dall'altro, anche se meccanismi e struttura tendono a un qualcosa di comune, facente parte della nostra specie.
Certo, l'argomento è affascinante, ma dannatamente spinoso.
@Tommo: hai letto il post di warduck? vedi che alla fine Godel c'entra :P
@Tommo: hai letto il post di warduck? vedi che alla fine Godel c'entra :P
Si e non cio capito una sega :asd:
Comunque; credo che tu abbia ragione, anche se si riuscisse ad avere un'emulazione di questi processi, staremmo modellando "qualcos'altro".
Il che, secondo la mia tesi, è proprio l'obiettivo a cui puntare :D
Ovvero, ci serve veramente che un programma abbia desideri, un io, delle sensazioni o una località spaziale e temporale, o che sia un'unica unità indivisibile?
In fondo le persone sono "inutili", e un programma uguale ad una persona lo sarebbe ancora di più :D
IMHO è meglio cercare di emulare il cervello nei suoi processi avanzati di smistamento delle informazioni, che
1) è più facile
2) è più utile
Permettendo di rendere "smart" tutti quei processi in cui oggi si è tentati di prendere a manate il computer.
Tipo un SO che possa suggerire cose davvero utili, che anticipi quello che stai pensando adattandosi al tuo tipo d'uso.
O un servizio che inserisce pubblicità ancora migliore a seconda di quello che scrivi o dici al PC.
O un coso che ti dice le scadenze e le ricette possibili da fare con la roba che hai in frigo.
O un attrezzo che guida la macchina.
O che ordina le foto a seconda di che cosa c'è dentro.
Eccetera eccetera... tutte queste attività non presuppongono affatto una AI completa cosciente di sè, ma solo la capacità di relazionare dati provenienti da contesti del tutto diversi.
Io sto provando a realizzarne una ma anche dopo aver semplificato parecchio è tantissima roba...
B|4KWH|T3
10-08-2010, 23:32
La chiave sta nel fatto che non sappiamo come siamo stati creati noi e non conosciamo pienamente il nostro funzionamento... ammesso che di "creazione" si possa parlare.
Noi abbiamo inventato le macchine, noi c'abbiamo fatto una teoria sopra e sempre noi le abbiamo programmate.
Tuttavia c'è qualcosa che evidentemente sfugge, il reverse-engineering del mondo nel suo complesso non è detto che porti a capire come funzioni in realtà (anche se è notevole il fatto che ci siamo creati un modello e siamo riusciti più o meno a far tornare molte cose all'interno di questo modello).
Ho una teoria riguardo al "creazionismo", ma è solo una mia congettura.
[FANTASIA MODE ON]
Per come la vedo io è una gerarchia, in cui un essere a livello X può creare esseri a livello X-1 ma non al suo stesso livello, dove per livello intendiamo livello di intelligenza (per intelligenza prendiamo l'ampia definizione di Hofstadter).
O livello di complessità, astraendoci dal mezzo materiale (neuroni o transistor).
Su queste cose c'è anche un forte dibattito fra riduzionisti (anche "gerarchici", alla Dawkins) e olisti (forse non è il termine più appropriato, ma non mi viene in mente).
Lo stesso essere umano quando concepisce una creatura non concepisce una creatura della sua stessa età e con il suo stesso progresso mentale (qui entra in gioco l'evoluzione).
Può essere vista come una forzatura ma a conti fatti è molto simile a ciò che dice Goedel con il suo teorema di incompletezza.
[FANTASIA MODE OFF]
Io lascerei perdere questo terreno insidioso.
I teoremi di Goedel riguardano un certo tipo di algebre costruite con una logica formale del primo ordine. Stop. E' un teorema di matematica pura.
Qualsiasi deviazione metafisico filosofica è fuori luogo.
Ti consiglio questo (http://www.google.com/search?hl=it&safe=off&&sa=X&ei=fdJhTIrZKt-SOLDl0MEK&ved=0CBMQBSgA&q=tutti+pazzi+per+godel&spell=1) libro
Nel 1930 un ragazzo ventitreenne di nome Kurt Gödel dimostrò un teorema destinato a cambiare per sempre la nostra comprensione della matematica e, forse, di noi stessi: il Teorema di Incompletezza dell'Aritmetica. Questo libro ci guida, e senza presupporre alcuna particolare competenza matematica, nei segreti della leggendaria dimostrazione di Gödel e delle sue controverse implicazioni filosofiche. Francesco Berto mostra come alcuni usi del Teorema oggi invocato in migliaia di siti Internet, in discorsi di politica, religione, sociologia e, naturalmente, ermeneutica e postmodernismo - sorgano da buffi fraintendimenti del risultato gödeliano. E discute le posizioni dei molti nomi celebri del pensiero contemporaneo che hanno sentito il bisogno di dir la loro sul Teorema. Da Wittgenstein al profeta dell'Intelligenza Artificiale Douglas Hofstadter, vincitore del Premio Pulitzer col celebre Gödel, Escher, Bach; dal fisico Roger Penrose, per il quale invece il Teorema di Incompletezza mostra che nessun computer può emulare la mente umana, allo stesso Kurt Gödel, che associò la propria scoperta a un'intuizione puramente intellettuale dell'infinito.
Nella stessa descrizione del libro si afferma che il teorema di Godel ha delle implicazioni che trascendono dalla matematica pura.
Certo la mia era una forzatura, ma il fatto che arrivi ad un punto in cui non puoi dimostrare qualcosa perché usi degli strumenti di cui a loro volta non è stata provata l'efficacia crea una interessante questione.
Noi cerchiamo di spiegare noi stessi (ed eventualmente le nostre creazioni) e il motivo della nostra stessa esistenza, ma queste questioni sono ad un livello evidentemente superiore rispetto a quello in cui ci poniamo.
Mi viene in mente un altro paragone... il principio di indeterminazione di Heisenberg.
Noi siamo osservatori di noi stessi, ed in quanto tali modifichiamo noi stessi (in particolare il nostro pensiero) ogni volta che tentiamo di osservarci.
Di fatto abbiamo bisogno degli altri per darci una identità. Ci osserviamo tra di noi per cercare di spiegare la struttura comune, ma credo sia necessario un livello più alto di comprensione, un osservatore esterno al sistema, per poter rispondere ai nostri dubbi.
In particolare queste considerazioni (ammesso che siano valide, lascio giudicarlo a voi), mi portano a credere che tutto ciò che possiamo creare possa al massimo avere una intelligenza al massimo pari alla nostra, ma non superiore.
banryu79
11-08-2010, 14:33
Nella stessa descrizione del libro si afferma che il teorema di Godel ha delle implicazioni che trascendono dalla matematica pura.
Ma infatti; i teoremi di incompletezza di Godel non parlano della matematica, direttamente, ma dei sistemi formali. Sono dei teoremi limitativi, ovvero precisano le proprietà che i sistemi formali non possono avere.
[1]
Il Primo Teorema di completezza di Gödel dice che:
In ogni teoria matematica T sufficientemente espressiva da contenere l'aritmetica, esiste una formula f tale che, se T è coerente, allora né f né la sua negazione not f sono dimostrabili in T.
Merito di Gödel fu dunque l'aver esibito tale proposizione e la vera potenza di tale teorema è che vale "per ogni teoria affine", cioè per qualsiasi teoria formalizzata, forte quanto l'aritmetica elementare. In particolare Gödel dimostrò che l'aritmetica stessa risulta incompleta: vi sono dunque delle realtà vere ma non dimostrabili.
[2]
Il secondo teorema di incompletezza di Gödel, che si dimostra formalizzando una parte della dimostrazione del primo teorema all'interno del sistema stesso, afferma che:
Sia T una teoria matematica sufficientemente espressiva da contenere l'aritmetica: se T è coerente, non è possibile provare la coerenza di T all'interno di T.
Semplificando molto, significa che nessun sistema coerente può essere utilizzato per dimostrare la sua stessa coerenza.
Fondamentalmente, la dimostrazione del primo teorema consiste nella costruzione, all'interno di un sistema assiomatico formale, di una certa affermazione p a cui si può dare la seguente interpretazione meta-matematica:
p = "Questa affermazione non può essere dimostrata"
Se il sistema formale è coerente, la prova di Gödel mostra che p (e la sua negazione) non possono essere dimostrate nel sistema. Pertanto p è "vera" (p dice che non può essere dimostrata, e non può essere dimostrata) ma non può essere formalmente dimostrata nel sistema. Si noti che aggiungere p all'elenco degli assiomi non aiuterebbe a risolvere il problema: ci sarebbe un'altra, simile affermazione di Gödel costruibile nel il sistema allargato.
Varie (le cito perchè ho trovato qualcosa di interessante su cui riflettere):
Secondo Roger Penrose questa (presunta) differenza tra "ciò che può meccanicamente essere dimostrato" e "ciò che può essere riconosciuto come vero dagli uomini" mostra che l'intelligenza umana non ha una natura algoritmica. Questa convinzione è sottoscritta anche da JR Lucas in Minds, Machines and Gödel.
Questa opinione non è generalmente condivisa perché, come ha sostenuto Marvin Minsky, l'intelligenza umana può commettere errori e può comprendere affermazioni che sono in realtà incoerenti o false. Ciò nonostante, Marvin Minsky ha raccontato che Kurt Gödel gli disse personalmente della sua convinzione nel fatto che gli esseri umani possiedono una modalità intuitiva, non solo computazionale, per arrivare alla verità e che quindi il suo teorema non pone limiti a ciò che può essere riconosciuto come vero dall'uomo.
L'opinione secondo cui il teorema mostrerebbe la capacità degli uomini di trascendere la logica formale può anche essere messa in questione nel seguente modo: non è possibile sapere se l'affermazione p è vera o no, perché non si sa, e non è possibile stabilirlo, se il sistema è coerente. Quindi, in pratica, non è possibile conoscere alcuna verità esterna al sistema. Tutto ciò che si può conoscere è la verità della seguente affermazione:
O p non è dimostrabile nel sistema, oppure il sistema non è coerente.
Questa affermazione può facilmente essere dimostrata all'interno del sistema. Infatti, tale dimostrazione sarà ora schematicamente delineata.
...
Esiste una teoria nota come il "pensiero laterale" (De Bono, Edward) che, a mio avviso, potrebbe presentare delle affinità con quanto evidenziato in italico.
[ovvimaente non è farina del mio sacco la "roba" sui due teoremi di Godel, di cui però ne ho letto sul famoso libro di Hofstader che spiega bene il meccanismo aritmetico-tipografico alla base (dedica un intero capitolo alla faccenda, e i disegni e i vari input a supporto, oltre che all'esame minuzioso dei meccanismi che sottendono la produzione dei teoremi a partire dagli assiomi, la loro formalizzazione in formule valide espresse mediante simboli tipografici, e l'assegnazione di valori ai simboli tipografici stessi per poter poi lavorare con le regole del sitema sul sitema stesso la rendono una lettura impegantiva per i non adetti, ma comunque comprensibile e secondo me soddisfacente rispetto allo scopo di trasmettere il significato e la portata di questi due teoremi)].
Per me la "modalità intuitiva" come ho già detto è pura e semplice associazione di idee basata sul funzionamento del cervello, e può assolutamente essere computatata...
Queste associazioni saltano dei passaggi che la matematica non può affrontare e quindi possono rivelarsi giuste, ma anche sbagliate. Più che altro sono buttate a caso...
solo che siamo 6 miliardi e uno che ci prende lo trovi :D
Scusate il pessimismo :asd:
banryu79
11-08-2010, 15:55
Queste associazioni saltano dei passaggi che la matematica non può affrontare e quindi possono rivelarsi giuste, ma anche sbagliate. Più che altro sono buttate a caso...
Su questo ti sbagli: non sono "buttate a caso" :D (parlo del pensiero laterale).
Dovresti leggerti qualcosa sulle teorie del cervello (ci sono libri divulgativi abbastanza accessibili, la fuori) fin qui citate, se sei incuriosito.
lupoxxx87
11-08-2010, 15:59
tornando un po' più vicini al discorso del P != NP, o meglio, per come la vedevo per quando bazzicavo per via saldini 50, ogni dimostrazione legata alla teoria della complessità, mostra soltanto come le macchine sono limitate rispetto all'uomo.
IMHO:
• P=NP (mi par di ricordare che godel fosse per questa sponda..)
- Una macchina a stati finiti (turing, chomsky, von neumann....) ha le capacità di calcolo per risolvere, a patto di avere il giusto algoritmo di esecuzione e t->∞, ogni problema, compresa la modellazione e simulazione di un cervello biologico.
- C'è bisogno di un differente tipo di macchina (non deterministica/quantistica/biologica) per formulare nuove strutture crittografiche
• P != NP
- Una macchina a stati finiti non è in grado di risolvere determinati problemi. La potenza di calcolo di questa è quindi limitata, seppure la velocità di calcolo non ha limiti apparenti.
- C'è bisogno di un differente tipo di macchina (nd/q/b) per studiare nuovi modelli (AI, logiche non classiche, ...)
oggigiorno un calcolatore si basa sul semplicissimo principio che l'unità atomica di informazione può essere solo 0 o 1. Ma non tutto è sempre vero o falso, e l'algebra di boole non è che un sistema di calcolo.
il fatto che l'algebra di boole copra in modo ottimale la logica classica ci da solo gli strumenti, e le dimostrazioni, per sapere che la logica classica è un sistema consistente e possiamo basarci su di essa per modellare gli algoritmi, ma negli ultimi anni le ricerche in campo di logica si sono riattivate prendendo in considerazione diversi sistemi non classici.
volendola buttare là, è un po' come il discorso sulle geometrie non euclidee vs le euclidee.
su una sfera è lampante che passano ∞ rette per un dato punto, perpendicolari ad una retta esterna al punto, ma provate a spiegare a un muratore che seguendo le linee di due pareti di una casa ci si incontrerà sempre; o che un cerchio e una parabola sono la stessa figura se ammettiamo la chiusura all'infinito dello spazio...
la matematica resterà sempre la madre di tutte le scienze (purtroppo), e il fatto che la sua stessa esistenza non pone limiti all'infinito, lascia infinite porte aperte su ogni questione. Ogni limite, quindi, può essere evitato, magari cambiando semplicemente il proprio punto di vista
tornando un po' più vicini al discorso del P != NP, o meglio, per come la vedevo per quando bazzicavo per via saldini 50, ogni dimostrazione legata alla teoria della complessità, mostra soltanto come le macchine sono limitate rispetto all'uomo.
IMHO:
• P=NP (mi par di ricordare che godel fosse per questa sponda..)
- Una macchina a stati finiti (turing, chomsky, von neumann....) ha le capacità di calcolo per risolvere, a patto di avere il giusto algoritmo di esecuzione e t->∞, ogni problema, compresa la modellazione e simulazione di un cervello biologico.
- C'è bisogno di un differente tipo di macchina (non deterministica/quantistica/biologica) per formulare nuove strutture crittografiche
• P != NP
- Una macchina a stati finiti non è in grado di risolvere determinati problemi. La potenza di calcolo di questa è quindi limitata, seppure la velocità di calcolo non ha limiti apparenti.
- C'è bisogno di un differente tipo di macchina (nd/q/b) per studiare nuovi modelli (AI, logiche non classiche, ...)
Ma non e' una questione di possibilita', ovvero di essere o non essere in grado di risolvere un problema.
Noi siamo gia' in grado di risolvere TUTTI i problemi classificati, che siano essi classificati come P, NP, NP-Hard o NP-completo, e sempre in tempo finito.
Le nostre macchine hanno gia' la potenza necessaria per farlo.
Il problema e' il come.
E' possibile risolvere anche il postino cinese o il commesso viaggiatore anche ora, anche dato il problema come NP-Completo.
Semplicmente ci mettiamo "alla peggio" un tempo esponenziale rispetto ai dati in ingresso. Che comunque significa che riusciamo a risolverlo, e in tempo finito.
I.E. enumero tutti i possibili percorsi (che sono un insieme esponenziale del numero di punti in ingresso), ne calcolo le loro lunghezze e scelgo il minore. Saro' quindi sicuro di avere trovato il percorso piu' breve, e l'avro fatto in tempo finito seppur lungo.
lupoxxx87
12-08-2010, 10:08
era imho proprio per questo...
a questo punto sollevo una piccola questione :p
una soluzione ad un dato problema P in tempo non polinomiale è valida?
a mio parere no, non l'accetterei come valida.
la riconoscerei, senza dubbio, come soluzione, ma non la accetterei come una soluzione valida al problema.
Quello che intendevo, a grandi linee, è che la dimostrazione di una delle due equazioni traccerebbe comunque dei limiti alle MdT. Dei limiti di cui si è sempre saputa l'esistenza, ma non si è mai riusciti a delineare le fattezze di questi limiti.
Nb che dico che nel caso di p=np una MdT classica avrebbe le potenzialità per modellare e simulare un cervello biologico, ma non di equipararlo.
Le teorie su calcolatori biologici e quantistici restano sempre aperte e dibattute, soprattutto finchè il principio di heisemberg (per quelli quantistici) resterà valido, e le potenzialità teoriche di un cervello umano restano ancora incalcolabili
Ma non e' una questione di possibilita', ovvero di essere o non essere in grado di risolvere un problema.
Noi siamo gia' in grado di risolvere TUTTI i problemi classificati, che siano essi classificati come P, NP, NP-Hard o NP-completo, e sempre in tempo finito.
Le nostre macchine hanno gia' la potenza necessaria per farlo.
Il problema e' il come.
E' possibile risolvere anche il postino cinese o il commesso viaggiatore anche ora, anche dato il problema come NP-Completo.
Semplicmente ci mettiamo "alla peggio" un tempo esponenziale rispetto ai dati in ingresso. Che comunque significa che riusciamo a risolverlo, e in tempo finito.
I.E. enumero tutti i possibili percorsi (che sono un insieme esponenziale del numero di punti in ingresso), ne calcolo le loro lunghezze e scelgo il minore. Saro' quindi sicuro di avere trovato il percorso piu' breve, e l'avro fatto in tempo finito seppur lungo. be', non esageriamo :D
ci sono dei problemi che proprio non riusciamo a risolvere e basta. per esempio non riusciamo a trovare una dimostrazione o un controesempio per la congettura di Goldbach. potremmo cercare di usare anche li la forza bruta in cerca di un controesempio, ma se la congettura é vera la ricerca non avrebbe fine.
be', non esageriamo :D
ci sono dei problemi che proprio non riusciamo a risolvere e basta. per esempio non riusciamo a trovare una dimostrazione o un controesempio per la congettura di Goldbach. potremmo cercare di usare anche li la forza bruta in cerca di un controesempio, ma se la congettura é vera la ricerca non avrebbe fine.
Certo. Ma un problema del quale non sappiamo se ci sia o meno una soluzione non e' P o NP. Per definizione i P o NP sono risolvibili.
Il vero problema degli NP e' capire se c'e' una soluzione di riduzione polinomiale di questa classe di problemi, che altrimenti verrebbe risolta (ma comunque risolta) alla peggio in tempi esponenziali.
I problemi dei quali non sappiamo se c'e' o meno una soluzione potrebbero non essere affatto risolvibili, e pertano nessuna macchina, che sia deterministica o meno, potra' farlo.
banryu79
12-08-2010, 15:35
I problemi dei quali non sappiamo se c'e' o meno una soluzione potrebbero non essere affatto risolvibili, e pertano nessuna macchina, che sia deterministica o meno, potra' farlo.
Scusa, non vorrei confodermi e chiedo conferma: equivale a dire che la soluzione alla domanda "E' questo problema risolvibile?" per questa classe di problemi non è computabile?
lupoxxx87
12-08-2010, 15:47
Scusa, non vorrei confodermi e chiedo conferma: equivale a dire che la soluzione alla domanda "E' questo problema risolvibile?" per questa classe di problemi non è computabile?
non vorrei sbagliarmi io...
ma mi pare che la risolvibilità di un problema è ben lontana dal modo e dal tempo in cui questo viene risolto, e se non mi sbaglio, ogni problema formulabile in un algebra eterogenea ammette soluzione dentro all'algebra stessa, e questo viene dalla matematica.
l'informatica invece si occupa di studiare gli algoritmi per risolvere questi problemi con complessità determinabili in funzione della grandezza dell'input.
le congetture (goldbach, riemann, collatz, ...) spesso trattano proprietà dei numeri (essere primo, essere pari, ...) e per questo sono difficili da dimostrare
B|4KWH|T3
12-08-2010, 18:00
Ma infatti; i teoremi di incompletezza di Godel non parlano della matematica, direttamente, ma dei sistemi formali. Sono dei teoremi limitativi, ovvero precisano le proprietà che i sistemi formali non possono avere.
Questa affermazione non mi è chiara :mbe:
Logica Matematica (http://en.wikipedia.org/wiki/Mathematical_logic)
Varie (le cito perchè ho trovato qualcosa di interessante su cui riflettere):
Esiste una teoria nota come il "pensiero laterale" (De Bono, Edward) che, a mio avviso, potrebbe presentare delle affinità con quanto evidenziato in italico.
[ovvimaente non è farina del mio sacco la "roba" sui due teoremi di Godel, di cui però ne ho letto sul famoso libro di Hofstader che spiega bene il meccanismo aritmetico-tipografico alla base (dedica un intero capitolo alla faccenda, e i disegni e i vari input a supporto, oltre che all'esame minuzioso dei meccanismi che sottendono la produzione dei teoremi a partire dagli assiomi, la loro formalizzazione in formule valide espresse mediante simboli tipografici, e l'assegnazione di valori ai simboli tipografici stessi per poter poi lavorare con le regole del sitema sul sitema stesso la rendono una lettura impegantiva per i non adetti, ma comunque comprensibile e secondo me soddisfacente rispetto allo scopo di trasmettere il significato e la portata di questi due teoremi)].
Qui entriamo nel campo delle opinioni però.
Io volevo semplicemente sottolineare la differenza fra ciò che riguarda i teoremi di Godel in senso stretto e ciò che è divagazione.
B|4KWH|T3
12-08-2010, 18:05
era imho proprio per questo...
a questo punto sollevo una piccola questione :p
una soluzione ad un dato problema P in tempo non polinomiale è valida?
a mio parere no, non l'accetterei come valida.
la riconoscerei, senza dubbio, come soluzione, ma non la accetterei come una soluzione valida al problema.
Quello che intendevo, a grandi linee, è che la dimostrazione di una delle due equazioni traccerebbe comunque dei limiti alle MdT. Dei limiti di cui si è sempre saputa l'esistenza, ma non si è mai riusciti a delineare le fattezze di questi limiti.
Nb che dico che nel caso di p=np una MdT classica avrebbe le potenzialità per modellare e simulare un cervello biologico, ma non di equipararlo.
Le teorie su calcolatori biologici e quantistici restano sempre aperte e dibattute, soprattutto finchè il principio di heisemberg (per quelli quantistici) resterà valido, e le potenzialità teoriche di un cervello umano restano ancora incalcolabili
Mi sa che stai confondendo il problema di P?=NP con quello della calcolabilità
B|4KWH|T3
12-08-2010, 18:09
Scusa, non vorrei confodermi e chiedo conferma: equivale a dire che la soluzione alla domanda "E' questo problema risolvibile?" per questa classe di problemi non è computabile?
Credo, ma non vorrei dire una cazzata, che (tanto per ritornare a Godel) dipende dal sistema formale in cui sei.
Questo forse può aiutare: http://en.wikipedia.org/wiki/Undecidable_problem
Mbe al di là delle speculazioni...
ma allora st'indiano c'ha ragione o no alla fine :D
Non ho visto riscontri da nessuna parte...
Da quello che ho letto ci sono dubbi in un paio di passaggi (non hanno detto che siano errati). Se riescono a dimostrare che quei passaggi sono validi allora abbiamo la dimostrazione.
banryu79
13-08-2010, 08:53
[OT]
Questa affermazione non mi è chiara :mbe:
Logica Matematica (http://en.wikipedia.org/wiki/Mathematical_logic)
Volevo solo evidenziare il fatto che il teorema di incompletezza di Godel riguarda più propriamente i sitemi formali di un certo tipo.
L'aritmetica è uno di questi, il che "tira dentro" tutte le teorie matematiche che si reggono su questo sistema formale.
In particolare, il teorema di incompletezza di Godel ci racconta qualcosa a proposito di una delle proprietà fondamentali dei sistemi logici formali, la completezza. (vedi qui (http://en.wikipedia.org/wiki/Logic#Consistency.2C_validity.2C_soundness.2C_and_completeness)).
Tutto qua.
Comunque, per gli interessati, tanto per mettere un po' in prospettiva le cose:
[link alla pagina (http://en.wikipedia.org/wiki/Hilbert%27s_program)]
Gödel showed that most of the goals of Hilbert's program were impossible to achieve, at least if interpreted in the most obvious way. His second incompleteness theorem stated that any consistent theory powerful enough to encode addition and multiplication of integers cannot prove its own consistency. This wipes out most of Hilbert's program as follows:
* It is not possible to formalize all of mathematics, as any attempt at such a formalism will omit some true mathematical statements.
* An easy consequence of Gödel's incompleteness theorem is that there is no complete consistent extension of even Peano arithmetic with a recursively enumerable set of axioms, so in particular most interesting mathematical theories are not complete.
* A theory such as Peano arithmetic cannot even prove its own consistency, so a restricted "finitistic" subset of it certainly cannot prove the consistency of more powerful theories such as set theory.
* There is no algorithm to decide the truth (or provability) of statements in any consistent extension of Peano arithmetic. (Strictly speaking this result only appeared a few years after Gödel's theorem, because at the time the notion of an algorithm had not been precisely defined.)
Credo, ma non vorrei dire una cazzata, che (tanto per ritornare a Godel) dipende dal sistema formale in cui sei.
Questo forse può aiutare: http://en.wikipedia.org/wiki/Undecidable_problem
Grazie del link, mi ha aiutato a chiarire dei termini e alcuni aspetti che prima ignoravo e su cui facevo confusione :)
Mbe al di là delle speculazioni...
ma allora st'indiano c'ha ragione o no alla fine :D
Non ho visto riscontri da nessuna parte...
http://rjlipton.wordpress.com/
Su questo blog puoi seguire la diatriba al bleeding-edge :D
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.