Figure e strutture ricorsive e autoreferenziali

2

Premessa

“Ma come ti è venuto in mente?” è la domanda che mi è stata posta più di frequente nei mesi in cui ho sviluppato questa tesina, la risposta non è così semplice ma cercherò brevemente di chiarirlo in questa premessa.

La scelta dell’argomento in questione risale a questa estate quando inaspettatamente mi sono reso conto che alcuni degli interessi scaturiti dai miei studi, apparentemente lontani ed eterogenei tra loro, si trovavano in realtà strettamente legati e avvicinati da una teoria, che fino ad allora avevo considerato esclusivamente informatica. Ciò che ha ispirato questa tesina sono un film, ExistenZ di Cronenberg, un libro, Sei personaggi in cerca d’autore di Pirandello, e un paio di progetti informatici sui quali stavo lavorando, un programma per il calcolo del determinante di una matrice quadrata e un programma per il disegno del frattale di Mandelbrot. A questo dovrei forse aggiungere il profondo interesse che da sempre nutro per tutto ciò che è complesso, articolato e che spesso sfugge all’immediata comprensione.

Ma come si legano tra loro questi diversi spunti? Per spiegarlo proverò a ricostruire brevemente come il nucleo della tesina si sia formato inizialmente nella mia mente. Dovrebbe essere andata all’incirca così: “Bello quel film dell’altra sera! Ma c’è qualcosa che non riesco a cogliere, nel film quei ragazzi iniziavano a giocare ad un videogioco e nel videogioco iniziavano un altro videogioco e così via…, mi sembra di aver già sentito qualcosa di simile ma non riesco a ricordarlo… Ecco, aspetta... Ma sì sicuro Pirandello! Sei personaggi in cerca d’autore! Il teatro nel teatro, ecco cos’era, il teatro che al suo interno richiama se stesso. Bello, detto così sembra quasi una funzione di informatica, ricordi?, una funzione che al suo interno richiama se stessa si definisce ricorsiva. L’avevo usata in quel programma per il calcolo del determinante e adesso di nuovo nel programma per disegnare il frattale di Mandelbrot… e se si ingrandisce il frattale si trova nuovamente una struttura simile a quella di partenza, una figura nella figura… come nel film!... Come nel libro!...

Delineato il nucleo principale ho ampliato la tesina documentandomi su internet e consultando diversi libri primo tra i quali Gödel, Escher, Bach: un’Eterna Ghirlanda Brillante, un volume di Hofstadter che mi ha guidato nello sviluppo della parte riguardante l’autoreferenza permettendo un ampliamento delle tematiche trattate.

Nel percorso da me seguito è risultato inoltre fondamentale l’interesse personale per una materia studiata nei primi quattro anni di liceo e abbandonata in quest’ultimo, disegno tecnico, che mi ha permesso di conoscere e approfondire le litografie “matematiche” di Escher e i paradossi in esse rappresentati. Essi spesso rientrano perfettamente nelle tematiche da me qui trattate e proprio per questo sono state scelte e da me unite nella copertina della tesina.

In conclusione questo lavoro rispecchia perfettamente tutti gli stimoli culturali che questo indirizzo di studi è stato in grado di offrirmi in cinque anni e che mi è piaciuto accogliere e trasformare in interessi personali.

3

Autoreferenza e ricorsività

Durante una giornata ci si trova spesso di fronte a problemi logici da risolvere o fenomeni da analizzare con attenzione e quello che si tende il più delle volte a fare è di costruire un procedimento lineare da seguire che, come una retta, partendo da un punto iniziale giunga ad una conclusione o ad un risultato finale.

Esistono però dei casi particolari in cui questo percorso lineare non può sussistere ma deve forzatamente deviare piegandosi o ramificarsi in sottoprocedure. Per quanto riguarda il primo caso può accadere che, deviando, un procedimento si ripieghi su se stesso portando inizio e fine a coincidere in uno stesso punto. Cercando così di utilizzare tale procedura nella risoluzione di un problema ci si troverebbe in un dato istante del tutto inaspettatamente di fronte al problema di partenza rendendo evidente il fatto che la procedura o il problema stesso contengano un richiamo più o meno esplicito verso il proprio inizio, essendo dunque autoreferenziali.

Anche se ci si trovasse di fronte ad un procedimento ramificato, che si suddivide cioè in sottoprocedure di ordini gerarchici via via inferiori, potrebbe verificarsi un altro fenomeno altrettanto particolare. Potrebbe infatti accadere che le sottoprocedure siano esatte copie della procedura di partenza dalla quale si ramificano generando così quel fenomeno definito come ricorsività. Utilizzando tale procedura ricorsiva nella risoluzione di un problema ci si ritrova più volte di fronte a sottoproblemi del tutto identici al problema di partenza ma in esso contenuti.

