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

giovedì, Aprile 13th, 2017

macchine ricorsive,insieme di cantor,ricorsività,macchine ricorsive topologiche,mathematica — **Fig. 3**

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

macchine ricorsive,insieme di cantor,ricorsività

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.

macchine ricorsive,insieme di cantor,ricorsività,macchine ricorsive topologiche — **Fig.1.**

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:
macchine ricorsive,insieme di cantor,ricorsività

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:
macchine ricorsive,insieme di cantor,ricorsività