Nummerierung (Informatik)

Eine Nummerierung einer Menge <math>M</math>, im Sinne der Berechenbarkeitstheorie, ist eine möglicherweise partielle surjektive Funktion <math>\nu :\mathbb N\to_p M</math>.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>

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

Einzelnachweise