La scorsa lezione si è interrotta sul problema che nasce dal limitare dominio e codominio dei programmi WHILE ai soli numeri naturali. Per risolvere questo problema abbiamo introdotto il concetto di codifica, realizzato da una funzione invertibile che mette in relazione un dominio qualsiasi con i numeri naturali.

Un esempio di codifica è la codifica a “coda di colomba” o funzione coppia di Cantor, che codifica coppie di numeri naturali come un singolo naturale.

Esempio di codifica a “coda di colomba” o funzione coppia di Cantor:

Questa funzione è biunivoca e quindi invertibile. La sua inversa è

Il nome di questa codifica “a coda di colomba”, si riferisce alla sua rappresentazione grafica: una tabella a due entrate per x e y dove ogni cella cresce monotonicamente in diagonale da sinistra verso destra, dal basso verso l’alto.

Le codifiche devono rispettare alcune proprietà: devono essere biunivoche, effettive e facili. Questi termini non vengono definiti rigorosamente per il momento.

Se ci inventiamo un nuovo formalismo che ha dominio e codominio più esteso rispetto ai numeri naturali, questo formalismo non è più potente del linguaggio WHILE (o della MdT), nel senso che entrambi possono calcolare la stessa classe di funzioni. Le codifiche, che sono “facili” da calcolare, non allargano e non restringono la classe di funzioni calcolabili.

Per dimostrare questi asserzioni dobbiamo passare a definire il termine funzione in termini di insiemi.

Funzioni

Definizione di funzione totale: \(f:A \mapsto B \subset A \times B\) è una funzione totale se e soltanto se:

1. \(\forall a \in A \exists b \in B : (a,b) \in f\) (funzione definita ovunque)
2. \((a,b), (a,c) \in f \implies b = c\) (unicità)

Definizione di funzione parziale: \(f:A \mapsto B \subset A \times B\) è una funzione parziale se e soltanto se:

1. \((a,b),(a,c) \in f \implies b = c\) (unicità)
2. esiste al più un \(b \in B \text{ tale che } f(a) = b\) (non è richiesto che f sia definita sempre)

Definizione di convergenza di una funzione: f è definita o converge su a se e solo se:

$$\exists b : (a,b) \in f \text{ cioè } f(a) = b$$

Definizione di divergenza di una funzione: f non è definita o diverge su a se e solo se:

$$\nexists b : (a,b) \in f$$

Notazione

Data una funzione \(f:A \mapsto B\) :

• scriviamo \(f(a)\downarrow\) se f è definita o converge su a.
• scriviamo \(f(a)\uparrow\) se f non è definita o diverge su a.
• dominio di f è l’insieme \(\{a \in A | f(a) \downarrow\}\)
• codominio di f è l’insieme B.
• immagine di f è l’insieme \(\{b \in B | \exists a \in A : f(a) = b\}\)
• f è iniettiva se e soltanto se \(\forall a,b \in A. a \ne b \implies f(a) \ne f(b)\)
• f è surgettiva se e soltanto se \(\forall b \in B. \exists a \in A : f(a) = b\)
• f è biunivoca se e soltanto se è iniettiva e surgettiva

Rapporto tra algoritmi e funzioni

Una funzione f è un insieme di coppie, cioè f associa l’argomento con il risultato, senza dire come fare a calcolarlo. Non ci sono due funzioni diverse che per ogni argomento restituiscono lo stesso risultato. In termini insiemistici non esistono due insiemi diversi che hanno gli stessi elementi.

Un algoritmo specifica, invece, come si calcola il risultato a partire dall’argomento. Un algoritmo calcola o rappresenta in modo finito una funzione. Esistono più algoritmi che calcolano la stessa funzione.

Prendiamo la congettura di Goldbach come esempio di funzione:

\(gb : \mathbb{N} \mapsto \mathbb{N}\) per cui \( gb(n) = \begin{cases} 0 & \text{se la congettura di Goldbach è vera per n}\\ 1 & \text{altrimenti} \end{cases}\)

Definizione di congettura di Goldbach:

Non sappiamo tutt’oggi se la congettura di Goldbach vale. Nonostante ciò abbiamo un algoritmo che ci dice se un numero m rispetta la congettura: basta prendere m e provare in modo esaustivo tutti i numeri primi a coppie finché non se ne trovano 2 che sommati danno 2m.

Senza una dimostrazione della congettura di Goldbach, non sappiamo se l’algoritmo giusto che calcola gn(n) sia quello che restituisce 0 o quello che restituisce 1.

Non mi è molto chiaro questo discorso dei due algoritmi che restituisco 0 o 1. Forse intende dire che per dimostrare la congettura, l’algoritmo dovrebbe calcolare all’infinito per controllare tutti i numeri naturali e rispondere 0. Quindi conosciamo l’algoritmo per verificare se un numero rispetta la congettura, ma non sappiamo la funzione che stiamo calcolando?