I due fenomeni appena presentati risultano a mio parere strettamente legati da una caratteristica comune: sia un procedimento autoreferenziale che uno ricorsivo presentano infatti un richiamo verso se stessi. Attraverso l’autoreferenza il richiamo si genera su uno stesso livello gerarchico mentre con la ricorsività il richiamo è effettuato su più livelli gerarchici.

Ho deciso di caratterizzare ciascuna parte con una figura che ne evidenziasse l’essenza: il nastro di Möbius per l’autoreferenza e il triangolo di Sierpinski per la ricorsività.

• Processi chimico-biologici autoreferenziali
• Processi e algoritmi ricorsivi
• Figure e strutture autoreferenziali
• Autoreferenza
• Ricorsività
• Frattali
• Autoreferenza nel pensiero
• Procedure autoreferenziali
• Figure e strutture ricorsive

4

• Calcolo fattoriale (Programma Java)
• Calcolo matriciale (Programma VB)
• Processi e algoritmi ricorsivi
• Programmazione ricorsiva
• Frattale di Mandelbrot (Programma VB)
• Triangolo di Sierpinski
• Frattali non biomorfi
• Sei personaggi in cerca d’autore
• Il fu Mattia Pascal
• Pirandello
• Ricorsività
• Frattali
• Shakespeare - Hamlet
• Beckett - Waiting for Godot
• Strutture ricorsive in letteratura
• Frattali biomorfi
• Strutture ricorsive presenti in natura
• Figure e strutture ricorsive
• Ricorsione nell’arte
• Alberi
• Montagne
• Effetto Droste
• Nuvole
• M.C. Escher
• Metabolismo DNA - proteine
• Meccanismi di autoregolazione
• Metabolismi cellulari
• Autoreferenza nell’arte
• Figure e strutture
• Processi chimico-biologici autoreferenziali
• Autoreferenziali
• Strutture autoreferenziali in letteratura
• Pavese - Feria d’agosto
• Beckett - Waiting for Godot
• Autoreferenza
• Nietzsche - Filosofia dell’eterno ritorno x
• Schopenhauer - Autoreferenza della volontà
• Derivazione e
• Procedure matematiche
• Pensiero filosofico
• Procedure autoreferenziali
• Autoreferenza nel pensiero
• Procedure logiche
• Paradosso di Epimenide

5

• Magritte - L’uso della parola I
• Wittgenstein
• Processi e algoritmi ricorsivi
• Automatizzazione procedure di calcolo matematiche con funzioni ricorsive
• Programmazione ricorsiva
• Calcolo del determinante di una matrice quadrata
• Richiamo ricorsivo alla funzione per il calcolo del determinante

Inizio

F V

Calcolo determinante della matrice

Calcolo dei complementi algebrici di una riga della matrice

Dimensione di 2° ordine

Dimensione di matrice > 2

Scomposizione in matrici di 1 ordine inferiore

Calcolo determinante delle matrici di ordine inferiore

Somma dei prodotti degli elementi della riga scelta per i rispettivi complementi algebrici

Calcolo del fattoriale di un numero n

Richiamo ricorsivo alla funzione per il calcolo del fattoriale

Inizio

F V

Il fattoriale di 0 è uguale a 1

N <> 0

Il fattoriale di N è uguale a N per il fattoriale di N-1

Disegno del frattale di Mandelbrot

Inizio

Selezione di un punto P del piano

0

Traslazione del punto P in Z

0 Richiamo ricorsivo alla funzione per la traslazione del punto (Z viene passato alla funzione come P)

N = N + 1

|OP₀| > 2

0

OR

N > 100

Selezione del colore di P in base a N

6

0

Processi e algoritmi ricorsivi

Automatizzazione di procedure matematiche ricorsive tramite funzioni ricorsive

Avendo definito brevemente nell’introduzione il concetto di ricorsività vediamo ora come esso possa essere applicato efficacemente nell’automatizzazione di procedure di calcolo nell’ambito della programmazione.

Dato un problema risulta essere abbastanza naturale cercarne una rappresentazione astratta, cioè cercare di assimilare il problema specifico ad una categoria più generale di problemi che, una volta individuata una procedura di risoluzione adeguata e funzionale, possano portare alla risoluzione, per analogia, di tutti i casi specifici. In secondo luogo nel creare un algoritmo risolutivo si tenderà il più delle volte a modularizzare il problema di partenza, si cercherà cioè di suddividere il problema in sottoproblemi via via più semplici per i quali si possono individuare o già si conoscono delle soluzioni facilmente calcolabili.

