Nummerierung (Informatik)

Eine Nummerierung einer Menge , im Sinne der Berechenbarkeitstheorie, ist eine möglicherweise partielle surjektive Funktion .

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.

BemerkungenBearbeiten

  • Man vergibt für alle   eine Nummer   mit  .
  • Es müssen nicht alle Nummern vergeben sein, z. B.  . 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   darf auch mehrere Nummern haben.