Nummerierung (Informatik)

Nummerierung (Informatik)

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.

Bemerkungen

  • Man vergibt für alle m \in M eine Nummer n \in \mathbb{N} mit ν(n) = m.
  • Es müssen nicht alle Nummern vergeben sein, z. B. ν(3) = div. 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 m \in M darf auch mehrere Nummern haben.

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Nummerierung — (traditionelle Schreibweise: Numerierung; rsp. Benummerung) bezeichnet: allgemein die Zuweisung einer Nummer, siehe auch Aufzählungszeichen eine Funktion in der theoretischen Informatik, siehe Nummerierung (Informatik) eine Kennzeichnungsart in… …   Deutsch Wikipedia

  • Gödel-Nummerierung — Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nach einem gewissermaßen „durchschaubaren“ Verfahren – Gödelisierung – zugeordnet wird und dieses Wort eindeutig kennzeichnet. Alle über die Kodierung von Programmen …   Deutsch Wikipedia

  • Rang (Informatik) — Der Rang bezeichnet in der Informatik eine aufsteigende Reihenfolge von Objekten. Verwendung Bei der Datenaggregation für Data Warehouse Anwendungen kommt die Rang Funktion oft zum Einsatz. Durch diese Funktion werden Sätze aus einer Selektion… …   Deutsch Wikipedia

  • Schlüssel (Informatik) — Als Schlüssel bezeichnet man in der Informatik eine Entität aus einer geordneten Menge, die man einem Objekt oder Element zuweisen kann. Der Schlüssel erlaubt es, Elemente der Relation zu identifizieren. Über die zugeordneten Schlüssel erhalten… …   Deutsch Wikipedia

  • Partition (Informatik) — Unter einer Partition (lat. Partitio = „(Ein)teilung“) versteht man einen zusammenhängenden Teil des Speicherplatzes eines geeigneten physischen oder logischen Datenträgers. Partitionen sind voneinander unabhängig und können von Betriebssystemen… …   Deutsch Wikipedia

  • Numerierung — Nummerierung (traditionelle Schreibweise Numerierung) bezeichnet: allgemein die Zuweisung einer Nummer eine Funktion in der theoretischen Informatik, siehe Nummerierung (Informatik) eine Kennzeichnungsart in der Vermittlungstechnik, siehe… …   Deutsch Wikipedia

  • Cantor'sche Paarungsfunktion — Die Cantorsche Paarungsfunktion (manchmal auch Nummerierungsfunktion) ist eine in der theoretischen Informatik verwendete Abbildung, die auf dem Diagonalargument von Cantor basiert. Ihre Verallgemeinerung von Paaren auf Tupel wird als Cantorsche… …   Deutsch Wikipedia

  • Cantorsche Tupelfunktion — Die Cantorsche Paarungsfunktion (manchmal auch Nummerierungsfunktion) ist eine in der theoretischen Informatik verwendete Abbildung, die auf dem Diagonalargument von Cantor basiert. Ihre Verallgemeinerung von Paaren auf Tupel wird als Cantorsche… …   Deutsch Wikipedia

  • Die cantorsche Paarungsfunktion — (manchmal auch Nummerierungsfunktion) ist eine in der theoretischen Informatik verwendete Abbildung, die auf dem Diagonalargument von Cantor basiert. Ihre Verallgemeinerung von Paaren auf Tupel wird als Cantorsche Tupelfunktion bezeichnet. Mit… …   Deutsch Wikipedia

  • Nummerierungsfunktion — Die Cantorsche Paarungsfunktion (manchmal auch Nummerierungsfunktion) ist eine in der theoretischen Informatik verwendete Abbildung, die auf dem Diagonalargument von Cantor basiert. Ihre Verallgemeinerung von Paaren auf Tupel wird als Cantorsche… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”