Su Numeri e Giochi

Che si possa usare la matematica per parlare di giochi è una cosa abbastanza scontata, ma usare i giochi per parlare di numeri è qualcosa che poteva fare solo quel geniaccio di Conway, l’inventore del Game of Life (che, a dispetto del nome, non è un gioco ma un automa cellulare).

Lo fa nel suo On Numbers and Games, pubblicato dall’Academic Press nel 1976 (seconda ed. 1977), dove generalizza e fonde insieme la costruzione dei numeri reali ideata da Dedekind (alternativa a quella basata sulle sequenze di Cauchy) e quella dei numeri ordinali introdotta da Cantor e poi perfezionata da Von Neumann (che, sia detto per inciso, ebbe anche una parte rilevante nella nascita della teoria dei giochi e degli automi cellulari), dando così una definizione generale del concetto di numero, la quale comprende sia i reali che gli ordinali (e dunque numeri infiniti; ma anche numeri infinitesimali, come nell’analisi non-standard di A. Robinson – che in realtà è la “vera” analisi, quella di Leibniz) ed identifica i numeri come casi particolari di oggetti ancora più generali: i giochi, appunto.

Il libro è diviso in due parti: la parte “zeroesima” tratta dei numeri, e la prima parte dei giochi; cercherò di riassumere soltanto i concetti-base di entrambe, con qualche esempio qua e là (tra parentesi i riferimenti all’edizione del 1977).

Numeri

La prima definizione è abbastanza semplice: se L e R sono insiemi di numeri e nessun membro di L è maggiore o uguale a qualche membro di R, allora {L|R} è un numero; tutti i numeri sono costruiti così (p. 4). Convenzione: se x={L|R}, scriviamo e per indicare, rispetttivamente, i tipici membri di L e di R; quindi . (Perdoniamo WordPress per il pessimo allineameno LaTeX…)

Le definizioni seguenti sono un po’ più complicate e quindi vanno prese, per il momento, così come sono (in compenso, ometto quella della moltiplicazione):

• se e solo se non esiste un né un
• sse e
• sse e
• 
• 

Queste definizioni sono tutte spiegabili tenendo presente l’”interpretazione intesa” della notazione di Conway, in base alla quale ogni numero x si trova tra e , cioè . Una cosa interessante di queste definizioni è che sono induttive ma non richiedono alcuna base, dato che alla fine (o meglio, all’inizio) tutto si riduce a questioni su membri dell’insieme vuoto. Un’altra cosa interessante è che l’uguaglianza è una relazione definita (pp. 5-6).

Ma è giunto il momento di vedere alcuni esempi. Se ogni numero ha forma {L|R}, dove L e R sono insiemi di numeri, come si iniziano a costruire numeri… senza avere già a disposizione dei numeri? Facile: anche se non abbiamo numeri con cui partire, abbiamo pur sempre un insieme di numeri: l’insieme vuoto ∅. Dunque il primo numero sarà {|} (cioè {L|R} con L=R=∅), e ovviamente questo è il numero 0.

Per poter dire che 0 è un numero, però, bisogna verificare che rispetti la condizione che nessun membro di L sia maggiore o uguale a qualche membro di R; e le cose stanno proprio così, perché ∅ non ha membri, dunque in particolare non c’è un membro di ∅ che sia maggiore o uguale a qualche membro di ∅!

Inoltre perché, di nuovo, non esistono e tali che o (dal momento che e non esistono, punto). Similmente si dimostra che (p. 7).

Altri numeri: 1 e -1 sono rispettivamente {0|} e {|0} (cfr. la definizione di -x sopra). D’altra parte, {0|0} non è un numero, perché ; ma è pur sempre un gioco (vedi oltre)! Anche in questo caso tutto funziona come dovrebbe: per esempio, perché non c’è un né un ; mentre perché c’è un , cioè 0.

Ora, in generale si può immaginare che i numeri vengano costruiti in vari giorni, in modo tale che i numeri costruiti in un certo giorno abbiano nei rispettivi insiemi L e R numeri costruiti in giorni precedenti. Dunque il giorno 0 viene costruito il numero 0; il primo giorno vengono costruiti i numeri 1 e -1; il secondo giorno vengono costruiti i numeri 2, -2, 1/2 e -1/2 (infatti 2={1|}, -2={|-1}, 1/2={0|1}, -1/2={-1|0}); e così via (da notare che i numeri si possono scrivere in diversi modi; per esempio, si può verificare che è anche 2={0,1|}).

