Un’enumerazione di un insieme $\cal I$ è una funzione suriettiva dai numeri naturali all’insieme $\cal I$, cioè una funzione $\tau : \natnums \rarr \cal I$ che soddisfa la proprietà
$$ \forall e \in \mathcal I \ \ \exist k \in \natnums \text{ tale che } \tau(k)=e $$
In pratica, un’enumerazione indicizza gli elementi dell’insieme $\cal I$: si può dire che $e_i = \tau(i)\in \cal I$ è l’$i$-esimo elemento dell’insieme. Allora, l’insieme $\cal I$ può essere scritto come
$$ \mathcal I = \{ \underbrace{e_0}{\tau (0)}, \underbrace{e_1}{\tau (1)}, \underbrace{e_2}{\tau (2)}, \dots, \underbrace{e_i}{\tau (i)}, \dots\} $$
e l’enumerazione $\tau$ può essere indicata elencando gli elementi in ordine crescente di indice:
$$ \tau: e_0, e_1, e_2, ..., e_i, ... $$
In seguito, si considereranno enumerazioni calcolabili e invertibili, cioè che consentano di determinare effettivaente l’elemento dell’insieme a partire dal suo indice, e viceversa.
Una possibile enumerazione delle stringhe su $\{ 0, 1\}$ può essere costruita a partire dalla funzione
$$ f:\{0, 1\}^* \rarr \natnums \\ f(w) = \texttt{bin2dec}(1w) $$
dove bin2dec è l’usuale funzione di conversione da binario a decimale. Alcuni esempi di applicazione della funzione $f$ sono:
Essendo intuitivamente calcolabile, per la etsti di Church-Turing $f$ è calcolabile da una MdT.
Si definisce poi la funzione inversa sinistra di $f$, cioè una funzione $g$ tale che $g(f(w))=w$:
$$ g: \natnums \rarr \{0, 1\}^* \\ g(i)=\begin{cases} \epsilon &\text{se }i=0 \\ \texttt{tail(dec2bin(}i\texttt{))} &\text{se }i > 0 \end{cases} $$
dove dec2bin è la conversione da decimale a binario, mentre tail toglie il primo carattere della stringa (restituendo la “coda” rimanente), al fine di invertire l’aggiunta del simbolo 1 effettuata dalla funzione $f$. Alcuni esempi di applicazione di $g$ sono:
$g$ è una funzione dai numeri naturali alle stringhe su $\{0, 1\}$ ed è suriettiva (si può intuire che qualunque stringa su $\{0, 1\}$ compare nell’immagine di $g$), dunque è un’enumerazione delle stringhe su $\{0, 1\}$. Inoltre, $g$ è intuitivamente calcolabile (quindi è calcolabile da una MdT), ed è invertibile perchè $f$ è la sua funzione inversa, quindi l’enumerazione definita da $g$ è appunto calcolabile e invertibile.
Per mettere in evidenza il fatto che sia un’enumerazione, la funzione $g$ viene chiamata $e_{01}$, e l’$i$-esima stringa secondo tale enumerazione viene indicata in astratto con $w_i$: