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



© biancahoegel.de
Datum der letzten Änderung: Jena, den: 28.06. 2022