Prima di passare a numeri più interessanti, facciamo qualche somma: 1+0=0+1=1, perché (dato che non esistono). E, incredibile ma vero, !

Ma i giorni a disposizione sono veramente tanti, cosicché il giorno “nascono” il più piccolo ordinale infinito, cioè appunto , e l’infinitesimale ; inoltre nascono anche parecchi numeri reali, come , e (cfr. Fig. 0 a p. 11).

Basta così: per quanto i numeri siano belli, è ora di passare a qualcosa di più divertente.

Giochi

Ho già accennato al fatto che Conway costruisce i numeri come un caso particolare di giochi; dunque nella definizione dei secondi mancherà qualcosa rispetto a quella dei primi: si tratta della clausola che gli oggetti in L non debbano essere maggiori o uguali di quelli in R (i giochi, infatti, al contrario dei numeri, non sono linearmente ordinati).

La definizione, quindi, suona così: se L e R sono insiemi di giochi, allora {L|R} è un gioco. Prima di spiegare come va interpretata questa definizione, occorre fare una premessa: gli unici giochi considerati sono quelli per 2 giocatori, in cui non si può passare, senza patte né stalli, e che finiscono quando un giocatore al suo turno non può più muovere, cosicché la vittoria spetta al suo avversario (un gioco di questo tipo, ad esempio, è Sprouts). I due giocatori si chiamano Left e Right (o Black e White), e apprendiamo con lietezza che Conway simpatizza con Left.

Ora, ogni gioco ha degli stati, o posizioni; una posizione P è identificata dalle mosse che Left può fare partendo dalla posizione P e da quelle che può fare Right partendo dalla stessa posizione, in base alle regole del gioco; tali mosse sono rappresentate come le nuove posizioni a cui portano, le quali si chiamano rispettivamente le opzioni sinistre di P e le opzioni destre di P. Come nel caso dei numeri, le “tipiche” opzioni sinistra e destra di P sono chiamate, rispettivamente, e . Quindi per una data posizione P possiamo scrivere .

Ogni gioco G ha una posizione di partenza P; ma si può ottenere un gioco più breve G’ partendo invece da una qualsiasi altra posizione P’ di G: in tal caso identificheremo il gioco G’ con la posizione P’; allo stesso modo, identificheremo il gioco G con la posizione P: in generale, ogni gioco è identificabile con la propria posizione di partenza.

Dunque ogni gioco G può essere rappresentato da un albero (orientato), in cui ogni nodo è una posizione di G (la radice è la posizione di partenza); le frecce che partono da ciascun nodo P rappresentano le mosse legali per Left e per Right a partire da P, e i nodi a cui portano (i nodi “figli” di P) sono quindi le varie posizioni e . Sottintendendo che ciascun albero sia disegnato dal basso verso l’alto, al posto delle frecce si possono usare semplici spigoli, orientati verso sinistra o verso destra a seconda che rappresentino opzioni sinistre o destre (pp. 71-72).

Ed ecco i primi, elementari esempi (“rubo” la Fig. 4 a p. 72):

Anziché commentarli, lascio la parola all’autore, traducendone più o meno liberamente la spassosa spiegazione:

Il gioco più semplice di tutti è l’Endgame, . Ti offro cortesemente la prima mossa in questo gioco, e ti invito a farla. Tu perdi, ovviamente, perché è definito come il gioco in cui non è mai legale fare una mossa.
Nel gioco , c’è una mossa legale per Left, la quale conclude il gioco, ma non c’è mai una mossa legale per Right. Se io gioco come Left, e tu come Right, e hai di nuovo la prima mossa (mi sembra giusto, visto che hai perso la partita precedente), perderai ancora, essendo incapacitato a muovere perfino dalla posizione iniaziale. Per dimostrare la mia abilità, ora inizierò dalla stessa posizione, farò la mia mossa legale verso , e ti inviterò a fare la tua.
Naturalmente adesso starai iniziando a sospettare che Left vince sempre, quindi nel nostro prossimo gioco, , tu puoi giocare come Left e io come Right! Nell’ultimo dei nostri esempi, , puoi giocare scegliendo il ruolo che desideri, purché per questo privilegio mi permetti di giocare per primo.

Riassumendo, abbiamo i seguenti esiti:

• Nel gioco c’è una strategia vincente per il giocatore che muove per secondo
• Nel gioco c’è una strategia vincente per Left (chiunque inizi)
• Nel gioco c’è una strategia vincente per Right (chiunque inizi)
• Nel gioco c’è una stretegia vincente per il giocatore che muove per primo

