Nummerierung (Informatik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Wenn die Zuordnung berechenbar ist spricht man auch von einer effektiven Nummerierung.

Bemerkungen[Bearbeiten]

  • 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.