i(n)naturali
Ho procrastinato questa serie di post troppo a lungo, e alla fine la discussione che ne doveva scaturire è già iniziata [qui] e [qui]. Manca ancora la premessa. Che tenterò di scrivere in troppe parole semplici piuttosto che tante parole difficli, per motivi di ecologia mentale. Per cui anche quei testoni che saltano a pié pari i post scientifici questa volta non hanno scusanti (lussu, ce l’ho con te). Premessa necessaria: queste sono speculazioni pre-scientifiche personali dell’autore, che si impegna a studiare meglio la questione e a porre domande veramente pertinenti (ora devo: è arrivato questo).
Enumerare i naturali
Per parlare dei reali dobbiamo prima fare un excursus sugli altri insiemi numerici. Non daremo per scontato neanche l’insieme N dei naturali. N è l’insieme dei numeri che si usano per contare:
0, 1, 2, 3 …
e ovviamente contiene infiniti elementi. Infinito quanto? Si dice un infinito numerabile, ed ogni insieme che può essere messo in relazione uno-ad-uno (biunivocamente) con l’insieme dei numeri naturali si dice un insieme numerabile, nel senso primitivo della parola enumerare. Infatti anticamente per conteggiare il numero di pecore in un gregge si metteva un sassolino (calcolo) in un sacchetto, e al ritorno dal pascolo si calcolava se le pecore erano tante quante quelle che erano uscite. Si stabiliva cioè una relazione biunivoca tra i sassi e le pecore. Dopodiché il fanatismo islamico ci ha infettato con la mania dei numeri naturali e abbiamo imparato a contare "uno-due-tre-quattro…" senza aver più bisogno dei calcoli. Questo è vero in senso pratico, ma anche formale: i numeri naturali sono assiomatizzati partendo dallo zero e costruendoli uno ad uno con la funzione "successore" (assiomi di Peano).
Questa è precisamente la nozione che ci è rimasta di enumerazione: stabilire una relazione biunivoca, ed un insieme si dice numerabile se esiste una relazione biunivoca con l’insieme dei numeri naturali. Per esempio sono numerabili i numeri interi Z (naturali di ambo i segni). Posso infatti costruire questa relazione uno ad uno tra gli interi e i naturali:
0 -> 0
1 -> 2 -1 -> 1
2 -> 4 -2 -> 3
… …
che manda gli interi positivi nei naturali pari e gli interi negativi in quelli dispari. Per ognuno del primo insieme ve n’è uno del secondo e viceversa, per cui l’infinità di Z è la stessa di N (anche se intuitivamente i primi sono "il doppio" dei secondi).
Perché sono così pedante? Perché non è detto che se esiste una relazione biunivoca, questa si possa effettivamente mostrare. La cosa può apparire sorprendente, sapere che una cosa c’è e non poterla vedere. Il fascino della matematica del ‘900 è che ha imparato a trattare le cose formalmente, immergendole nel loro spazio di residenza, senza sporcarsi le mani. Per cui, ad esempio, è possibile mostrare che un certo problema non ha risposta, senza bisogno di smanettare con il problema stesso. Può succedere pertanto che ci siano numeri naturali numerabili che non si possono enumerare! Chiarisco.
Il numero più grande
[più che ispirato da qui]
Chi la spara più grossa, ovverosia chi sa dire il numero più glande? Avrete sicuramente giocato a questo gioco da bambini. Regole: il numero deve essere un numero naturale, e ben definito: un matematico deve saperlo riconoscere. Non può essere "infinito", e non può essere "uno più del tuo"; e non può neanche essere "il numero di particelle nell’universo" (anche perché non conviene). Partiamo: dieci, cento, millemilioni! Chi vince? Il più furbo. Quello, per esempio, che comincia ad usare le potenze: "dieci alla cento" (anche detto googol). Più furbo di lui è quello che dice "dieci alla dieci alla cento" (googolplex). Attenzione: questo numero è già più grande di qualsiasi numero fisicamente sensato. Infatti in fisica parliamo di ordini di grandezza, potenze del dieci: tra lo yocto e lo yotta, passando per il femto, il nano, il micro, il kilo, il giga, il tera, ci sono 48 ordini di grandezza (dieci alla quarantotto). Il numero di particelle nell’universo è stimato intorno a 10^85. Quando si comincia a frequentare ordini di grandezza importanti non ha senso porsi problemi sulle singole unità. Chi compra una villa da 20 milioni di euro difficilmente sarà preoccupato per 20 euro di marca da bollo. Ma quando uno dice "dieci alla dieci alla dieci", perfino l’ordine di grandezza è negligibile. Siamo veramente molto in alto!
Più furbo ancora è quello che si inventa una nuova operazione. Come il prodotto è una notazione breve per successive somme, e la potenza è una notazione breve per prodotti ripetuti, si può definire una notazione compatta per le potenze ripetute (tetrazione, che indiciamo con #), e poi via via si possono definire operazioni computabili che sparano sempre più in alto. Un esempio di notazione compatta per queste operazioni è la notazione di Steinhaus-Moser. Altre notazioni concise per arrivare veramente in alto sono la notazione di Knuth, con la quale si può scrivere il numero di Graham g_64, fino ad un po’ di tempo fa il più alto numero naturale mai definito che fosse la risposta ad un qualche quesito matematico che non fosse "scrivere il numero più alto", cioè che comparisse in maniera naturale da qualche parte in matematica (curiosamente, è la risposta più vicina che si è riusciti a dare ad un problema la cui risposta congetturata si ritiene essere semplicemente 6).
Numeri molto grandi si ottengono quindi definendo funzioni computabili che, dato in pasto un numero, cominciano a sommarlo, moltiplicarlo, elevarlo, superelevarlo etc. etc. fino ad ottenere numeri stratosferici. Computabile significa che in teoria, disponendo di sufficiente tempo, dando in pasto ad una macchina di Turing (un computer) le istruzioni per calcolare il numero, questa prima o poi ve lo sputa fuori. Il problema casomai è che non ci sarebbe spazio per scriverlo: se l’Universo è finito, è al più fatto di quantità grandi "ordini di grandezza" di cose su cui scrivere, e già un numero con un googolplex di cifre non ci sta. Una simile funzione computabile è la funzione di Ackermann A(n), definita in questo modo:
A(1) = 1 + 1
A(2) = 2 * 2 = 2 + 2
A(3) = 3^3 = 3 * 3 * 3
A(4) = 4#4 = 4^4^4^4
A(5) = pentazione(5) = 5#5#5#5#5
…
Il numero XKCD definito da A(g_36) (funzione di Ackermann valutata sul numero di Graham) è il numero computabile più grande e conciso che possiate menzionare se volete vincere la gara. La funzione di Ackermann non è altro che la formalizzazione matematica della megalomania più sfrenata: quando immaginiamo di abbracciare il tutto e superarlo, e di superare il superamento del tutto, e ancora e ancora, quando visualizziamo una quantità e la facciamo diventare risibile per arrivare ad una nuova quantità risibile, stiamo ideando una procedura ricorsiva che tende a superare ogni grandezza concepibile, eppure lo stiamo facendo costruttivamente, computabilmente. Ci rimane sempre il dubbio che non ci sia qualcosa di ancora più grande, inafferrabilmente più grande.
Il lavoratore industrioso
Esiste qualcosa di inafferrabilmente più grande? In effetti si, esiste una funzione che cresce più velocemente di qualsiasi funzione computabile. Pensavate di aver vinto con A(g_36), ed invece c’è qualcuno di più cazzuto di voi. Ed anche più stronzetto. Perché lui sfodera una funzione che definisce in maniera implicita, ma assolutamente ben definita, numeri naturali talmente grandi da non essere computabili (casomai potete far ricorso in cassazione sulla corretta interpretazione del regolamento). Questa funzione cresce più velocemente di qualsiasi esponenziazione, tetrazione, graham-izzazione. Si chiama busy-beaver. Il concetto è questo. Un qualsiasi programma lungo M istruzioni su computer può portare a termine il suo compito dopo un certo numero di computazioni, per quanto lentamente (Linux), oppure entrare in loop e inchiodarsi (Windows). Ma non è possibile costruire un super-programma che giri sullo stesso computer e che sappia prevedere, per ogni dato programma con M istruzioni, se questo si fermerà o andrà avanti all’infinito*. Non possiamo costruire un super-programma che ci predica il destino di un qualsiasi programma. Questo è uno dei grandi risultati della matematica del ‘900 (halting problem), versione computazionale del teorema di Goedel.
Ora definiamo questa funzione: BB(M) (busy beaver) è la funzione che ci dice il massimo di computazioni che un generico programma con M istruzioni iniziali può performare, purchè prima o poi si arresti. Tra tutti i programmi di M istruzioni che si fermano, BB(M) ci dice quanto avanti va quello che si ferma più tardi. Ebbene: noi non possiamo inventare un programma che dato M ci dica BB(M), ovverosia BB(M) non è computabile, perché se potessimo computarla potremmo risolvere l’halting problem. Non sarebbe infatti difficile costruire un super-programma che per un dato programma di M istruzioni di cui vogliamo conoscere il destino calcola BB(M) e lascia correre il programma fino a che non ha performato BB(M) computazioni; se non si è ancora fermato, da definizione di BB(M) allora sapremmo che il programma continuerà all’infinito, ed avremmo risolto l’halting problem.
Confusi? OK, dimenticate il paragrafo sopra. Quello che importa è che esiste una funzione che definisce precisamente numeri naturali non computabili, ovverosia un computer non potrebbe enumerare tutti i numeri generati dalla funzione busy-beaver uno per uno. Questo non vuol dire che singoli valori siano inconoscibili, e non vuol dire neanche che i numeri naturali non siano enumerabili. I numeri busy-beaver, per definizione, per quanto grandi verranno raggiunti da un programma che conta 1,2,3…, ma questo stesso programma non saprà dirvi se il numero che sta contando è busy-beaver o no. Si giunge a questa conseguenza, sbalorditiva:
esistono insiemi numerabili non enumerabili
Per esempio l’insieme dei numeri busy-beaver, perfettamente definito con finita informazione (i 12000 caratteri di questo post sono sufficienti e ridondanti), è in relazione univoca con i naturali:
M -> BB(M)
e pertanto è al più numerabile (la biunivocità è garantita se la successione BB(M) è dimostrata crescente) eppure non è enumerabile, nel senso appena detto. Notiamo la peculiarità della definizione di questi numeri: essa si basa sulle specifiche di programmi che calcolano numeri, e quindi è una definizione meta-logica. Se per costruire la somma dobbiamo dire "prendi M e aggiungi M", per costruire BB(M) dobbiamo dire "prendi un programma di M istruzioni…". Per costruire questo esempio ben definito e astruso, abbiamo dovuto cambiare livello semantico.
Adesso voi direte: vabbeh questo non vuol dire nulla. Hai solo detto che le macchine di Turing non possono enumerare tutti gli insiemi numerabili. Ma attenzione: non ho mai veramente fatto uso del fatto che la macchina fosse di Turing; ho solo supposto che elaborasse finita informazione iniziale (N bits) a passi discreti. Per tanto il concetto è che
esistono modelli dei numeri naturali che non sono enumerabili da nessun algoritmo che contiene finita informazione
Continueremo con i numeri razionali e reali nei prossimi post, ora una divagazione.
Loosing my religion
Concludo con un tocco di religione. Al momento io credo (fideisticamente) che la congettura di Riemann sia indimostrabile. Lo credo perché i numeri primi sono il mistero ultimo della matematica, e la congettura di Riemann il distillato di questo mistero. Una sua risoluzione sarebbe un evento tristissimo, come la morte. Ma la matematica sopravviverà all’uomo. Quindi credo. La mia fede è supportata da questo indizio: i numeri primi giocano un ruolo di primo piano nella dimostrazione del teorema di incompletezza, consentendo la numerazione di Goedel delle proposizioni. Mi parrebbe assurdo che questo fosse un caso. Secondo me è un chiaro indizio della loro colpevolezza: se permettono di dimostrare l’incompletezza, allora essi stessi incarnano questa incompletezza.
Personalmete fantastico addirittura di una dimostrazione di indimostrabilità/non-refutabilità, basata sulla violazione del teorema di Goedel. Ma, c’è un grosso ma. Come rileva anche Chaitin (qui), una dimostrazione di non-refutabilità sarebbe una prova, dato che la congettura riguarda un insieme numerabile. Se dimostro che non posso trovare un caso contrario, dimostro il teorema. Nulla vieta che si possa dimostrare l’indimostrabilità, una sorta di teorema dimezzato. Ma c’è un altra opzione, e qui diventa fantastascienza sfrenata: che si possa dimostrare che non è rintracciabile un caso contrario computabile. Insomma un risultato del tipo: non possiamo sapere se l’ipotesi è vera, ma non troveremo mai un caso contrario, perché se c’è non è computabile. Non sarebbe fico?
* A proposito dell’halting problem, non so se esista un risultato che dice che ogni macchina di Turing che va avanti all’infinito entri in loop, e quindi che ogni macchina di Turing elabora numeri razionali periodici (loop) o troncati (halt), ossia numeri di informazione comunque finita, quanta è l’informazione dei bits iniziali. La cosa mi sembrerebbea molto sensata.
Non ho (ancora) letto il link a Chaitin che citi, ma per “dimostrazione di indimostrabilità” intendi una dimostrazione di indecidibilità? In tal caso mi pare di ricordare che si possa benissimo dimostrare l’indecidibilità di un teorema di esistenza per numeri naturali (esiste un numero tale che…) affrontando a testa alta l’obiezione “se dimostro che non posso trovare un caso contrario, dimostro il teorema.” E la soluzione, per quel che ricordo, sta nel fatto che il concetto di numero naturale è “inchiodato” solo dagli assiomi di peano, per cui resta un’ampia variabilità nel “modello” di numeri naturali da scegliere. Detto in altri termini, l’indecidibilità di un teorema di esistenza si interpreta come: puoi sceglire una definizione di numero naturale (i.e. aggiungendo un ulteriore particolare assioma a quelli di peano) per cui il numero di cui parla il teorema esiste, e poi sceglierne un’altra (negando l’assioma di prima) in cui quel numero non esiste.
Ti torna?
Comment by hronir — March 8, 2009 @ 8:28 am
Si intendo indecidibilità, ma non necessariamente in entrambi i sensi di marcia, per questo distinguo indimostrabilità e non-refutabilità. Anche l’indecidibilità dell’ipotesi del continuo nel sistema ZF+C è stata dimostrata in due tempi, prima da Goedel e poi da Cohen.
Non ho mai sentito questa cosa di cui parli, sarei interessato a vederla, hai qualche link? Stai dicendo che aggiungendo diversi assiomi a quelli di Peano si possono individuare modelli isomorfi ai naturali ma in cui non valgono gli stessi teoremi?
Io invece resto attaccato al sistema di Peano, e in particolare all’assioma di induzione, e favoleggio della possibilità che non-refutabilità possa voler anche dire che se un controesempio esiste, questo non si possa mai vedere, come non posso mai vedere la numerazione di Goedel della proposizione “questa proposizione non è decidibile” o “questa teoria è consistente”.
Comment by Administrator — March 8, 2009 @ 9:10 am
Ciao tomate,
tutto il tuo ragionamento è affascinante, ma non mi convince per nulla. Quello che alla fine si ottiene è che esistono insiemi di naturali non computabili, cioè che non sono l’insieme di output di alcuna macchina di Turing; ma questo non mi sorprende perchè i possibili output di macchine di Turing sono numerabili; infatti esistono una quantità numerabile di macchine di Turing. Invece, l’insieme potenza dei numeri naturali è più che numerabile. È quindi ovvio che esistono insiemi di naturali che non sono computabili.
Poi non capisco cosa intendi precisamente con “esistono modelli dei naturali non numerabili”: ti riferisci alla teoria dei modelli? Oppure usi il termine “modello” in senso intuitivo e/o generico?
Comment by Stefano — March 8, 2009 @ 9:31 am
> l’insieme potenza dei numeri naturali è più che numerabile. È quindi ovvio che esistono insiemi di naturali che non sono computabili
Si, infatti non volevo dire altro che questo, cosa ovvia. Hai riassunto benissimo il senso del post: ci sono numerabili macchine di Turing, e non numerabili insiemi di naturali: la maggior parte di questi non saranno computabili. Non penso di aver detto niente di più, ho solo coniato (senza definirla, pardon) l’espressione “enumerare”, distinta da “numerare”, per intendere “esiste un algoritmo finito che li mette in fila”. A parte qualche improprietà lessicale, a meno di svarioni non credo che ci sia nulla di non ordinario.
Credo di non aver scritto da nessuna parte “modelli dei naturali non numerabili”, ma solo “non e-numerabili”.
Comment by Administrator — March 8, 2009 @ 9:41 am
Non sono sicuro di aver capito a quali sensi di marcia tu ti riferisca (non-refutabilità come dimostrazione di non poter dimostrare l’esistenza? e l’altro senso sarebbe una dimostrazione di non poter dimostrare la non-esistenza? mi perdo…)
Del resto quando parlo dell’indecidibilità di Goedel mi sembra sempre di barcollare sul filo della (mia presunta) comprensione, per cui è molto probabile che ti riferisca a qualcosa che mi manca…
Quanto alla cosa che dicevo, non ho link (sottomano) e ho anche idee vaghe. Queste idee vaghe, ad esempio, interpretano nel modo seguente la proposizione G del teorema di goedel:
G: non esiste alcun numero naturale che nella numerazione di goedel corrisponda alla dimostrazione di questa stessa proposizione G.
Cioè G, letta a un certo livello, parla dell’esistenza di un numero (la dimostrazione di G): se quel numero esistesse davvero (mi pare di capire sia una parte della tua argomentazione) si avrebbe una contraddizione, dunque nessuno potrà mai mostrarmi quel numero. Ma siccome non è possibile dimostrare che quel numero non esiste, è possibile aggiungere agli assiomi di peano l’assioma: esiste un numero naturale g che corrisponde alla dimostrazione di G (ovviamente g non può essere un numero naturale “usuale”). Se non sbaglio, una possibilità che contempla questo g è quella di “estendere” il concetto di numero naturale a includere numeri “inifiti”, i cui inversi sono gli “infinitesimi” dell’analisi non standard.
Probabilmente Stefano ne sa molto di più sull’analisi non-standard…
Comment by hronir — March 9, 2009 @ 1:32 pm
Dunque, come naturale quando ci si addentra in queste cose a volte e’ difficile capirci. Ti scrivo qualche nota che non so se corrisponda.
Per “senso di marcia” intendo semplicemente che se dico che una proposizione e’ indecidibile, dico che non puo’ essere ne’ dimostrata ne’ confutata, ma in questo caso e’ necessario dividere i due casi (sensi di marcia) perche’ una dimostrazione di inconfutabilita’ dell’ipotesi di Riemann coinciderebbe con una sua dimostrazione.
Quanto alla numerazione di Goedel, ho volutamente evitato di entrarci troppo a fondo e ho preferito parlare di macchine di Turing che esprimono gli stessi concetti in maniera piu’ semplice. Piuttosto di scomodare la tua proposizione G su cui faccio fatica a concentrarmi, guarderei quella originale:
G: “questa proposizione non e’ dimostrabile”
Goedel ha mostrato che esiste una numerazione di Goedel per G e che questa proposizione assume un valore di verita’ ben definito. D’altra parte questa numerazione non e’ conoscibile in quella stessa teoria, perche’ se la potessimo conoscere avremmo dimostrato la proposizione. Potremmo aggiungerla tra gli assiomi ed ottenere altre proposizioni di Goedel.
Non ho invece capito la tua ultima frase. La numerazione di G e’ pur sempre un numero finito; tu stai parlando di aggiungere gli ordinali transfiniti agli assiomi di Peano?
Comment by Administrator — March 9, 2009 @ 3:01 pm
@hronir: non è esattamente così che Hofstadter introduce i numeri non standard? Mi ricordo vagamente che ne parla in GEB. D’altra parte, leggendo il primo capitolo di Robinson (”Non standard analysis”) e spulci un po’ fra i riferimenti bibliografici, scopri che in effetti la NSA ha molto a che fare col teorema di Gödel. Per concludere il mio sermone, Gödel era un fan di NSA e predisse, sbagliandosi, che entro 50 anni (mi sa che era negli anni ‘30) tutti avrebbero usato l’una o o l’altra forma di NSA…
@tomate: giusto per capire: il tuo aggettivo “enumerabile” vuol dire “computabile”?
Buona giornata
Stefano
Comment by Stefano — March 9, 2009 @ 4:15 pm
Non credo che i “numeri infiniti” dell’analisi non-standard siano transfiniti (nè cardinali nè ordinali (ma forse hai ragione: sono equivalenti agli ordinali transfiniti…)… Stefano, ci aiuti?)
Poi non capisco perchè tu distingua “dimostrare” da “confutare”: io userei: “dimostrare-come-vera” e “dimostrare-come-falsa”. Se una proposizione (e.g. l’ipotesi di Riemann) è indecidibile, non puoi fare ne’ l’una ne’ l’altra, non capisco perchè tu debba distinguere: una “dimostrazione di inconfutabilità” sarebbe una “dimostrazione-che-e-vera” (come dici tu stesso, del resto, quindi continuo a non capire sempre più…)
Sei sicuro che Goedel abbia dimostrato che il valore di verità di G sia ben definito? E quale sarebbe: vero o falso?
Da quel che avevo capito io, Goedel aveva dimostrato che il valore di verità di G non poteva essere dedotto (dimostrato) dagli assiomi, e pertanto poteva essere assunto tanto come vero quanto come falso (come il postulato delle parallele). Credo anche che si dovrebbe distinguere fra il numero di Goedel di G e il numero di Goedel della dimostrazione…
Che casinoooooooo!!!
PS
Sentiti libero di non rispondere, così la finiamo qui… per ora.
Comment by hronir — March 9, 2009 @ 4:15 pm
Stefano: sì, è da lì vengono i miei vaghi ricordi…
Quanto a tomate/Admin, non capisco perchè continui a distinguere fra i “due sensi di marcia”: come dici tu stesso una dimostrazione di inconfutabilita’ coinciderebbe con una sua dimostrazione…
E ancora: non dovremmo distinguere tra il numero di Goedel di G e quello della sua dimostrazione?
E ancora: davvero Goedel ha dimostrato che G ha un valore di verità definito? Non ha mica dimostrato che, come l’assioma delle parallele, puoi prenderlo per vero oppure per falso e ottenere cose, sì, diverse, ma ugualmente legittime?
Non sono sicuro, invece, che gli inifiti dell’analisi non-standard siano i transfiniti di Cantor (ma forse effettivamente sono equivalenti agli ordinali…)
Comment by hronir — March 9, 2009 @ 5:31 pm
Stefano: si, enumerabile vuol dire computabile, cioè che l’insieme può essere fornito ordinatamente come output da una macchina, ma non necessariamente una macchina di Turing. Perché ho voluto parlare di enumerabilità sarà chiaro in futuro.
Hronir: “come dici tu stesso una dimostrazione di inconfutabilita’ coinciderebbe con una sua dimostrazione…”. E’ proprio quello che discuto su: ipotizzavo che sia possibile parlare di una “inconfutabilità computazionale”, nel senso che un controesempio potrebbe esistere ma non essere mai mostrabile.
Francamente non so la dimostrazione di Goedel della proposizione di Goedel abbia un numero di Goedel. Nel senso: noi possiamo dire che la proposizione di Goedel è vera perché disponiamo di un’intuizione metalogica, ma quella proposizione è indecidibile all’interno del linguaggio in cui è formulata. Tante sono le proposizioni indecidibili che si possono costruire a partire da G, tra le altre la più famosa è la proposizione “questa teoria è coerente”. Io mi riferisco sempre a quella più basilare.
Però la risposta alla tua terza domanda è SI, G ha un valore di verità ben definito: se la proposizione “questa proposizione è indimostrabile” fosse falsa sarebbe assurda, per cui deve essere vera.
Infine una nota personale su GEB: penso che sia un libro ampiamente sopravvalutato; leggendolo (a suo tempo) che trovo confuso e ho avuto l’imopressione che non cogliesse veramente a fondo la genialità del teorema di Goedel, che non è la ricorsività del paradosso di Russell, ma il fatto che una proposizione sulla teoria sia esprimibile all’interno della stessa teoria. Consiglio invece la lettura del molto più breve La Prova di Goedel di Nagel-Newmann, Bollati Boringhieri.
Comment by Administrator — March 9, 2009 @ 10:29 pm
Ciao tomate,
non essere troppo duro con GEB. Non è un libro sul teorema di Gödel, ma su molto di più. È chiaro che se vuoi solo studiare Gödel, la cosa migliore è leggersi i suoi articoli.
GEB è divulgazione di alto livello, non è un saggio…
Comment by Stefano — March 10, 2009 @ 9:02 am
tomate, forse qualcosa comincia a chiarirsi: se un controesempio esiste (si può dimostrare l’esistenza) quantunque non computabile, non si può parlare di indecidibilità (non si potrebbe dimostrare l’esistenza). L’indecidibilità, se vuoi, è una cosa più forte della non-computabilità.
Dici: Francamente non so la dimostrazione di Goedel della proposizione di Goedel abbia un numero di Goedel. Nel senso: noi possiamo dire che la proposizione di Goedel è vera perché disponiamo di un’intuizione metalogica, ma quella proposizione è indecidibile all’interno del linguaggio in cui è formulata.
Io credo di sapere, invece, se la dimostrazione della proposizione G abbia un numero di goedel, e la risposta è: puoi scegliere (per definizione di indecidibilità). All’obiezione che ma allora se sceglo “sì” potrei mostrarti tale numero, e tu non potresti quindi scegliere “no” si risponde con un ma state parlando di cose (numeri naturali) diverse. Ora: questo significa davvero che tu non potrai mai mostrarmi il numero di goedel g ma solo a voler considerare i numeri naturali “alla solita maniera”. La scelta “no”, dunque, semplicemente aggiunge un assioma ai 5 di peano che non viene soddisfatta dai numeri naturali “soliti”.
Per cui la tua affermazione G ha un valore di verità ben definito è vera solo a patto di scegliere di che numeri naturali stiamo parlando. Se uno dice ma quelli di Peano!, la risposta è: no, non basta! per i numeri di peano G non ha un valore definito! E la tua frase ma noi disponiamo di un’intuizione metalogica va interpretata come ma noi ci riferiamo inconsapevolmente e intuitivamente ai numeri naturali come ai numeri di Peano più la proprietà che non esiste g, mentre a voler fare analisi non-standard si potrebbe considerare un concetto diverso di numero naturale, che però soddisfa tutti e 5 gli assiomi di Peano ma non quello della non esistenza di g, anzi, il suo sesto assioma è che un tale g esista (cioè che la proposizione G abbia un valore di verità ben definito ma diverso da quello dei numeri naturali “standard”).
Ti torna?
Io questa cosa non l’ho sentita affatto sottolineare in Nagel-Newmann e (anche per questo) ho un’opinione del tutto contraria alla tua sulla coppia GEB-NN: preferisco di gran lunga il primo!
Comment by hronir — March 10, 2009 @ 9:44 am
Se si puo’ dimostrare che esiste allora l’ipotesi e’ falsa, banalmente. Io dico che sarebbe ancora possibile dimostrare che non esistono controesempi computabili, e chi lo sa se ce ne sono di non computabili. Comunque e’ un miraggio: di fatto la comunita’ matematica e’ in gran parte orientata a tentare di dimostrare la congettura di Riemann, qualche raro pazzo cerca di confutarla, e quasi nessuno che io sappia pensa ad una prova di indecidibilita’.
Quanto alla tua seconda affermazione, credo che ci sia un po’ di confusione. La dimostrazione di una proposizione di Goedel non pu’ avere una numerazione, il che vuol dire semplicemente che non puo’ essere scritta nella grammatica di quella teoria, altrimenti G sarebbe un teorema della teoria. Questo non ha a che vedere con la sua computabilita’. In una teoria piu’ potente, in cui si aggiunge G come assioma, o un qualunque assioma che implichi G, allora ci sara’ una numerazione per G, ma G non sara’ piu’ una proposizione indecidibile. Infatti la proposizione di Goedel della teoria sara’ una certa G’… Ovviamente anche questa seconda teoria sara’ potente abbastanza da contenere i naturali, che sono sempre quelli standard. Ma in questa nuova teoria le numerazioni di Goedel dei teoremi non coincideranno affatto con quelle della teoria piu’ debole. Questo assioma in piu’ non aggiunge niente di interessante a parte G stesso, in particolare non vedo come possa implicare il passaggio all’analisi non-standard; d’altra parte non credo che aggiungere gli assiomi dell’analisi non standard implichi di per se G, e che quindi uno possa dire che la proposizione di Goedel della teoria di Peano abbia una numerazione non-standard. Direi che sono questioni indipendenti, ma non ci metterei la mano sul fuoco. Non credo che ci sia bisogno di appellarsi all’analisi non-standard.
Su GEB, ho rivalutato il mio giudizio dopo aver tentato di leggere Concetti Fluidi e Analogie Creative e soprattutto dopo aver visto un seminario di DH molto superficiale, ed aver pensato che sia solo una furba operazione di giustapposizione di idee interessanti. Ho il dente avvelenato con tutta una generazione di pensatori sistemici tipo Morin, Bateson etc. che passavano per guru ma, sotto sotto, secondo me si nascondeva poca roba. La scienza avrebbe delle cose veramente belle da dire filosoficamente, dei paradigmi concettuali rivoluzionari, ma non viene presa abbastanza sul serio.
Comment by tomate — March 11, 2009 @ 9:25 am
Io dico che sarebbe ancora possibile dimostrare che non esistono controesempi computabili, e chi lo sa se ce ne sono di non computabili.
Ok, non volevo insistere, è solo che quando ti ho chiesto se intendevi “indecidibilità” mi avevi risposto di sì e mi ero confuso…
Comment by hronir — March 11, 2009 @ 3:15 pm