In generale, per ogni gioco G si può verificare una di queste quattro situazioni (ce lo assicura il Teorema 50 a p. 73):

• (G è positivo): esiste una strategia vincente per Left
• (G è negativo): esiste una strategia vincente per Right
• (G è zero): esiste una strategia vincente per il secondo giocatore
• (G è fuzzy): esiste una strategia vincente per il primo giocatore

Anche per i giochi si possono definire alcune operazioni. Dato un gioco G, il suo negativo -G è definito dall’equazione : Left e Right si scambiano i ruoli. È anche possibile giocare più giochi contemporaneamente: per giocare la somma (disgiunta) , ogni giocatore al proprio turno seleziona uno dei due componenti e (possiamo immaginarli come due giochi separati, per es. giocati simultaneamente su due scacchiere diverse) e fa una mossa che per lui sia legale in quel componente; un giocatore perde nel gioco quando non può più muovere in nessuno dei due componenti (pp. 73-74).

Finora ho mostrato solo esempi astratti di giochi; vediamo allora almeno un esempio concreto: Domineering. Si tratta di un gioco da giocare con le tessere del Domino, dove Left e Right si alternano piazzando una tessera a turno su una scacchiera rettangolare, il primo verticalmente e il secondo orizzontalmente (senza sovrapporre le tessere); come sempre, l’ultimo giocatore che riesce a muovere è il vincitore.

Man mano che il gioco procede la scacchiera viene suddivisa in varie porzioni libere non connesse tra loro; allora il gioco sarà di fatto la somma disgiunta di vari sotto-giochi, uno per ogni porzione libera (pp.74-75).

La porzione più piccola possibile è costituita da una sola casella:

Giocando in questa porzione, naturalmente, si gioca al gioco , in cui nessuno dei due giocatori può fare una mossa (ovviamente, dunque, i giocatori ignoreranno tutte le porzioni siffatte).

In una porzione come questa:

c’è solamente una mossa possibile per Left (che consiste nel riempirla tutta, ottenendo così una porzione “nulla”, che è un altro esempio del gioco ), ma nessuna mossa per Right. Tale porzone corrisponde quindi al gioco , ed infatti il valore (per Left) del gioco giocabile su di essa è 1, perché Left ha esattamente una mossa di vantaggio su Right.

D’altra parte, in questa porzione di scacchiera:

ci sono due mosse a disposizione per Right (e nessuna per Left): giocare una tessera al centro, ottenendo due porzioni sconnesse costituite ognuna da una singola casella (e quindi il gioco ), oppure a una delle due estremità, ottenendo una singola porzione costituita da due caselle adiacenti (e quindi il gioco , dove Right ha ancora una mossa a disposizione); il valore del gioco giocabile in questa porzione, dunque, è -2 (ricordiamo che uno dei modi per scrivere è ; quindi, similmente, ): Right sta “due mosse avanti” rispetto a Left, che quindi sta “due mosse indietro”.

La situazione è un po’ più complessa in questa porzione:

Qui possono iniziare sia Left che Right (cioè, diversamente dagli esempi precedenti, ci sono mosse “non vuote” legali per entrambi). Left ha due mosse (ovviamente, nella parte verticale della “L”) : occupare le prime due caselle dall’alto oppure occupare le prime due caselle dal basso. Nel primo caso, lascia vuote due caselle adiacenti in orizzontale (il gioco ), quindi una mossa per Right; la seconda opzione è invece più vantaggiosa, perché lascia due caselle vuote sconnesse (quella più in alto di tutte e quella in basso a destra), cioè il gioco , dove Right non ha nessuna mossa legale da fare. D’altro canto, Right ha soltanto una mossa a disposizione: piazzare una tessera sulle due caselle in basso, lasciando così il gioco a Left (le due caselle adiacenti in alto a sinistra).

Ricapitolando, Left può muovere lasciando a Right il gioco o il gioco ; nel primo caso vincerebbe, nel secondo perderebbe. Right, invece, può solo muovere lasciando a Left il gioco e quindi la vittoria assicurata. Dunque la porzione “a L” ha valore ; infatti, considerando solo la strategia migliore per Left (passando ai numeri, si può scrivere anche , perché basta sapere che 1/2 sta tra 0 e 1, quindi la presenza di -1 è irrilevante; tornando ai giochi: perché mai considerare il valore -1 quando c’è un gioco di valore maggiore, cioè 0?), gli esiti possibili sono se inizia Left e se inizia Right: in ogni caso una vittoria per Left, ma con un vantaggio di 0 mosse nel primo caso e di 1 nel secondo, quindi con valore medio pari a 1/2 (un esempio concreto di una porzione di gioco con valore 1/2 – seppure con un modo abbastanza complicato di calcolarlo – è il “ko da mezzo punto” nel gioco del Go).

Da notare, infine, che non tutti i “valori” dei giochi sono numerici come quelli visti in questi esempi (infatti, non tutti i giochi sono numeri). Per esempio, il valore di una configurazione “a L corta” (cioè come quella dell’ultimo esempio, ma senza la casella superiore) è (provare per credere!), mentre il valore di un gioco su una scacchiera 2×2 è : entrambi i giochi sono fuzzy.

Concluderò raccontandovi del Teorema 51 (pp. 75-76), il cui enunciato è molto semplice: per ogni gioco G,

Banale, no? Ma è un po’ meno banale capire cosa vuol dire questa profonda verità ludoteoretica: si tratta della cosiddetta copycat strategy, messa in pratica (così si narra, o almeno così narra Conway) da una bambina che affrontò due campioni di scacchi contemporaneamente, impegnandosi a vincere con almeno uno dei due; e in effetti così fu, perché la bambina giocò come nero contro uno (il giocatore iniziale) e come bianco contro l’altro, copiando le mosse dell’uno nella partita con l’altro (quindi sostanzialmente facendo da tramite tra i due giocatori, che giocavano di fatto l’uno contro l’altro). La vittoria del “giocatore copione” in una situazione di questo tipo è sempre certa, escludendo la possibilità di stallo e dunque pareggio (quindi con gli Scacchi Cinesi, dove lo stallo non implica il pareggio – come negli Scacchi – ma la sconfitta del giocatore che non può più muovere, il trucco funzionerebbe sempre e comunque).

Il gioco G-G menzionato dal teorema non è altro che G+(-G), cioè due copie del gioco G (quale che esso sia) giocate simultaneamente su due scacchiere identiche, in cui una mossa legale per Left in G diventa legale per Right in -G (cfr. definizione di -G), perché nei due giochi i giocatori si invertono i ruoli. Il gioco G-G sarà sempre vinto dal secondo giocatore (quindi ha valore 0), come nell’esempio della bambina (che infatti muove per seconda), se questi adotta la copycat strategy! La differenza rispetto al simpatico aneddoto scacchistico è che qui i due campioni sono la stessa persona: quel che avviene è che il secondo giocatore “ruba” la strategia al primo, applicandola contro di lui.

Questo concetto, in modo simile ma opposto, viene sfruttato nell’argomento della strategia rubata (dovuto a John Nash), grazie a cui si dimostra che in certi giochi (come l’Hex) esiste una strategia vincente per il primo giocatore: se così non fosse, esisterebbe una strategia vincente per il secondo (poiché non si può pattare); ma allora il primo può “sottrargliela” copiandola, dato che la mossa iniziale non può costituire uno svantaggio (è una pedina in più), e avere così una strategia vincente: contraddizione (piccola nota di logica: quest’argomento è un caso di consequentia mirabilis).

P.s.: apprendo or ora dal Web che i numeri costruiti da Conway si chiamano numeri surreali, e che sono stati chiamati così da D. Knuth (inventore del TeX, il motore tipografico alla base del LaTeX) in un libro dal titolo Surreal Numbers: How two ex-students turned on to pure mathematics and found total happiness.

P.p.s.: detto questo, per quanto sia interessante Domineering, credo proprio che Dominion rimanga decisamente più entusiasmante… ; )

(post clonato dal mio mini-blog ludico)

Sandman e la sua biblioteca

Overture.

Sandman è un fumetto degli anni ’90 pubblicato dalla DC comics e scritto da Neil Gaiman: a mio avviso la più bella serie di fumetti mai scritta; ma il tema di questo blog è un altro ed allora non mi dilungo più del necessario in sperticate lodi.

Sandman è Morfeo: è Sogno. Sandman possiede un biblioteca infinita che contiene ogni libro che sia mai stato scritto e non solo. Sandman possiede ogni versione d’ogni libro che sia mai stato scritto, ma anche ogni versione dei libri che siano solo pensati, immaginati o sognati. Per me, divoratore di libri sin da bambino, una simile biblioteca è uno dei tesori più grandi in possesso di Morfeo. Mentre è evidente a tutti che una cosa simile non può che esistere nel Sogno… O no?

