Corrispondenza tra Induzione e Ricorsione: un breve cenno

 

Abbiamo in precedenza accennato [FBg] al fatto che dimostrare e programmare (descrivere computazioni) siano essenzialmente ed intrinsecamente la stessa cosa.

Qual e' allora il processo computazionale corrispondente alle dimostrazioni per induzione? [VS]

Il procedimento dimostrativo di una formula ∀n.φ(n) per induzione matematica consiste nel dimostrare φ(0) e nel dimostrare, preso un m generico, che vale φ(m) utilizzando l'ipotesi che valga φ(m-1).
Il suo corrispettivo computazionale e' la programmazione di funzioni su numeri naturali utilizzando una particolare forma di ricorsione: si descrive l'algoritmo per il calcolo della funzione specificando quanto vale la funzione per 0 e specificando quanto vale la funzione per un generico m supponendo di conoscere il risultato del calcolo della funzione su m-1.
Utilizziamo, per fare degli esempi, il semplice linguaggio di programmazione funzionale descritto nella Sezione 2 di [VS] (in pratica e' un piccolo sottoinsieme del linguaggio Haskell).
Il seguente programma sommadazeroa calcola la somma dei numeri da 0 al numero dato in input:

sommadazeroa 0 = 0             
                
          // specifichiamo il valore dell'output per l'input 0

sommadazeroa n = (sommadazeroa (n-1)) + n             

          // specifichiamo il valore dell'output per un input generico n
          // (diverso da 0) supponendo di conoscere il risultato 
          // del calcolo per l'input (n-1)

Il procedimento dimostrativo di una formula ∀n.φ(n) per induzione completa consiste invece nel dimostrare φ(0) e nel dimostrare, preso un m generico, che vale φ(m) utilizzando (non necessariamente tutte) le ipotesi φ(m-1), φ(m-2),... e φ(1), (che quindi corrisponde a dimostrare (∀1≤q≤m.φ(q)) → φ(m) ).

Il suo corrispettivo computazionale e' la programmazione di funzioni attraverso una particolare laseguente forma di ricorsione: si descrive l'algoritmo per il calcolo della funzione specificando quanto vale la funzione per 0 e specificando quanto vale la funzione per un generico m supponendo di sapere il conoscere il risultato del calcolo della funzione per i numeri da 1 ad m-1.

Vediamo un esempio di programma ricorsivo che utilizza tale forma di ricorsione per restituire, dato in input n, l'n-esimo numero di Fibonacci:

fib 0 = 1                                       
         // specifichiamo il valore dell'output per l'input 0

fib n = if (n==1) then 1 else (fib (n-1) + fib (n-2)) 
 
         // specifichiamo il valore dell'output per un input generico n
         // (diverso da 0) supponendo di conoscere il risultato 
         // del calcolo per tutti gli input da 1 ad (n-1) (anche se
         // ci serve poi solo il valore per n-1 ed n-2)

L'induzione e la ricorsione appena viste considerano solo il dominio dei numeri naturali. Esiste una generalizzazione dei principi di induzione matematica e completa che permette di dimostrare proprieta' quantificate universalmente su insiemi ben fondati: l'induzione ben fondata, che noi non studiamo per limiti di tempo (se interessati, vedere [VS]).