Fondamenti della matematicae teoria algoritmica dell'informazione
Fondamenti della matematica e teoria algoritmica dell'informazione
Ciò che possiamo dimostrare intorno ai fondamenti della matematica usando i suoi stessi metodi costituisce la metamatematica, il cui attuale punto di partenza consiste nel fatto che si fa matematica usando un linguaggio artificiale e si sceglie un insieme fisso di assiomi e regole di inferenza (regole di deduzione); ciò viene fatto con tanta precisione che si può stabilire un algoritmo di verifica per le dimostrazioni. Definiremo teoria assiomatica formale un siffatto sistema formale. Come è stato mostrato da Alan Turing e ulteriormente chiarito da Emil Leon Post, l'insieme X di tutti i teoremi che sono conseguenza degli assiomi può essere generato sistematicamente passando in rassegna tutte le possibili dimostrazioni in ordine di lunghezza e controllando meccanicamente, sulla base delle regole di inferenza, quali sono valide. Questa elaborazione senza fine, che sarebbe enormemente dispendiosa in termini di tempo, viene talvolta chiamata scherzosamente algoritmo del British Museum. La lunghezza in bit H(X) del programma che genera l'insieme X dei teoremi, cioè la complessità di X in termini di lunghezza del programma, giocherà un ruolo cruciale nel seguito: si tratta, informalmente, del numero complessivo di bit degli assiomi della teoria formale. H(X) fornisce un modo per misurare la complessità algoritmica o il contenuto di informazione algoritmica di una teoria assiomatica formale e rende manifesta la presenza diffusa dell'incompletezza. Infatti, in questo ambito, parlare del programma più corto possibile è problematico e anzi vale il seguente risultato di incompletezza: se si hanno n bit di assiomi, non si può dimostrare che un programma sia il più breve possibile se è più lungo di n bit. Ripercorriamo ora la storia della materia, iniziando con un pregevole pezzo d'antiquariato: il primo teorema di incompletezza, enunciato e dimostrato da Kurt Gödel nel 1931.
Fissiamo la nostra teoria assiomatica formale come sopra descritto e chiediamoci se la proposizione 'questa proposizione è indimostrabile' può essere dimostrata all'interno della nostra teoria: essa può esserlo se e solo se è falsa. 'Questa proposizione è indimostrabile' non suona affatto come una proposizione matematica, ma Gödel mostra che in realtà lo è. La dimostrazione di Gödel è basata sulla costruzione di un'ingegnosa asserzione relativa all'aritmetica, o alla teoria dei numeri, che si riferisce a se stessa e alla propria indimostrabilità indirettamente, attraverso i cosiddetti 'numeri di Gödel' delle proposizioni e delle dimostrazioni all'interno della teoria formale. In altre parole, Gödel numera tutte le proposizioni e dimostrazioni all'interno della teoria assiomatica formale ed è poi in grado di costruire un'affermazione matematica vera e propria (molto complessa) che afferma che essa stessa è indimostrabile; il riferimento a se stessa è indiretto, poiché l'affermazione autoreferenziale di Gödel non può contenere il proprio numero di Gödel. Perciò le teorie assiomatiche formali, se dimostrano solo teoremi veri, sono incomplete perché non dimostrano tutte le proposizioni vere. E così emerge che 'vero' e 'dimostrabile' sono cose ben diverse.
Per quanto meravigliosa, la dimostrazione di Gödel non fa uso di tre delle grandi idee del XX sec., cioè quelle di algoritmo, informazione e casualità. Il primo passo per l'introduzione di questi concetti nella metamatematica fu compiuto appena cinque anni più tardi da Turing, che utilizzò gli algoritmi per formulare un nuovo teorema di incompletezza.
Una definizione matematica della nozione di algoritmo viene fornita da Turing nel 1936. Le contemporanee scoperte del logico statunitense Alonzo Church lo privano del pieno riconoscimento dei suoi meriti, ma l'assoluta originalità del suo approccio è subito chiara: egli fa infatti uso solo di operazioni concretamente realizzabili nel mondo fisico, per esempio da una macchina. Benché egli si avvalga di un linguaggio di programmazione estremamente primitivo (ora chiamato 'macchina di Turing'), si tratta ugualmente di un decisivo passo avanti verso l'era del computer. Definito cos'è un algoritmo, Turing dimostra che ci sono cose che non possono essere ottenute mediante calcolo, facendo un uso brillante del procedimento diagonale di Cantor, usato in teoria degli insiemi, che egli applica all'elenco di tutti i numeri reali calcolabili. In tal modo Turing ottiene un numero reale non calcolabile R, come spiegheremo oltre, e una fonte di incompletezza totalmente diversa da quella scoperta da Gödel nel 1931.
Algoritmi e linguaggi di programmazione
Un algoritmo è una procedura 'meccanica' per calcolare qualcosa, in genere formulata in un qualunque linguaggio di programmazione. Un importante esempio è il LISP, che useremo in seguito come linguaggio di riferimento. I programmi e i dati in LISP sono tutti S-espressioni (dove la S sta per simbolico), cioè liste i cui elementi possono essere a loro volta liste, racchiuse tra parentesi e con gli elementi separati da spazi, come la S-espressione (A BC (123 DD)). Per esempio, (f x y) esprime f(x, y), cioè l'applicare la funzione f agli argomenti x e y; (if x y z) sceglie tra y e z e dà come risultato y o z a seconda che x sia vero (true) o no; (= x y) verifica se x=y, dando come risultato vero (true) o falso (false). Per illustrare meglio come funziona questo linguaggio, analizziamo l'algoritmo che definisce l'appartenenza a un insieme in LISP:
(define (in-set? member set)
(if (= () set) false
(if (= member (head set)) true
(in-set? member (tail set))
))
)
Questo definisce (in-set? member set) come false se l'insieme è vuoto, true se member è il primo elemento dell'insieme (head), e ricorsivamente come (in-set? member tail) negli altri casi, dove tail indica il resto dell'insieme. Per ragioni storiche, head è in realtà chiamato car e tail è in realtà chiamato cdr. Quindi:
(in-set? (′y) (′(x y z)))
dà come risposta true, e
(in-set? (′ q) (′ (x y z)))
dà come risposta false. Qui l'apice ′(quote) interrompe l'elaborazione e introduce i dati non elaborati. Insomma, un programma in LISP non è un elenco di istruzioni che vengono eseguite, ma è un'espressione che dev'essere valutata, e quel che fa è dare in uscita un valore. In altre parole, il LISP è un linguaggio di programmazione funzionale e non un linguaggio imperativo, ovvero strutturato intorno a un insieme di istruzioni pensate come ordini impartiti a una macchina. Questa caratteristica del LISP lo rende particolarmente adatto ai nostri scopi.
Il primo teorema moderno di incompletezza: il problema dell'arresto di Turing
I numeri reali sono numeri come π (3,1415926…). Immaginiamo un elenco numerato di tutti i possibili programmi per computer per calcolare numeri reali, cioè tutti i possibili programmi in qualche linguaggio fissato, ordinati per lunghezza e, tra quelli della stessa lunghezza, in qualche ordine alfabetico arbitrario. Così R(N) è il numero reale (se esiste) che è calcolato dall'N-simo programma dell'elenco (N=1,2,3,…). Sia R(N,M) l'M-sima cifra dopo la virgola dell'N-simo numero reale computabile, cioè il numero reale R(N) calcolato dall'N-simo programma. Definiamo ora un nuovo numero reale R* la cui M-sima cifra dopo la virgola, R*(M) con M=1,2,…, sia 3 se R(M,M) è diverso da 3, e sia 2 negli altri casi (compreso il caso che l'M-simo programma non fornisca mai in uscita un'M-sima cifra). R* è un numero reale non calcolabile, perché differisce dall'N-simo numero reale calcolabile nell'N-sima cifra e la sua esistenza implica che non ci può essere alcun modo di decidere se l'N-simo programma fornisce o meno un'N-sima cifra, perché in tal caso potremmo calcolare concretamente R*, il che è impossibile. Un corollario di questo teorema è che non esiste alcuna teoria assiomatica formale all'interno della quale sia sempre possibile dimostrare se l'N-simo programma produrrà un'N-sima cifra o no, perché altrimenti si potrebbero passare in rassegna tutte le possibili dimostrazioni in ordine di lunghezza e calcolare R*. Si noti che chiedersi se l'N-simo programma fornirà mai un'N-sima cifra è un caso particolare del problema dell'arresto, cioè il problema di determinare a priori se un programma per computer si fermerà o no (in assenza di limiti di tempo per la sua esecuzione). Se un programma si ferma, ciò si può prima o poi determinare semplicemente eseguendolo. Il vero problema è decidere se un programma non si fermerà mai, per quanto tempo gli si dia.
Metamatematica postmoderna: la probabilità di arresto Ω
Fu così che Turing portò la nozione di algoritmo nella metamatematica, cioè nella discussione sui fondamenti della matematica. Vediamo ora un'ulteriore fonte di incompletezza, e introduciamo nella discussione i concetti di informazione, casualità, complessità e irriducibilità. Dobbiamo però preventivamente definire un certo tipo di computer ‒ o equivalentemente specificare il suo ‒ che chiameremo computer binario universale auto-delimitante U. Il programma di U è una stringa di lunghezza finita e ha inizio con un prefisso che è un'espressione LISP. Quest'ultima è convertita in binario, dando come risultato 8 bit per carattere, ed è seguita da uno speciale carattere di punteggiatura (altri 8 bit) seguito a sua volta da dati binari grezzi. Il prefisso in LISP viene valutato o eseguito e leggerà i dati binari grezzi un bit per volta senza oltrepassare la fine del programma. In altre parole, il prefisso LISP deve chiedere il corretto numero di bit di dati binari grezzi. Se chiede un ulteriore bit dopo aver letto l'ultimo, ciò non porta a una condizione di fine del file, bensì interrompe l'elaborazione. Il fatto che non ci sia un segno di punteggiatura che segnala la fine dei dati binari grezzi, e quindi la fine dell'intero programma, è ciò che costringe questi programmi in linguaggio macchina a essere auto-delimitanti. In altre parole, la fine del programma in binario è come uno strapiombo nel quale il computer U non deve precipitare. La probabilità di arresto Ω per U è:
[1] Ω = ∑2−(numero di bit in p)
p si ferma quando
eseguito su U
Così se il programma p si ferma ed è lungo K bit, esso contribuisce per un valore 1/2K alla probabilità di arresto Ω. Questa probabilità di arresto può essere definita in modo da comprendere programmi binari p di ogni possibile lunghezza proprio perché questi p devono essere auto-delimitanti, vale a dire proprio perché è U che deve decidere autonomamente dove fermare il programma p. U non deve oltrepassare il limite, non può cadere nello strapiombo, deve leggere esattamente fino all'ultimo bit di p, ma non oltre. La conoscenza dei primi N bit della rappresentazione in base due del numero reale Ω ‒ che, essendo una probabilità, è compreso tra zero e uno ‒ dà una soluzione al problema dell'arresto per tutti i programmi di lunghezza fino a N bit. Così la conoscenza dei primi N bit di Ω dopo la virgola decimale (o binaria) renderebbe teoricamente in grado di decidere se ciascun programma binario p lungo fino a N bit si ferma o meno quando viene eseguito su U e ciò risulta di grandissima utilità, come dimostra il seguente esempio. Consideriamo l', una famosa congettura matematica ancora aperta, ovvero ancora non risolta. Esiste un programma per mettere alla prova l'ipotesi di Riemann: il programma cerca sistematicamente controesempi e si ferma se e solo se ne trova uno, dimostrando così che l'ipotesi di Riemann è falsa. La lunghezza in bit di questo programma rappresenta la complessità, in termini di lunghezza del programma, di questa maniera di mettere alla prova l'ipotesi di Riemann. E se questo programma è lungo H(Riemann) bit, conoscere questo numero di bit iniziali di Ω risolverebbe l'ipotesi di Riemann e cioè ci metterebbe in grado di dire se l'ipotesi di Riemann è vera o no. Sfortunatamente il metodo per fare ciò, pur essendo valido teoricamente, è completamente privo di utilità pratica. L'elaborazione richiesta, pur di lunghezza finita, è di gran lunga superiore alle attuali capacità di calcolo. Il tempo necessario cresce molto più che esponenzialmente rispetto a H(Riemann), il numero di bit di Ω che conosciamo: esso cresce come il tempo necessario per eseguire simultaneamente su U tutti i programmi che hanno lunghezza inferiore o uguale a H(Riemann) bit fino a che tutti i programmi che prima o poi si fermano saranno giunti ad arrestarsi. Più precisamente, bisogna eseguire un numero sufficiente di programmi per un tempo sufficiente a ottenere correttamente i primi H(Riemann) bit di Ω e questo, a causa di riporti da parte di bit in posizioni successive, può coinvolgere anche programmi di lunghezza maggiore di H(Riemann) bit. La grande utilità dei bit di Ω è dovuta al fatto che essi costituiscono informazione matematica irriducibile, ovvero non possono essere derivati o dedotti da principî più semplici. Più precisamente, abbiamo il seguente risultato di incompletezza: occorre una teoria assiomatica formale da N bit (cioè una teoria che ha un algoritmo di N bit per generare tutti i teoremi) per essere in grado di determinare i primi N bit di Ω o, addirittura, i valori e le posizioni di un qualunque insieme di N bit di Ω. In effetti, si può dimostrare che una teoria da N bit non può determinare più di N+c bit di Ω, dove la costante c è pari a 15.328. Riformuliamo tutto ciò. Consideriamo una teoria assiomatica formale con insieme dei teoremi X e con complessità algoritmica o contenuto di informazione algoritmica H(X). Allora, posto che una proposizione come
Il 99° bit di Ω è 0,
Il 37° bit di Ω è 1,
la quale determina il valore di un particolare bit di Ω in una particolare posizione, sia in X se e solo se è vera, segue che ci sono al più H(X)+c teoremi siffatti in X. In altre parole, X ci mette in grado di determinare al più H(X)+c bit di Ω. Possiamo descrivere questa irriducibilità anche in modo non tecnico, ma molto efficace, come segue: il fatto che ogni dato bit di Ω sia uno 0 o un 1 è un fatto matematico che non è vero per qualche ragione specifica, è vero per accidente!
Che cos'è l'informazione algoritmica
Ω è in realtà solo un elemento della teoria algoritmica dell'informazione (AIT, Algorithmic information theory), di cui esporremo ora alcuni degli aspetti più importanti. Consideriamo ancora il computer U che abbiamo usato per definire Ω: esso può essere usato come metro campione per misurare l'informazione algoritmica, attraverso la lunghezza dei suoi programmi, adottando come unità dell'informazione algoritmica il bit 0/1. Si definisce contenuto di informazione algoritmica assoluta H(X) di un oggetto X (in realtà, di una S-espressione in LISP) la lunghezza in bit del più breve programma per U che calcola X. Il contenuto di informazione congiunto H(X,Y) è definito come la lunghezza in bit del più breve programma per U che calcola la coppia (X,Y), che si esprime in LISP come (X Y). Il contenuto di informazione relativo H(X∣Y) è definito come la lunghezza in bit del più breve programma per U che calcola X a partire da un programma di lunghezza minima per Y, non direttamente da Y. La complessità H(X) di una teoria assiomatica formale con insieme dei teoremi X è definita anch'essa usando il computer U. H(X) è definita come la lunghezza in bit del più breve programma che fa sì che U generi l'insieme di teoremi X. Si noti che questa è un'elaborazione che non ha termine. Si può pensare a H(X) come al numero di bit di informazione nel più conciso o più elegante insieme di assiomi che generano l'insieme di teoremi X.
Esponiamo ora alcuni dei teoremi che si possono dimostrare a proposito di queste quantità. Prima di tutto, consideriamo una stringa X lunga N bit. H(X) non differisce in genere di molto da N+H(N), che è circa N+log2N. Le stringhe di bit X per cui vale ciò sono dette algoritmicamente casuali e hanno il massimo contenuto di informazione possibile. Peraltro, una successione infinita di bit X viene poi definita algoritmicamente casuale se e solo se esiste una costante c tale che H (i primi N bit di X) è maggiore di N−c per ogni N. Un punto cruciale è che la rappresentazione in base due di Ω soddisfa questa definizione di casualità algoritmica, il che è una delle ragioni per cui Ω è così interessante. L'informazione algoritmica è (sub)additiva:
[2] H(X,Y) ≤ H(Y) + c.
Inoltre, a partire da H(X) e H(X,Y), si può definire il cosiddetto contenuto di informazione comune H(X:Y), che misura quanto calcolare due oggetti insieme sia meglio che calcolarli separatamente:
[3] H(X:Y) = H(X) + H(Y) − H(X,Y).
X e Y sono detti indipendenti algoritmicamente se la loro informazione comune è piccola rispetto ai loro contenuti di informazione individuali (H(X:Y)≈0), cosicché
[4] H(X,Y) ≈ H(X) + H(Y).
Premesso ciò, ecco alcuni sottili risultati che collegano l'informazione comune e quella relativa:
[5] H(X,Y) = H(X) + H(Y∣X) + O(1)
H(X:Y) = H(X) − H(Y∣X) + O(1)
H(X:Y) = H(Y) − H(Y∣X) + O(1).
Qui A=B+O(1) significa che la differenza tra il membro sinistro e quello destro dell'uguaglianza è limitata, cioè è al più un numero fisso di bit. Quindi l'informazione comune misura anche fino a che punto la conoscenza di un elemento di una coppia aiuti a conoscere l'altro.Questi risultati vengono qui citati per mostrare che Ω non è un'entità isolata, è parte di un'elegante teoria dell'informazione algoritmica e della casualità, una teoria della complessità in termini di lunghezza di programma per U.
La matematica è quasi-empirica?
A nostro parere i risultati di incompletezza di cui abbiamo parlato hanno molta importanza. Riteniamo infatti che la matematica sia più simile alla fisica di quanto vorrebbero ammettere i matematici, cioè che l'incompletezza non possa essere ignorata e che i matematici dovrebbero talvolta essere disposti ad aggiungere nuovi assiomi che sono giustificati dall'esperienza, sperimentalmente, pragmaticamente, ma che non sono del tutto ovvi. Qualche volta, per dimostrare di più occorre fare ipotesi più azzardate, aggiungere più assiomi. Questo è ciò che suggerisce il nostro approccio all'incompletezza mediante la teoria dell'informazione. Naturalmente in questo momento, all'inizio del XXI sec., questa posizione risulta difficile da accettare: va contro il paradigma attuale di che cosa sia la matematica, di come si debba fare matematica e di quale sia la sua natura. Ma la nostra speranza è che il XXI sec. arriverà a decidere che aggiungere nuovi assiomi non è affatto una cosa discutibile bensì la cosa giusta da fare. In ogni caso questo radicale cambiamento potrebbe richiedere molti anni di discussione e di riflessione per essere accettato, ammesso che ciò si verifichi. Confidiamo che fra cento anni i matematici saranno in grado di giudicare la nostra attuale matematica e metamatematica come noi giudichiamo la matematica del Novecento, con un giustificato sentimento di superiorità. La nostra speranza è che essi si stupiranno di come abbiamo potuto essere così ciechi da non vedere le nuove teorie, semplici, meravigliose, bellissime, che stavano appena dietro l'angolo, di come abbiamo fatto a non accorgercene pur essendo a un soffio da esse.
Bibliografia
Borwein, Bailey 2004: Borwein, Jonathan - Bailey, David, Mathematics by experiment, Natick (Mass.), Peters, 2004.
Calude 2002: Calude, Cristian, Information and randomness: an algorithmic perspective, 2. ed., Berlin, Springer, 2002.
Chaitin 1970: Chaitin, Gregory J., To a mathematical definition of "life", "Association for Computing Machinery SICACT news", 4, 1970, pp. 12-18.
Chaitin 1975: Chaitin, Gregory J., A theory of program size form-ally identical to information theory, "Journal of the Association for Computing Machinery", 22, 1975, pp. 329-340.
Chaitin 1987: Chaitin, Gregory J., Algorithmic information theory, Cambridge, Cambridge University Press, 1987.
Chaitin 1998: Chaitin, Gregory J., The limits of mathematics: a course on information theory and the limits of formal reas-oning, 2. ed., Singapore, Springer, 1998.
Chaitin 1999: Chaitin, Gregory J., The unknowable, Singapore, Springer, 1999.
Chaitin 2001: Chaitin, Gregory J., Exploring randomness, London, Springer, 2001.
Chaitin 2002: Chaitin, Gregory J., Conversations with a mathematician: math, art, science and the limits of reason, London, Springer, 2002.
Davis 1965: The undecidable: basic papers on undecidable pro-positions, unsolvable problems and computable functions, edited by Martin Davis, New York, Raven, 1965.
Delahaye 2002: Delahaye, Jean-Paul, Les nombres oméga, "Pour la science", 295, 2002, pp. 98-103.
Gödel 1931: Gödel, Kurt, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, ‟Monatshefte für Mathematik und Physik", 38, 1931, pp. 173-198.
Grattan-Guinness 2000: Grattan-Guinness, Ivor, The search for mathematical roots 1870-1940, Princeton (N.J.), Princeton University Press, 2000.
McCarthy 1962: McCarthy, John e altri, LISP 1.5 programmer's manual, Cambridge (Mass.), MIT Press, 1962.
Nagel, Newman 1958: Nagel, Ernest - Newman, James R., Gödel's proof, New York, New York University Press, 1958 (trad. it.: La prova di Gödel, Torino, Boringhieri, 1961).
Post 1944: Post, Emil L., Recursively enumerable sets of posi-tive integers and their decision problems, "Bulletin of the American Mathematical Society", 50, 1944, pp. 284-316.
Tasić 2001: Tasić, Vladimir, Mathematics and the roots of postmodern thought, Oxford, Oxford University Press, 2001.
Turing 1936: Turing, Alan, On computable numbers, with an application to the Entscheidungsproblem, "Proceedings of the London Mathematical Society (Series 2)", 42, 1936, pp. 230-265.
Tymoczko 1998: Tymoczko, Thomas, New directions in the philosophy of mathematics: an anthology, 2. ed., Princeton (N.J.), Princeton University Press, 1998.