Introduzione
Raccontare bene quello che ho in mente rchiede un po’ di conoscenze sui numeri. Conoscenze che sicuramente si possono raccontare più in dettaglio: un piccolo dettaglio è questo.
Vediamo, invece, cosa sia il minimo indispensabile: la trascendenza di . è una costate che viene fuori dividendo il perimetro di una circonferenza per il suo diametro; sappiamo fin dalle scuole elementare che

Dove è il perimetro della circonferenza, e il suo raggio; è la costante di cui parliamo e che (alle scuole elementari) ci dissero che vale . Il fatto è che ha numerose cifre dopo il , infinite altre per la precisione: è un numero decimale illimitato non periodico; cioè le cifre di dopo la virgola non sono solo infinite, ma neppure si ripetono ciclicamente. Insomma è molto diverso da che pur avendo infinite cifre decimali, queste sono tutte uguali fra loro.

Calcoliamo ?
Ciò che più sorprende di non è il fatto di essere illimitato e non periodico, numeri con questa proprietà ve ne sono a iosa (per esempio ), quanto la difficoltà che si incontra nel calcolare le sue cifre: al momento non esiste alcun modo di conoscere l’-esima cifra di se non calcolando prima tutte le precedenti! Non solo: si congettura che una formula che fornisca l’-esima cifra di senza dover conoscere tutte le cifre precedenti non esista affatto!

Volendo essere più tecnici si congettura che l’entropia di sia massima, pur essendo minima la sua complessità di Kolmogorf. L’applicazione di questa congettura, per tornare a parlare un linguaggio comprensibile, è che qualunque sequenza numerica finita esiste all’interno di . Per esempio la mi data di nascita espressa come gg/mm/aaaa parte dalla -esima cifra decimale; pur avendo a disposizione solo una quantità limitata di cifre, chiunque può fare qualche esperimento. Per esempio su questo sito.

Applicazioni
Dunque, sebbene il vantaggio sia poco o nullo, potremmo evitare di ricordare delle sequenza numeriche, come il codice del bancomat o qualche numero di telefono, ma ricordare la loro posizione su .
In effetti ogni programma è interpretato dal computer come una sequenza numerica, ed allora questa sequenza numerica può essere ritrovata su : non è necessario salvare alcun genere di file: basta salvare la posizione che occupa su .
Tenendo conto della dovuta codifica, in si può trovare ogni cosa: le foto delle mie vacanze, il testo della divina commedia, i fascicoli segreti della CIA sugli UFO e su JFK, la dimostrazione del teorema di Banach-Tarski, e ancora e ancora e ancora…

Preveggenza?
Pare che su ci sia tutto, dalle banalità scritte ogni giorno da ognuno di noi alle più grandi verità mai pensate da mente umana… Forse anche dell’altro: per esempio ci sono i titoli dei giornali di domani e la dimostrazione della congettura di Goldbach.
Ma allora imparare a “leggere” permetterebbe di leggere il futuro? In pratica bisogna fare molta attenzione perchè in c’è scritto tutto e dunque anche tutte le cose false. Per quanto riguarda la dimostrazione della congettura di Goldbach dovremo scorrere attentamente tutta la dimostrazione che quel pezzo di ci propone per essere certi che sia priva di errori. Per quanto riguarda i titoli dei giornali dovremo aspettare l’indomani per scoprire se quel pezzo di sono realmente i titoli dei giornali o solo una loro copia farlocca!
L’esempio più evidente della situazione sono i numeri del superenalotto: praticamente ogni pezzetto di potrebbe essere interpretato come i numeri della prossima estrazione, ma questo non vuol dire affatto che lo siano davvero!

Allora… la Biblioteca esiste!
Che non fornisca previsioni affidabili fa molto pensare… in effetti in c’è proprio tutto: ci sono molte sequenze che sembrano essere cose note ed importanti ma che in realtà non sono proprio nulla; c’è una sequenza che “sembra” I promessi sposi ma che non lo è perchè manca tutta la punteggiatura.
Pensandoci ancora ci rendiamo conto che se contiene questa strana versione dei promessi sposi allora conterrà tutte le versioni del romanzo, da “Fermo e Lucia” a tutte le altre che il Manzoni aveva potuto immaginare o sognare.

La Biblioteca di Sandman è una realtà ed è contenuta in !

Quando la matematica non c’entra (problemi esistenziali)

Inauguro la categoria “Logica” con questo post un po’ tecnico, ma forse utile per chiunque voglia togliersi qualche dubbio sui vari quantificatori utilizzati nel matematichese corrente. Trattasi, in realtà, di una manciata di osservazioni alquanto banali sul “potere espressivo” della logica (classica) del primo ordine, le quali vanno considerate più che altro come una curiosità o, meglio ancora, come una scusa per “giocare” coi quantificatori.

 

