Numero di Shannon

closeQuesto articolo è stato pubblicato 9 anni 5 mesi 29 giorni fa. Nel frattempo potrei avere cambiato idea. Anzi, quasi sicuramente è accaduto così: tienine conto se pensi di commentare quanto ho scritto.

Grazie ai Rudi matematici scopro l’esistenza del Numero di Shannon: il «limite inferiore del numero di possibili partite a scacchi» (a quanto pare è impossibile calcolare l’effettivo numero di possibili partite, e ci si accontenta di una stima per difetto).

Questo numero è circa 10120, un 1 seguito da centoventi zeri.

La cosa interessante è che nell’universo osservabile si stimano esserci stimato tra 1079 e 1085 particelle elementari. In altre parole, per ogni particella elementare nell’universo osservabile ci sono almeno 1035 possibili partite di scacchi.
Io la interpreto come una straordinaria vittoria degli oggetti sociali sugli oggetti fisici (certo, non c’è il tempo per giocare queste 10120 partite di scacchi: una piccola, ma importante, ritorsione del mondo fisico).

37 pensieri su “Numero di Shannon

  1. cosa c’e di “sociale” in una partita a scacchi solamente ipotetica ? (e ammetto di non avere la più pallida idea di cosa siano gli “oggetti sociali” 🙂 )

  2. @Dario Bressanini:Hai perfettamente ragione: in questo confronto si gioca sporco, da una parte qualcosa che esiste, le particelle elementari, dall’altra qualcosa che potrebbe esistere, le ipotetiche partite possibili. Se volessimo giocare ad armi pari, dovremmo confrontare le partite effettivamente giocate con le particelle realmente esistenti, oppure le partite possibili con le particelle potenzialmente esistenti (e come le calcoli?).
    Quanto agli oggetti sociali: sono quelle “cose” come i matrimoni, le patenti, i contratti, le lauree, le dichiarazioni dei redditi… Sto pensando di preparare delle FAQ sugli oggetti sociali, che forse ce n’è bisogno.

  3. Ho appena risposto al tuo commento sul mio ultimo post. Dopodichè sono venuto (metaforicamente) qui e ho letto questo post. Allora ho esclamato: “Appunto”.

    Se provi a fare lo stesso percorso che ho fatto sarà chiaro il perchè!

    =)

  4. @Corrado: Non chiedere troppo a una riflessioni così striminzita (certo, testimonia che sono ossessionato dagli oggetti sociali, ma è un problema mio, non degli oggetti sociali)

  5. @Ivo: e che cosa avrebbero di profondamente comune tutte queste “cose” ?

    E perche’ si e’ sentita l’esigenza di definire un “contenitore” per tutte ?

    (scusa la domanda scema, ma io e la filosofia abbiamo sempre litigato fin dal Liceo 😉 )

  6. @Dario Bressanini: Cosa hanno in comune? Di essere oggetti sociali, ovviamente 😉
    L’esigenza di definire un contenitore per tutte queste cose può venire da due fronti: mettere ordine nel creato (distinguere tra le varie cose che esistono); capire il senso di alcune frasi che non descrivono la realtà ma la modificano (le dichiarazioni: “io mi scuso” non descrive le scuse, ma le crea).
    Come chiarirò nelle FAQ, se mai le farò, prerequisito essenziale è chiarire cosa significa esistere.

    Una piccola nota sull’utilità di queste ricerche: stiamo parlando forse dell’unica disciplina filosofica che abbia davvero una qualche utilità. Barry Smith è riuscito a guadagnarci un bel po’ di soldi, grazie all’ontologia applicata, se ricordo bene, alla medicina.
    Diciamo, in poche parole, che ovunque tu voglia creare un archivio (un qualsiasi archivio: dalla tua biblioteca personale a un database di sostanze chimiche) ti devi porre domande ontologiche.

  7. @Ivo

    infatti sono subito andato a leggere (e commentare) il blog che parla di chimica 🙂
    Pensa che dedico un’ora a lezione con i miei studenti a rispondere alla domanda “in che senso una molecola esiste?” 😉 (però i miei tentativi di risposte sono di tipo scientifico, non filosofico).

    Per gli oggetti sociali, non mi hai mica risposto 🙂 mi devi dire quale caratteristica debbano avere quegli “oggetti” per essere catalogati come “sociali”

    … e non ti crucciare se la filosofia è inutile in pratica: lo sono anche molte scienze 😉

    ciao Dario

  8. @Maurizio: Ottima idea. Me le procuri tu quel miliardo di scacchiere necessarie?

    @Dario Bressanini: Secondo Searle, un oggetto sociale istituzionale deve:
    a) essere epistemicamente oggettivo (ossia non deve essere una opinione discutibile, vera per me ma falsa per te, come “la rosa è più bella del tulipano”, ma oggettiva, vera o falsa per tutti, come “Berlusconi è il presidente del consiglio”)
    b) essere ontologicamente soggettivo (la loro esistenza dipende dai soggetti, dalle loro credenze e comportamenti – nel complesso, la singola credenza è irrilevante).
    c) avere una funzione di status (una funzione che non risiede unicamente nelle proprietà fisiche dell’oggetto: una banconota è un oggetto sociale istituzionale appunto perché non bastano le proprietà fisiche della carta a renderlo un oggetto di scambio).
    Secondo Ferraris, un oggetto sociale deve:
    a) sopravvivere all’atto (una promessa dura più della frase “io ti prometto che …”, mentre una passeggiata finisce quando torno a casa).
    b) essere iscritta da qualche parte (valgono anche i ricordi).

    PS In che senso una molecola esiste?

  9. Per le molecole, prima si devono chiarire le condizioni al contorno. Se si considera una molecola nel vuoto, che non interagisce con altre molecole, la risposta è che una molecola può esistere (che poi si riesca a sintetizzarla o meno non ha importanza teorica 🙂 ) se la sua equazione di schroedinger dice che esiste 🙂
    Ovviamente nella maggioranza dei casi non possiamo risolvere l’equazione esattamente o con accuratezza, ma dal punto di vista teorico quella è la risposta “definitiva”

    Se invece consideriamo un insieme macroscopico di molecole, allora le cose si complicano, e devi tenere conto della temperatura, pressione, termodinamica etc, però a rigore Non stai più parlando di una singola molecola, ma di un “materiale” (un bicchiere d’acqua ad esempio)

    ciao dario

  10. “Me lo procuri tu quel miliardo di scacchiere necessarie? ”

    E perche’ no? Potrei costruirle in parallelo, mentre gioco a scacchi.

    Mentre scrivevo queste righe ho appena cominciato a costruirne 10 ^ 22.

  11. Non fa niente! Le scacchiere non devono esistere tutte allo stesso momento. Posso fare una mossa nella partita I, disfare la scacchiera, ricomporla nella configurazione della partita I+1, fare un’altra mossa, ecc.

    Suvvia ragazzi, ammettete che siamo di fronte a una verita’ trascendente: “e’ possibile giocare qualunque numero di partite di scacchi.” Potremmo chiamarlo il Primo Teorema di Maurizio. 🙂

  12. @Dario: non vedo il problema. In realtà, essendo un numero finito, le partite di scacchi possono evidentemente essere messe in un ordine. Il trucco è quindi giocarle in ordine, nel senso che sulla scacchiera S_k giochi la partita P_k. Semplice, no?

  13. @hronir

    Ii assicuro che in questo momento sto giocando 10 ^ 22 partite di scacchi. Solo, molto, molto lentamente 🙂

    PS: a scanso di equivoci, .mau. non sono io. 🙂

  14. si parlava di giocarle, no?

    Esatto.
    Diciamo che non basta numerare le partite o le mosse, ma è necessario elencare tutte quante le mosse.
    Un elenco simile (tutte le mosse di tutte le possibili partite) è irrealizzabile – in forma estesa. Compresso, forse è realizzabile.

  15. Solo, molto, molto lentamente

    Metterei come limite di tempo l’età dell’universo. Quanto è? Facciamo 30 miliardi di anni
    3 * 10^10 anni, ossia circa 10^18 secondi.
    Tenendo conto che ogni particella deve essere giocata 10^35 volte, hai 10^18 / 10^35 secondi per ogni partita. Sono 0,00000000000000001 secondi.

  16. @Ivo

    Un elenco simile (tutte le mosse di tutte le possibili partite) è irrealizzabile – in forma estesa. Compresso, forse è realizzabile.

    Hmm… forse non ho seguito bene tutta la discussione, ma non mi è chiaro perché questo elenco dovrebbe essere realizzato in forma estesa prima di cominciare il tutto. Potremmo generarlo dinamicamente, mentre giochiamo.

    Cioè, qui l’importante è che tutte le possibili giocate siano “ricorsivamente enumerabili”. In questo caso potremmo ancora giocarle tutte, con un procedimento di “Goedelizzazione” o “a coda di colomba”. (credo che con un po’ di tempo si potrebbe scrivere un algoritmo per farlo).

    Questo funzionerebbe persino se il numero di partite possibili fosse infinito (cosa che non è, mi pare). Basta che sia un infinito numerabile.

    In questo modo le partite le giocherei _tutte_, senza lasciarmene dietro nessuna. Certo, senza terminare mai (perché morirei prima, o l’universo finirebbe prima). Ma _finirle_ non era un requisito: Il requisito era _giocarle_. Lo so che è un trucco, ma la mia battuta si basava proprio sulla distinzione tra giocare e terminare. 🙂

    (Mi è venuta in mente un’altra cosa: alcune partite di scacchi non finiscono mai. Se ben ricordo, negli scacchi, se ho una situazione di stallo, i giocatori possono anche inseguirsi all’infinito senza mai terminare. Ma con la goedelizzazione neppure questo è un problema.)

  17. Proprio perché si parla di giocare, e non di enumerare, il problema è meno grave di quanto sembrerebbe a prima vista. Se B e N vogliono giocare tutte le partite possibili:
    – A prepara una scacchiera per ciascuna prima mossa che può fare, e le mette in fila in un ordine qualunque. Ci sono venti prime mosse, se non sbaglio. Mette un segnalibro al fondo della fila di scacchiere.
    – B parte dall’inizio della fila, prende con sè la scacchiera, va al fondo, e aggiunge tante scacchiere quante sono le sue prime mosse (di nuovo venti) in risposta alla posizione nella scacchiera che si è portato via. Torna all’inizio e ripete l’operazione fino a che non arriva al segnalibro. Lo prende e lo mette in fondo alla fila.
    – A fa le stesse operazioni di B, con la sua seconda mossa.
    – B fa le stesse operazioni di A, con la sua seconda mossa.
    – Nel caso una partita finisca, la scacchiera viene semplicemente eliminata dalla fila.
    (Se non erro, è lo stesso ragionamento del mio omonimo.)
    Resta il problema di accorgersi se c’è patta per ripetizione di mosse, però un sistema c’è, visto che nel segnalibro si può indicare il numero di mossa e c’è un momento in cui si può essere certi che la stessa posizione è stata raggiunta per tre volte.
    Quanto al tempo, non c’importa d’o’passato, tanto le partite le iniziamo oggi, no?

  18. @Maurizio: Non pensavo alla differenza tra giocare e finire…

    @.mau.: Se non sbaglio, è teoricamente possibile che una partita non abbia fine senza tuttavia ripetersi.

    Giusto per precisare: quando dico che non si possono giocare queste 10^120 partite, non intendo dire che è teoricamente impossibile farlo. È una impossibilità pratica, quella a cui penso.

  19. .mau., la differenza fra computabilità e complessità è proprio che la seconda tiene conto delle risorse (tempo, spazio, etc…)

  20. @hronir: dal mio punto di vista la complessità dice in quanti passi (come ordine di grandezza) può essere eseguito un algoritmo al variare della dimensione N dei dati, mentre la computabilità dice semplicemente se l’algoritmo può essere eseguito in principio. Insomma, il numero di Graham è computabile. Quello di cui parli tu al limite è computabilità efficiente.

  21. @ivo: come fa una partita a durare all’infinito senza ripetersi? Hai un numero finito di pezzi che possono trovarsi in un numero finito di caselle.

  22. .mau., hai riassunto benissimo: la complessità è computabilità efficiente (in termini di tempo/spazio…).
    E qui stiamo appunto confrontando il numero di possibili partite a scacchi con il numero di atomi o il numero di secondi dell’universo, no?

  23. la complessità di per sé è neutra. È chiaro che un programma NP è peggio di uno polinominale a lungo andare, ma se l’unico algoritmo polinomiale a disposizione è O(N^200) me ne faccio poco…

  24. Ah, .mau., se il solito matematico.
    cmq non stai dicendo niente di nuovo:

    Now, I realize people will immediately object: what if a problem is solvable in polynomial time, but the polynomial is n^50000? Or what if a problem takes exponential time, but the exponential is 1.00000001^n? My answer is pragmatic: if cases like that regularly arose in practice, then it would’ve turned out that we were using the wrong abstraction. But so far, it seems like we’re using the right abstraction. Of the big problems solvable in polynomial time — matching, linear programming, primality testing, etc. — most of them really do have practical algorithms. And of the big problems that we think take exponential time — theorem-proving, circuit minimization, etc. — most of them really don’t have practical algorithms.
    http://www.scottaaronson.com/democritus/lec6.html

    PS
    Non sono gli algoritmi, ma i problemi, ad essere, o meno, NP, NP-completi, etc etc. Questo punto di come definire la “classe di difficolta’” di un problema senza far esplicito riferimento al “miglior algoritmo capace di risolverlo” e’ molto interessante… e nonostante al .mau. possa apparire un problema mal posto matematicamente, vista la sua obiezione, la questione P=NP è oggettivamente una delle più profonde di tutti i tempi, con potenziali implicazioni adddirittura a livello fisico…!

  25. @hronir: tra i miei tanti difetti non c’è il plagio, nel senso che so perfettamente di non essere un pensatore originale né faccio finta di esserlo 🙂

  26. ma no, .mau., era solo per dire che si tratta di un problema ben noto a chi è del mestiere… mi permetterei mai di offendere un mostro sacro come te? — oddio, no! ora sembrerà ironica questa chiosa… 🙁

  27. @.mau.:

    come fa una partita a durare all’infinito senza ripetersi? Hai un numero finito di pezzi che possono trovarsi in un numero finito di caselle.

    Ah non lo so, i matematici siete voi 😉
    Citavo (malamente) il sesto capitolo di Come tagliare una torta di Ian Stewart.
    Noto solo adesso che Stewart non si riferisce alla regola “se la stessa posizione si verifica tre volte un giocatore può chiedere che la partita termini in parità”, ma a quest’altra: “se la medesima sequenza di mosse, con esattamente le stesse posizioni, viene ripetuta tre volte di fila un giocatore eccetera”. Insomma, non parla di posizioni ma di mosse, e questo penso che questo risponda alla tua obiezione.
    A quanto pare, è possibile che una partita continui all’infinito senza ripetere tre volte di seguito le stesse mosse: esistono sequenza infinite senza triplette.

  28. @ivo: sicuramente esistono successioni infinite senza triplette, mi pareva di averne anche scritto a suo tempo e se non l’ho fatto lo farò.
    Però la regola di Stewart non torna né a me (che però non sono uno scacchista), né a en.wiki, né dalle regole FIDE (sezione 9.2).
    Se me ne ricordo, stasera verifico How to cut a cake per vedere qual è la frase originale del libro.

  29. @ivo: ho verificato. Nell’inglese Stewart dice che alcuni anni fa c’è stata la proposta di cui parli tu, e in una parentesi c’è scritto “che è diversa dalla regola attuale, dove la patta è solo proponibile”. Naturalmente l’altra legge gli serve per dire che possono esserci successioni senza triplette… ora che mi ricordo non ne ho mai scritto perché è da una vita che ho l’articolo in bozza.

  30. @.mau.: Ed ecco il passo in italiano:

    Una proposta avanzata qualche tempo fa prevedeva che la partita finisse se la medesima sequenza di mosse, con esattamente le stesse posizioni, veniva ripetuta tre volte di fila. Essa non va tuttavia confusa con la legge standard secondo cui, qualora la stessa posizione si verifichi tre volte, il giocatore che vi si ritrovi può chiedere che la partita termini in parità; va altresì notato che tale legge non impone alcun obbligo al riguardo. La sequenza in oggi può essere breve o lunga: prudentemente, la regola non ne specifica l’entità.

Lascia un commento