» Esercizi svolti di Matematica e Fisica

[¯|¯] L'insieme di Cantor quale Macchina ricorsiva topologica

Aprile 13th, 2017 | by Marcello Colozzo |

Scrivere un programma in ambiente Mathematica che "prende" un segmento di lunghezza unitario, lo divide in tre parti uguali e ne toglie quello di mezzo. Quindi riapplica il procedimento ai due "pezzi" rimasti, dopodichè riapplica il procedimento ai quattro pezzi rimasti, dopodiché riapplica il procedimento agli otto pezzi rimasti,
riapplica il procedimento ai 2^k pezzi rimasti.... all'infinito....

Sembra facile... In realtà qui entra in gioco il concetto di Macchina ricorsiva con la differenza che ora abbiamo una Macchina ricorsiva topologica. Infatti:
Consideriamo una funzione reale di una variabile reale

f è una legge che a ogni elemento x dell'insieme X associa univocamente il numero reale f(x) e che può essere schematizzata attraverso il diagramma orientato di fig. 1 in cui la variabile indipendente x si comporta alla stregua di un input che viene processato da f che a sua volta, emette l'output f(x). Per come abbiamo impostato la legge f, l'output f(x) è univocamente determinato dall'input x.

Ora immaginiamo di reindirizzare l'output f(x) all'ingresso, secondo lo schema del diagramma orientato di fig. 2.

Se impostiamo un valore iniziale x₀ dell'input, eseguendo n passi:

Notiamo che per un qualunque valore iniziale x, ciò equivale ad eseguire la composizione n-esima di f con se stessa, per cui abbiamo la funzione composta:

e quindi la successione di funzioni

dove

Tale procedura definisce una macchina ricorsiva. Se la funzione f verifica le ipotesi del teorema del punto fisso di Brouwer , si ha che la predetta successione converge a una funzione costante. Precisamente:

essendo ξ l'unica radice dell'equazione x=f(x). L'ambiente di calcolo Mathematica gestisce molto bene i processi ricorsivi attraverso l'istruzione Nest.

***
Per quanto visto nei numeri precedenti, l'insieme di Cantor C è ottenuto tramite un procedimento ricorsivo. Infatti, osserviamo che C può essere scritto come:

dove










A ogni passo abbiamo 2^k intervalli di ampiezza b_j^(k)-a_j^(k)=3^-k. Ciò premesso, assumendo un riferimento cartesiano ortogonale R(Oxy), possiamo considerare una legge f che a un segmento (intervallo) dell'asse x, associa univocamente un altro segmento. In simboli:

dove Σ è l'insieme dei segmenti contenuti nell'asse x o ciò che è lo stesso, l'insieme degli intervalli chiusi e limitati contenuti in R:

Quindi scriviamo

Si noti che la legge f è un'applicazione a tutti gli effetti con la differenza (rispetto al caso precedente) che agisce su segmenti, anziché su numeri. A questo punto è facile definire una macchina ricorsiva topologica reindirizzando l'uscita all'ingresso:

dove [a₀,b₀] è un intervallo iniziale. D'altra parte, la legge:

è univocamente determinata dalla coppia ordinata di funzioni reali di una variabile reale (f₁,f₂) tali che

Ne consegue che la macchina ricorsiva topologica che stiamo considerando equivale alla coppia ordinata di macchine ricorsive numeriche caratterizzate dalle funzioni reali f₁ e f₁:

La macchina di Cantor è più complicata della macchina ricorsiva appena esaminata, poiché a ogni iterazione non restituisce un solo segmento, ma 2^k segmenti, dove k è la variabile di iterazione (iteratore). Ancora una volta ci viene in aiuto l'ambiente di calcolo Mathematica, grazie alla sua capacità di trattare funzioni il cui argomento è un segmento. In generale, comunque prendiamo a e b in R con b>a, l'insieme {a,b} è interpretato da Mathematica con l'head List. Infatti:

Per quanto visto, il procedimento di Cantor consiste nel prendere un segmento [a,b] dividerlo in tre parti uguali e rimuovere la parte centrale. Definiamo allora la funzione:

Ad esempio

che è proprio quello che volevamo, a patto di osservare che tale funzione restituisce l'insieme degli estremi degli intervalli e non gli intervalli. Riapplichiamo il procedimento i.e. la funzione f al suo output:

che è un risultato corretto a meno di livelli di annidamento che possono essere rimossi tramite l'istruzione Flatten. Appare chiaro a questo punto che l'insieme di Cantor è una macchina ricorsiva, poichè per un assegnato input che denotiamo con x₀, la funzione emette un output f(x₀) che viene poi riprocessato calcolando f(f(x₀)) e così via all'infinito. Tutto questo ci rimanda al comando Nest, con la differenza che qui abbiamo una funzione il cui argomento è una lista e non un numero. Possiamo utilizzare il comando Map in modo da forzare f ad agire sul proprio output:

"Flattando":

Risultato non corretto, in quanto Flatten elimina tutti i livelli di annidamento, mentre dobbiamo eliminarne solo uno. Perciò fissiamo l'ordine di annidamento a 1:

che è il risultato corretto. Ciò suggerisce di definire la funzione:

Risultati corretti! Ora siamo in grado di utilizzare Nest in modo da implementare la macchina ricorsiva:

L'intero naturale n definisce la n-esima iterazione. Ad esempio:

che è, appunto, la prima iterazione. Siccome non possiamo utilizzare g1 per n=0, conviene utilizzare l'istruzione Which

Per quanto detto prima, ciò che abbiamo prodotto è l'insieme degli estremi degli intervalli generati a ogni ricorsione, ma a noi interessano gli intervalli per poi essere disegnati utilizzando la primitiva grafica Line. Ad esempio, per disegnare il segmento di estremi 0 e 1 dobbiamo innanzitutto assegnare un riferimento cartesiano ortogonale del piano Oxy, per cui le coordinate cartesiane degli estremi sono (0,0) e (1,0). In questo caso specifico, la sintassi è

Ci sono due modi per graficare il segmento in questione. La prima consiste nel processarlo attraverso l'istruzione Graphics:

Notiamo che l'istruzione Graphics ha l'attributo Listable, e ciò è utile perchè permette di inserire le opzioni ed eventualmente altre primitive come ad esempio:

Il secondo approccio utilizza il comando Epilog nell'istruzione grafica Plot. Il fatto di non dover graficare alcuna funzione, equivale per Mathematica a graficare la funzione Null

Ora cancelliamo tutte le variabili definite sopra:

Prima di implementare l'insieme di Cantor, consideriamo una generica macchina ricorsiva topologica. Ad esempio:

Non restituisce il risultato corretto per via delle parentesi {} che però, sono necessarie. Nel caso contrario, non è possibile utilizzare l'istruzione Map che definisce la funzione g. Dobbiamo allora dare l'attributo Listable alla funzione f, in modo da bypassare le parentesi.

Ora siamo in grado di implementare la Macchina di Cantor.

Il codice funziona in parte, poiché restituisce solo uno dei segmenti.

Procediamo quindi come nel caso precedente, defininendo:

Anche in questo caso non possiamo utilizzare g1 per n=0, per cui utilizziamo l'istruzione Which

Utilizzando l'istruzione Table si può generare una lista di iterazione per poi esportarla in formato gif, riproducendo l'animazione grafica di fig. 3.

Sostienici

Puoi contribuire all’uscita di nuovi articoli ed e-books gratuiti che il nostro staff potrà mettere a disposizione per te e migliaia di altri lettori.

---

Tags: insieme di cantor, macchine ricorsive, macchine ricorsive topologiche, Mathematica, ricorsività

Articoli correlati