http://www.xkcd.com/764/

In una delle tante serate ludiche di quest’estate parlavamo con satiro del fatto che a volte (anche in un discorso formale) si possono menzionare dei numeri senza effettivamente parlare di numeri. Con quest’affermazione dal sapore alquanto paradossale (o, fuori di un contesto formale, banale) intendo semplicemente dire che alcune asserzioni contenenti numeri possono essere fatte senza tirare in ballo la matematica, bensì all’interno della pura logica (con “matematica” intendo l’aritmetica di Peano del primo ordine e con “logica” intendo la logica dei predicati del primo ordine con identità).

Ma entriamo subito nel vivo della questione: il menù del giorno prevede come portate principali i tre quantificatori “esiste almeno“, “esiste esattamente“, “esiste al più“, per i quali userò rispettivamente queste notazioni:

Tu in che classe stai?

Ci sono due casi in cui tipicamente sentirete fare una domanda del genere: quando una liceale tenta goffamente di attaccare bottone con un ragazzo della stessa scuola, o quando uno studioso di complessità computazionale è alle prese con un problema, come per esempio il problema del commesso viaggiatore, a.k.a. TSP (traveling salesman problem). In questo post vi parlerò del secondo caso.

TSP gode di una proprietà molto interessante, vale a dire la seguente: “se x trova una soluzione efficiente di TSP, x guadagna un milione di dollari; se x dimostra che una tale soluzione non esiste, x guadagna un milione di dollari“.

Infatti, TSP (enunciato come problema di decisione) è un problema NP-completo, ovvero un problema in NP tale che ogni problema in NP è riducibile ad esso (cioè, se risolvi TSP, risolvi anche tutti gli altri). Dunque, se si trova una soluzione efficiente di TSP, si dimostra che sta in P, e quindi che ci stanno anche tutti gli altri problemi che stanno in NP; mentre, se si dimostra che tale soluzione non esiste, si ha almeno un esempio di un problema in NP che non è in P; in ogni caso, si risponde finalmente alla famigerata domanda:

Ma cosa sono, di preciso, P e NP? Beh, sono appunto classi di complessità, e sono il vero argomento di questo post…

Argomento Diagonale

L’argomento diagonale non è un modo per uscirsene da un discorso con qualcosa che non c’entra nulla. Piuttosto è una tecnica dimostrativa ideata da Cantor, poi rivisitata e riutilizzata in altri contesti: in particolare l’argomento diagonale gioca un ruolo fondamentale nella dimostrazione del Teorema di Incompletezza di Godel.
In questo post voglio presentare la dimostrazione di Cantor in cui si utilizza l’argomento diagonale.

Il problema è la numerabilità dei numeri irrazionali: questi non sono una quantità numerabile, sono “molti di più”, con la conseguenza che ogni volta che si sceglie a caso un numero reale questo è certamente un irrazionale.

Supponiamo di fare una lista dei numeri irrazionali, allora avremo qualcosa tipo:

Costruiamo il numero “diagonale”. Scegliamo dal primo numero, dal secondo, dal terzo e così via: dall’ -esimo numero della lista scegliamo la sua -esima cifra dopo la virgola; in questo modo possiamo scrivere il numero

Per ottenere il numero “diagonale” occorre ancora un passaggio: cambiare tutte le cifre al numero sovrastante: per esempio aggiungendo il valore a ciascuna e in caso di sostituirlo con . Il numero diagonale è

Per concludere la dimostrazione basta chiedersi in quale punto della lista comparirà il numero “diagonale”. Questo non può apparire in nessun punto perchè, per ogni valore di , il numero “diagonale” è diverso dall’-esimo numero della lista: infatti la loro -esima cifra è diversa.

Bene, o forse, Male. Comunque la lista, per quanto fosse infinita, mancava di un numero; neppure basta “aggiungerlo” da qualche parte nella lista: la nuova lista avrebbe un nuovo numero “diagonale” che non sarebbe compreso nella lista… E guarda un po’, questo genere di mancanze irresolubili, sono alla base del Teorema di Incompletezza di Godel

anim.orc.bots

Vi propongo l’indovinello logico più difficile che conosco, copiaincollandolo tal quale dalla Tana dei Goblin, dove l’ho postato la prima volta. In rosso trovate anagrammi che alludono alla mia identità, nonché all’autore e al titolo del libro da cui ho tratto l’arduo quesito (chi potrà mai essere?;). Buona spremuta di meningi.

 

---

 

