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.

Bemerkungen

• Man vergibt für alle $m \in M$ eine Nummer $n \in \mathbb{N}$ mit ν(n) = m.
• Es müssen nicht alle Nummern vergeben sein, z. B. ν(3) = div. Das bedeutet: der Wert an der Stelle 3 ist undefiniert bzw. eine Registermaschine, deren Maschinenfunktion ν ist, würde bei der Eingabe 3 in eine Endlosschleife geraten.
• Ein $m \in M$ darf auch mehrere Nummern haben.