Eine Nummerierung einer Menge [math]M[/math], im Sinne der Berechenbarkeitstheorie, ist eine möglicherweise partielle surjektive Funktion [math]\nu :\mathbb N\to_p M[/math].
Nummerierungen und die verwandten Notationen sind z. B. Werkzeuge beim Beweis der Äquivalenz von Register- und Turingmaschinen.
Wenn die Zuordnung berechenbar ist spricht man auch von einer effektiven Nummerierung.
Bemerkungen
- Man vergibt für alle [math]m \in M[/math] eine Nummer [math]n \in \mathbb{N}[/math] mit [math]\nu(n) = m[/math].
- Es müssen nicht alle Nummern vergeben sein, z. B. [math]\nu(3) = \bot[/math]. Das bedeutet: der Wert an der Stelle 3 ist undefiniert bzw. eine Registermaschine, deren Maschinenfunktion [math]\nu[/math] ist, würde bei der Eingabe 3 in eine Endlosschleife geraten.
- Ein [math]m \in M[/math] darf auch mehrere Nummern haben.