Dal Diario Interattivo di Viola F. Redlab:

08.09.2112: Stavo viaggiando alla volta di Feu Prox Zharhaqq e, devo ammetterlo, manovravo i biocomandi del mio cargo in modo abbastanza scriteriato (per me era diventato infatti assolutamente prioritario sbarazzarmi al più presto di quello scottante stock di armi psioniche che ero stata incaricata di consegnare al distaccamento della Ya**za s.r.l. ospitato da quello sperduto pianeta…), quando mi imbatto in un’ Entità Semidivina di classe C3.

Non era mai stato avvistato un Trono così vicino al Sistema Solare e chi, se non io con la mia dannata sfortuna, poteva non solo incontrarlo, ma anche coinvolgerlo in un incidente spaziale come non se ne vedevano dal disastro asteroidale del ’97?

In breve: il mio cargo trapassa letteralmente il Trono, rimanendo completamente avvolto in una brodaglia emiteoplasmatica che danneggia le sinapsi dei biocomandi, le psioarmi nella stiva, nonchè la maggior parte delle convinzioni etiche che avevo recentemente downloadato… Cosicchè cargo, armi e la sottoscritta si ritrovano a precipitare nell’esosfera di Lamda Sol Ymruynn, un pianetucolo di terza generazione.

I tuoi occhi sono blu come il cielo

John Tyndall (a cui devo il nick che uso su wordpress) era uno scienziato inglese, che è noto ai più per l’effetto che porta il suo nome. Di solito viene identificato con effetto Tyndall il fenomeno con cui si “vedono” i raggi di sole attraverso le nuvole, anche se – più precisamente – l’effetto Tyndall è lo scattering della luce dalle particelle in un colloide. Ora, le particelle in un colloide sono (molto) più piccole della lunghezza d’onda della luce incidente, a differenza della particelle di polvere che producono i raggi di sole tra le nuvole. In effetti, questi ultimi sono causati più da una riflessione che da uno scattering. Se mentre spazzate una stanza osservate la luce che entra attraverso le tapparelle, potete vedere un finto effetto Tyndall domestico, causato dalla particelle di polvere che avete messo in sospensione (a meno che non stiate usando dei prodotti all’avanguardia. Un motivo in più per non usare Swiffer.).

Prima che lo scattering si applichi anche all’informazione di questo post e finisca a parlare di quali prodotti sono meglio per combattere il calcare, torniamo al Nostro. Dirigendo della luce bianca su una tanica di latte (che è un colloide), Tyndall scoprì che se guardava “di lato” vedeva una tonalità decisamente bluastra, mentre se si allineava con la direzione della luce, il latte assumeva un colorito rossastro. Era dai tempi di Newton che si sapeva che la luce era composta di diverse componenti e quello che Tyndall capì era che, quando la luce attraversa un colloide, le componenti a frequenze più alte (blu-viola) vengono rifratte più di quelle basse (rosso). Nelle sue parole:

238. The waves of ether generated by luminous bodies are not all of the same length; some are longer than others. In refracting substances the short waves are more retarded than the long ones; hence the short waves are more refracted than the long ones. This is the cause of dispersion.

Notes of a course of nine lectures on light delivered at the Royal institution of Great Britain April 8-June 3, 1869 (1870)

In effetti Rayleigh, che studiò più seriamente il problema, riuscì a dimostrare che l’ammontare di luce diffusa cresce con la quarta potenza della frequenza (l’inverso della lunghezza d’onda). Automaticamente, il passo successivo fu supporre che il cielo fosse blu per lo stesso motivo. L’idea era semplicemente che piccole particelle di polvere o goccioline d’acqua in sospensione potessero agire come le particelle di grasso nel latte. Come lui stesso ha scritto

We have now to imagine light undulations of different dimensions, but all exceedingly minute, passing through air laden with extremely small particles. It is plain that such particles, though scattering portions of all the waves, will exert their most conspicuous action upon the smallest ones; and that the colour-sensation answering to the smallest waves in other words, the colour blue will be predominant in the scattered light. This harmonises perfectly with what we observe in the firmament. The sky is blue, but the blue is not pure.

Fragments of Science, Vol I sixth ed., D. Appleton and Co. (1892)

L’unico problema era che se così fosse stato, avremmo dovuto osservare una maggior variazione nel colore al variare delle condizioni atmosferiche (umidità relativa, nebbia, …). La vera spiegazione è che gli agenti diffusivi sono le molecole di acqua e azoto dell’atmosfera. Quindi sì, il cielo è blu per via dell’effetto Tyndall, anche se Tyndall stesso aveva frainteso l’origine della diffusione!

