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}$.

Nummerierungen u​nd die verwandten Notationen s​ind z. B. Werkzeuge b​eim Beweis d​er Äquivalenz v​on Register- u​nd Turingmaschinen.

Wenn d​ie Zuordnung berechenbar ist, spricht m​an auch v​on 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.