Nummerierung (Informatik)

Eine Nummerierung einer Menge , 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.

Basierend auf einem Artikel in: