Nummerierung (Informatik)

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

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