Certo, direte voi, ma allora perché il cielo non è viola, visto che la frequenza del viola è più alta? A parte che – o proprio a causa di – avere un cielo viola potrebbe avere effetti sul nostro umore, il motivo è nascosto nei nostri occhi. I recettori sulla retina sono sostanzialmente sensibili a tre colori: verde, rosso e blu. La luce che arriva diffusa dal cielo stimola maggiormente i recettori del blu, e in misura minore gli altri due. Il risultato è la combinazione di questi tre: il verde e il rosso spostano leggermente il blu verso le frequenze minori, con il risultato di avere il cielo azzurro.

Concludendo, e per tornare al titolo del post: l’iride non è blu, non contiene cioè alcun pigmento blu. Negli occhi la luce che entra viene diffusa dalle particelle presenti nell’iride. In particolare, la luce può essere diffusa al punto da riemergere verso l’esterno dell’occhio. Come sopra, lo scattering è più forte per le frequenze elevate, il che spiega il blu. Per quanto riguarda gli occhi verdi o marroni, sono dovuti alla presenza di pigmenti gialli o marroni nello stroma nonché alla maggiore quantità di melanina. Nel 1924 Mason ha studiato la questione con metodi che farebbero rabbrividire gli animalisti. In ogni caso, una delle conclusioni era che

The blue color is the color of turbid media (Tyndall blue) and is localized in the stroma.

C.W.Mason, Blue eyes, J. Phys. Chem., 1924, 28 (5), pp 498–501

Adesso, la prossima volta che guarderete rapiti la vostra ragazza, ditele che i suoi occhi sono azzurri come il cielo per via dell’effetto Tyndall.

Donna o Tigre? (primo giorno, prima prova)

Sono fortunosamente venuto in possesso di una copia di “Donna o Tigre?”, quindi condividerò con voi il primo indovinello della sezione “Ladies or Tigers?”, abbastanza facile.

Ladies or Tigers?

Many of you are familiar with Frank Stockton’s story “The
Lady or the Tiger?,” in which the prisoner must choose be­-
tween two rooms, one of which contains a lady and the other
a tiger. If he chooses the former, he marries the lady; if he
chooses the latter, he (probably) gets eaten by the tiger.
The king of a certain land had also read the story, and it
gave him an idea. “Just the perfect way to try my prisoners!”
he said one day to his minister. “Only, I won’t leave it to
chance; I’ll have signs on the doors of the rooms, and in each
case I’ll tell the prisoner certain facts about the signs. If the
prisoner is clever and can reason logically, he’ll save his
life – and win a nice bride to boot!”
“Excellent idea!” said the minister.

Difficoltà computazionali

Da piccolo ero un matematico puro e gli unici numeri con cui avevo a che fare erano e . Calcoli da affrontare, nemmeno a parlarne.

Eppure alcune problematiche legate al calcolo già le conoscevo: il problema del commesso viaggiatore, la fattorizzazione dei numeri naturali. Entrambi questi problemi mostrano la medesima difficoltà: per trovare la soluzione giusta non sembra esserci altra via che provare tutte le alternative. Alternative, fra l’altro che crescono smodatamente in fretta: come l’esponenziale per essere esatti.
Da un punto di vista pratico la domanda alla base è: Quale che sia il problema esiste sempre un metodo per risolverlo?
Da un punto di vista più formale la stessa domanda è: Esistono problemi intrinsecamente non-polinomiali?

Che io sappia manca ancora una soluzione a questo problema, ma passare dal non-polinomiale al polinomiale, nella pratica delle cose, non è una soluzione sufficiente.

Generatore di indovinelli

Tempo fa si parlava tra di noi di grammatiche libere dal contesto, della loro potenza e del divertimento che possono suscitare grazie al Polygen (http://www.polygen.org/).

Per dare un esempio della cosa, eccovi il mio generatore casuale di indovinelli (alla Smullyan, naturalmente: è il minimo che in questo blog gli si renda omaggio).

Per usarlo, scaricate ed installate l’eseguibile del Polygen dal summenzionato sito, scaricate e piazzate in un posto opportuno il file indogen.doc qui allegato, infine da terminale date il comando: polygen indogen.doc .

(N.B.: il file indogen.doc va salvato direttamente, e non aperto con un word processor e poi salvato da lì – questo perché si tratta di un file di testo semplice, e deve rimanere tale! (ha estensione DOC unicamente al fine di “ingannare” WordPress;))

È tutto. Buona generazione.