La ricorsività secondo Hofstadter

Maggio 28th, 2021 | by Marcello Colozzo |

Nel best seller Goedel, Escher, Bach, un'eterna ghirlanda brillante l'autore (Douglas Hofstadter) espone in maniera originale l'importante nozione di ricorsività. Per essere più specifici, a pag. 144 (ed. Adelphi) si parla di "toccare il fondo". Ciò significa assegnare il valore iniziale di una successione ricorsivamente definita. Per fissare le idee sia data la successione:

La definizione ricorsiva consiste nell'assegnare una funzione reale f(x) tale che

ed è chiaro che la successione è univocamente determinata dal valore iniziale x0. È facile persuadersi che ciò equivale nel continuo ad assegnare un problema di Cauchy relativo a un'equazione differenziale ordinaria del primo ordine autonoma. Più precisamente, definiamo la funzione reale:

Segue

avendo introdotto la variabile "tempo" opportunatamente campionata (Δt=1). Passando al continuo:

ovvero un'equazione differenziale del primo ordine autonoma. Per una qualuque f(x) lipchitziana, esiste ed è unica la soluzione del problema di Cauchy:

er quanto visto, le successioni ricorsivamente definite sono particolari funzioni da N a R, e rappresentano la controparte discreta di processi fisici governati da equazioni differenziali autonome. Di contro, Hofstadter si riferisce a successioni da N a N, come ad esempio quella che denota con G(n). Noi preferiamo utilizzare una notazione differente. Precisamente: