Nummerierung (Informatik)

Eine Nummerierung einer Menge $M$, im Sinne der Berechenbarkeitstheorie, ist eine möglicherweise partielle surjektive Funktion $\nu :\mathbb {N} \to _{p}M$.

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 $m\in M$ eine Nummer $n\in \mathbb {N}$ mit $\nu (n)=m$.
• Es müssen nicht alle Nummern vergeben sein, z. B. $\nu (3)=\bot$. Das bedeutet: der Wert an der Stelle 3 ist undefiniert bzw. eine Registermaschine, deren Maschinenfunktion $\nu$ ist, würde bei der Eingabe 3 in eine Endlosschleife geraten.
• Ein $m\in M$ darf auch mehrere Nummern haben.