Scomponendo il problema può capitare in taluni casi che i sottoproblemi siano esatte copie del problema di partenza (come è stato spiegato nell’introduzione), ciò permette di esprimere un dato problema in funzione di se stesso rendendo possibile lo sviluppo di un algoritmo ricorsivo per la sua risoluzione.

Un esempio di un problema che può essere chiaramente espresso in funzione di se stesso è quello della valutazione della mossa migliore nel gioco degli scacchi, infatti la mossa migliore per un giocatore è quella che lascia l’avversario nella situazione più difficile. Per valutare la bontà di una mossa allora si può pensare di eseguire la mossa e poi di valutare la situazione dal punto di vista dell’avversario che cercherà di capire quale è la sua mossa migliore generando un richiamo ricorsivo alla procedura.

In matematica sono molti i problemi e le procedure che possono essere espressi in maniera ricorsiva e quelli da me presi in esame in questo percorso sono solo alcuni esempi che mi sono divertito a realizzare nel corso di questi ultimi due anni di liceo. La prima volta che mi sono imbattuto in una procedura matematica ricorsiva stavo realizzando un programma in VisualBasic che fosse in grado di calcolare il determinante di una qualsiasi matrice quadrata.

Analizziamo ora brevemente il problema:

• data una matrice di 2° ordine: A = (a_1,1 a_1,2; a_2,1 a_2,2), il suo determinante si calcola: det A = a_1,1 · a_2,2 − a_1,2 · a_2,1.

• data una matrice di ordine superiore (es. 3° ordine): A = (a_1,1 a_1,2 a_1,3; a_2,1 a_2,2 a_2,3; a_3,1 a_3,2 a_3,3). Il suo determinante si calcola: det A = a_1,1 · a_2,2 · a_3,3 − a_1,1 · a_2,3 · a_3,2 + a_1,2 · a_2,3 · a_3,1 − a_2,2 · a_3,3 · a_1,1 + a_3,2 · a_3,3 · a_1,2 − a_3,1 · a_3,2 · a_1,3.

Dall’analisi del problema si può facilmente dedurre che per risolvere il determinante di una matrice di ordine superiore a 2 sarà necessario richiamare ricorsivamente la funzione per il calcolo del determinante stesso. Infatti nello sviluppo ogni elemento della prima riga viene moltiplicato con il suo minore complementare, ovvero il determinante della matrice di un ordine inferiore ottenuta eliminando la prima riga e una delle colonne.

Nel programma da me creato in VisualBasic questa procedura è rappresenta dalla seguente funzione:

Public Function Determinante(ByVal matrixA, dimensioneA,) As Long

If (dimensioneA > 2) Then 'risoluzione di matrici di ordini superiori a 2

Dim MatrixB() As Long 'matrice temporanea di 1 ordine inferiore a quella data

Dim dimensioneB As Long 'ordine della matrice temporanea

Dim ma As Long ‘complemento algebrico

Dim pos As Long 'posizione dell'elemento di sviluppo

Dim mtot As Long ‘somma dei prodotti del complemento algebrico per il minore complementare

dimensioneB = dimensioneA - 1

ReDim MatrixB(1 To dimensioneB, 1 To dimensioneB) As Long

Dim rB As Long 'contatore righe della matrice temporanea

Dim cB As Long 'contatore colonne della matrice temporanea

For i = 1 To dimensioneA 'per ogni elemento della 1a riga della matrice data

cB = 1

rB = 1

For ra = 1 To dimensioneA 'per ogni elemento riga della matrice data

For cA = 1 To dimensioneA 'per ogni colonna della matrice data

If (ra <> 1 And cA <> i) Then 'se la posizione NON equivale a una posizione nulla

MatrixB(rB, cB) = matrixA(ra, cA) 'composizione della matrice di 1 ordine inferiore

If (cB < dimensioneB) Then

cB = cB + 1 'contatore delle colonne della matrice temporanea

ElseIf (cB = dimensioneB) Then

cB = 1

rB = rB + 1 'contatore delle righe della matrice temporanea

End If

End If

Next cA

Next ra

pos = 1 + i 'posizione dell'elemento lungo il quale si sta sviluppando

ma = Determinante(MatrixB, dimensioneB) ‘richiamo ricorsivo alla funzione

If (pos Mod 2 = 0) Then '

ma = ma '

Else 'composizione del minimo algebrico

ma = -ma '

End If '

mtot = mtot + (ma * matrixA(1, i)) 'determinante della matrice data

Determinante = mtot

Next i

End If

If (dimensioneA = 2) Then 'risoluzione di matrici di ordine pari a 2

Determinante = (matrixA(1, 1) * matrixA(2, 2)) - (matrixA(1, 2) * matrixA(2, 1))

End If

If (dimensioneA = 1) Then 'risoluzione di matrici di ordine 1

Determinante = matrixA(1, 1)

End If

End Function

8

Un’altra procedura matematica che può essere semplicemente ridotta ad una funzione ricorsiva è quella per il calcolo del fattoriale di un numero (n!). Il fattoriale di un numero n si calcola infatti nel seguente modo:

• n! = n · (n − 1) · (n − 2) · … · (n − (n − 1))

che ricorsivamente può essere scritto:

• n! = n · (n − 1)!

Che nel programma da me scritto in Java si traduce nella seguente funzione:

public long fatt (int n)

{ if(n > 0)

{ return n * fatt(n-1); //Richiamo ricorsivo alla funzione

}

else if(n == 0)

{ return 1; //Il fattoriale di 0 è per definizione uguale a 1

}

return 0;

}

L’ultimo programma da me realizzato e qui preso in esame permette di disegnare e zoomare un numero indefinito di volte l’insieme di Mandelbrot. Tale frattale è descritto da una funzione ricorsiva che, preso un punto P sul piano dei numeri complessi, lo eleva al quadrato un numero n di volte sommandolo ogni volta allo stesso punto P di partenza e verificando per ogni iterazione se esso si allontani dall’origine o se esso tenda a rimanere confinato in quello che viene detto cerchio critico (circonferenza con centro nell’origine degli assi e di raggio pari a 2).

In questo caso il programma da me realizzato non fa uso di un vero e proprio richiamo ricorsivo a una funzione, sfrutta invece un ciclo che ad ogni iterazione eleva al quadrato il numero complesso ottenuto dall’iterazione precedente (ciò che si ottiene è in ogni caso una funzione ricorsiva del tipo f[f[f[…f[P]]]]).

Public Sub calcola(a, b)

n = 0

az = 0 ‘parte reale del numero complesso P = a + bi

bz = 0 ‘parte immaginaria del numero complesso P = a + bi

tz = 0 ‘variabile temporanea utile a fini di calcolo

Do

tz = (az ^ 2) - (bz ^ 2) ‘

bz = 2 * az * bz ‘elevamento al quadrato

az = tz ‘

az = az + a ‘

bz = bz + b ‘Il nuovo punto è sommato a quello di partenza

n = n + 1 ‘numero di iterazioni

Loop Until (Sqr(az ^ 2 + bz ^ 2) > 2) Or (n > 100) ‘il ciclo ha termine quando il punto esce dal cerchio critico o quando esso vi rimane

‘perennemente confinato (vengono superate le 100 iterazioni)

If n < 100 Then

n = n Mod 50

Picture1.PSet (a - trasX, b - trasY), RGB(255 - 5 * n, 255 - 5 * n, 220)

Picture2.PSet (a - trasX, b - trasY), RGB(255 - 5 * n, 255 - 5 * n, 220)

Else

n = 100

Picture1.PSet (a - trasX, b - trasY), RGB(0, 0, 0)

Picture2.PSet (a - trasX, b - trasY), RGB(0, 0, 0)

9

End If

End Sub

Frattali

Caratteristiche

• Autosimilarità strutturale su diversi livelli
• Triangolo di Sierpinski
• Frattali non biomorfi
• Costruzione per sostituzione
• Triangolo lato l
• Triangolo lato l/2
• Triangolo lato l/2
• Triangolo lato l/2
• Definizione attraverso una funzione ricorsiva
• Triangolo di Sierpinski
• Costruzione con metodo IFS
• Punto P del piano

X = 1/2x

T1

Y = 1/2y

Punto P’’

X = 1/2x

T2

Applicazione di una T casuale

Applicazione di una T casuale

Applicazione di una T casuale

Y = 1/2y + 1/2

X = 1/2x + 1/2

T3

Y = 1/2y + 1/2

Punto P’

Insieme di Mandelbrot

Costruzione con funzione ricorsiva

Z_n2 = Z_n² + P (applicata n volte su ogni punto P del piano dei numeri complessi)

F(z) = z² + c (0, F(0), F(F(0)), F(F(F(0))), F(F(F(F(0)))), ………)

Per ogni C del piano dei numeri complessi

Se |Z| > 2 la serie divergerà all’infinito

C non sarà parte dell’insieme