Finzioni

Il labirinto: la matematica del mito

(1882), il viaggiatore può in questa eventualità ritornare indietro, trattando l’incrocio già visitato

come un di un albero; il viaggiatore finge allora di spostarsi in un labirinto ad albero e si

cul-de-sac

riporta, come si dice, al caso precedente. Nulla gli può sfuggire.

S’insista ancora: i corridoi di allacciamento di Trémaux sono quegli stessi che, quando li si

percorre una prima volta, non costituiscono corridoi di scoperta di un incrocio; l’albero simulato è

ottenuto scollegandoli fittiziamente per farne quindi corridoi di scoperta di incroci fittizi.

Tutto sembra risolto, se non fosse che la matematica si applica a tutte le soluzioni possibili e

alle loro proprietà. Ora, questa «ritirata alla Trémaux» non è una necessità e non piace affatto a

quegli avventurosi che avrebbero preferito, al momento, prendere un corridoio libero piuttosto che

ritornare indietro. Tarry darà la risposta. I cicli, come suggerisce l’intuizione, offrono (e lo si vedrà

nel paragrafo seguente) numerose possibilità di varianti alla regola.

Il ruolo psicologico del ciclo nel labirinto è importante. Socialmente, il ciclo amalgama la

circolazione di un luogo pubblico o di una rete di scambio laddove le parti arborescenti della rete

stessa creano la segregazione. Nei film, il labirinto, che comunica l’affanno della ricerca continua, è

un ingrediente essenziale di Per Hitchcock come per Fellini è molto differente l’effetto fra

suspense.

l’incrociare i propri passi (ciclo) e il ritornare sui propri passi (albero).

Si sono classificati i labirinti in unicursali, arborescenti, di un numero ciclomatico k,

lasciando intendere che la complessità del dedalo cresce con Il labirinto più inestricabile è allora

k.

quello in cui i cicli crescono senza limite, quello stesso in cui il re degli Arabi abbandonò il re di

Babilonia, che si era preso gioco di lui facendolo prima smarrire in un dedalo architetturale di

grande lusso; egli lo portò in pieno deserto: «Oh, re del tempo…! In Babilonia mi volesti perdere in

un labirinto di bronzo con molte scale, porte e muri; ora, l’Onnipotente ha voluto ch’io ti mostrassi

il mio dove non ci sono scale da salire, né porte da forzare, né faticosi corridoi da percorrere, né

muri che ti vietano il passo» ( Borges). E lo abbandonò nel cuore del deserto.

L’evasione matematica dal labirinto

Le insufficienze della svolta a destra

Si racconta che è possibile uscire da un labirinto tenendo la mano destra continuamente in

contatto con la parete dei corridoi e degli incroci: prendere sempre il primo corridoio a destra. La

regola suppone due cose. Prima di tutto che il viaggiatore sia in un labirinto dove la destra e la

sinistra abbiano senso: deve trattarsi cioè di un labirinto tracciato in un piano senza ponti né tunnel,

o su una sfera senza manici. Poi, la regola suppone che il viaggiatore sia già sul ciclo-faccia che

comporta l’uscita! Un grafo piano divide infatti il piano in due regioni, e la mano destra del

viaggiatore del grafo prende contatto col bordo di una regione (la mano sinistra con il bordo di

un’altra regione) e camminare secondo una «prima a destra» (o «prima a sinistra») vuol dire girare

in tondo, percorrendo soltanto i corridoi che delimitano una regione; questi corridoi costituiscono

un ciclo-faccia del labirinto piano. Il viaggiatore troverà la porta della città soltanto se è

abbandonato in un luogo ove la sua mano destra ha contatto con la regione esteriore della città.

I sostenitori della regola del contatto potrebbero ribattere che dentro il palazzo di

Krokodipolis, come dentro le nostre stesse case, è possibile tenere la destra e arrivare così sempre

da qualche parte. È allora facile immaginare un appartamento su due piani con due scale agli

estremi, in modo che la regola del contatto conduca sempre a salire l’una ed a scendere dall’altra, a

percorrere al primo piano le parti disposte a sud e al secondo piano quelle disposte a nord, così da

mancare eventualmente «la porta» o «l’oggetto amato».

Per esplorare un grafo piano si potrà alternare: «prima a destra, prima a sinistra, ecc… »; nel

caso in cui il grafo non comporti cicli-cocicli, ogni corridoio sarà così percorso due volte, poiché

allora è descritta la «diagonale» del grafo piano. 17

Finzioni Il labirinto: la matematica del mito

La regola minimale che risolve tutti i labirinti

Ma quale regola occorre conoscere per risolvere un labirinto qualsiasi?

Risolvere un labirinto connesso significa percorrere, a partire da un incrocio di partenza, tutti i

corridoi una volta in ogni senso secondo una regola comune a tutti gl’incroci, non facendo uso che

di segni di passaggio nell’incrocio considerato. Si potrebbe pretendere di coprire il labirinto

percorrendo certi corridoi una volta sola; ciò non potrebbe essere che a profitto di certi cicli, poiché

il labirinto-albero non autorizza tali economie; ora, su un ciclo, ciò significherebbe una certa

memoria del viaggiatore, accertatesi che il ritorno sul ciclo non è indispensabile per esplorare

corridoi liberi che vi sarebbero incidenti. In questo modo ci si allontana dallo spirito labirintico per

tenere in considerazione soltanto «certe» eventualità. Dunque verrà imposto il doppio percorso di

ogni corridoio: un senso avanti che si chiama «esplorazione» e un senso indietro che si chiama

«ritirata». Al 1895 risale il

TEOREMA (regola di risoluzione dei labirinti di Tarry) A un incrocio prendere il corridoio di scoperta

dell’incrocio stesso soltanto come ultima possibilità.

Il corridoio di scoperta dell’incrocio è stato preso per definizione dapprima nel senso

x

«verso Sarà preso nel senso di «a partire da soltanto se tutti gli altri corridoi a partire da

x»:. x» x

sono già stati percorsi.

Prima di tutto si nota che la regola di Teseo dell’albero include proprio la regola di Terry e

che una cosa simile accade per la regola di Trémaux. Perciò infrangere la regola di Terry vorrà dire

fallire nei labirinti-alberi; essa è quindi necessaria. È anche sufficiente? Sí, e per tre ragioni: 1. il

viaggiatore non può trovarsi bloccato che all’incrocio di partenza, poiché in ogni altro incrocio in

cui si trovi, egli è arrivato una volta in più del numero di partenze, dunque al viaggiatore resta una

via d’uscita; 2. tutti i corridoi incidenti all’incrocio di partenza sono saturati (percorsi cioè nei due

sensi) poiché il viaggiatore vi è bloccato; e similmente per ogni corridoio incidente a un incrocio x

visitato, poiché è collegato all’incrocio di partenza da una catena di corridoi di scoperta che sono,

x

con un ragionamento progressivo a partire dall’incrocio di partenza, tutti saturati; 3. non potrebbe

esistere un incrocio non visitato, vicino a un incrocio nel quale tutti i corridoi incidenti sono

saturati; dunque tutti gli incroci sono visitati. Per le tre ragioni enunciate, il labirinto è risolto dalla

regola di Terry. Le tre regole non fanno altro che sfruttare in modo particolare la libertà di scelta in

un incrocio lasciata dalla regola di Tarry. A questo scopo sarà utile un po’ di terminologia relativa

alla struttura di monoide.

Il labirinto è una grammatica

La struttura matematica in cui si collocano gli oggetti prima considerati (corridoi, cammini,

fili, catene) è la struttura di monoide. I cammini sono delle parole che possono essere messe una

dopo l’altra, si dice concatenate, sotto certe condizioni grammaticali evidenti. La labirintologia

s’interessa alle particolari parole che ora verranno descritte.

Linguaggio “context-free” del cammino ,δ ) dove è un insieme finito (gli incroci);

Si chiama labirinto una quaterna = (V, + −

δ V

L A,

è un insieme finito di cardinalità pari, detto bialfabeto, i cui elementi – o lettere – sono accoppiati

A

a due a due (i due percorsi di un corridoio), due lettere accoppiate e essendo dette inverse, la qual

l k

è un’applicazione qualunque in in (δ (l) è l’incrocio alla

cosa si indica con = e = ; + +

δ V

l' k l k' A

fine del percorso che definisce tutte le incidenze del labirinto; e si deduce da mediante

− +

δ δ

l)

(l) = (l') per ogni lettera di

− +

δ δ l A.

18 Finzioni Il labirinto: la matematica del mito

Figura 7

Labirinto-grammatica

A un labirinto si associa una linguaggio costituito da: parole vuote, , definite per

Λ

L L v

ogni incrocio parole di una lettera, definite per ogni percorso di corridoio; e parole a lettere

v; l, l k

+ −

(percorsi di corridoi) ove per 1 2 1

δ δ

∈ = = −

k l l ...l ...l , l e l l i , ,...,k .

A

1 2 1

+

i k i i i

Si estende l’operazione di inversione a ponendo ( ) , ( ... ... ) ... ... .

′ ′ ′ ′ ′ ′

Λ = Λ =

l l l l l l l l

L 1 2 2 1

v v i k k i

( ) +

Allo stesso modo si estendono e ponendo = e ... , e per

+ − + +

δ δ δ δ δ σ

Λ = ∈

v, l l l l L,

1 2 k k

v

= Se = è detta ciclica.

− + + −

δ σ δ σ΄. δ σ δ σ, σ

Si ottiene pertanto in un’operazione interna di concatenazione non ovunque definita: se

L

e sono in è in se e solo se . In particolare, se è in (si è

+ −

σ σ σ σ δ σ δ σ σ σσ´

=

L, L L,

1 2 1 2 1 2

ripiegato completamente il filo su se stesso) è in e ciclica.

σ L,

Per il labirinto della figura 7 si hanno le parole , ecc.;

Λ fd, fde´e, fde´c´a,

p

è una parola di Tarry e non lo è. Il linguaggio associato al

a´ced´f´fbb´de´c´a a´ff´ced´bb´d´e´c´a L

labirinto è un linguaggio di Chomsky e Schützenberger poiché è generato da regole

L context-free

grammaticali formulate indipendentemente da ogni contesto, cioè da quanto, in una parola

trasformata, è lontano dal punto di trasformazione. Infatti, si prenda come alfabeto terminale, V

A

come alfabeto ausiliario, e si dia la scelta delle seguenti regole per ogni :

∈

context-free v V

+

, ( ), tale che = (l) (in particolare con gli incroci come assiomi di

−

δ δ

→ Λ → ∀ ∈

v v l l l v l´), v

A

v

partenza.

Si può dire che il labirinto è una grammatica che genera un linguaggio

L context-free

tutti i percorsi possibili del labirinto.

context-free L:

Parole nette, parole nulle

Si consideri un labirinto connesso Si chiama una parola del linguaggio tale

L. parola netta L

che ogni lettera del suo bialfabeto abbia una occorrenza esattamente (percorso di tutti i corridoi

A

una volta in ogni senso). Risolvere un labirinto consiste nel cercare una parola netta, seconda una

regola locale (di fatto non poiché il filo «tratta» nella regola le sue intersezioni col suo

context-free)

passato.

TEOREMA Una parola netta di labirinto è ciclica.

Infatti, ogni incrocio di è tante volte immagine secondo quante secondo delle lettere

+ −

δ δ

L

dell’alfabeto, dunque delle lettere di una parola netta Ora in la coppia identifica

σ. σ l l 1

+

i i

+ −

l’immagine e l' immagine , da cui la necessità di identificare e per garantire la

− +

δ δ δ σ δ σ

l l 1

+

i i

parità. 19

Finzioni Il labirinto: la matematica del mito

Si chiama di una parola tale che possa generare una parola vuota per

σ Λ

parola nulla L v

applicazione della regola grammaticale per qualunque. Evidentemente, una parola

σ σ σ σ

′ →

l l l

1 2 1 2

nulla è ciclica e = =

+ −

δ σ δ σ v.

Una parola nulla è senza nodo: Teseo ritornato dà il suo filo ad Arianna che tiene già l’altra

estremità del filo; ella tira insieme le due estremità; allora viene tutto il filo, se tutto il filo (parola

nulla) svolto da Teseo era effettivamente una parola nulla. Altrimenti ha un nodo. In generale una

parola di Tarry ha qualche nodo in questo senso. Una parola netta nulla del labirinto si chiama

soluzione di Arianna: essa risolve il labirinto, e si disfa quando la si tira completamente dalle due

estremità. Non è forse in questo modo che si immagina «il movimento della gru» da cui deriva la

visione del filo?

In tal modo funziona pure la struttura delle parentesi del linguaggio quotidiano; si apre una

parentesi per chiuderla in seguito; e se si apre una parentesi 2 nella parentesi 1, si chiude 2 prima di