Standardnummerierung

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 17. April 2020 um 18:39 Uhr durch imported>Xqbot(627628) (Bot: Ersetze veraltetes <source> tag und veralteten "enclose"-Parameter; kosmetische Änderungen).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Die Standardnummerierung der abzählbar-unendlichen Menge der Zeichenketten ist die unter den Voraussetzungen eines beliebigen Alphabetes mit endlicher Mächtigkeit und eindeutiger Zeichennummerierung (wo die Zahlen den Gesamtvorrat aller Zeichen produzieren) diejenige Aufzählweise (wo jede Zahl genau ein Wort produziert), welche genau diejenige bijektive Aufzählbarkeit (wo jede möglichen Zeichenkette genau eine Zahl produziert) umkehrt, die für alle Worte jedweder Länge der optimalen Konvention gehorcht, dass

Beispiel

Sei mit .

Die Elemente der Menge lassen sich systematisch auflisten:

Als i-tes Wort in der Liste erscheint stets .

entspricht .

Mithilfe eines Haskell-Zeileninterpreters lässt sich Letzteres schnell überprüfen:

strings chars = [] : [ string ++ [char] | string <- strings chars, char <- chars ]

zip [0..16] (strings "12")
[(0,""),(1,"1"),(2,"2"),(3,"11"),(4,"12"),(5,"21"),(6,"22"),(7,"111"),(8,"112"),(9,"121"),(10,"122"),(11,"211"),(12,"212"),(13,"221"),(14,"222"),(15,"1111"),(16,"1112")]

Deutlich wird dabei, dass unser herrschendes Stellenwertsystem angesichts der zu überspringenden führenden Nullen keine Standardnummerierung im Sinne obiger Definition ergibt:

zip [0..12] (strings "0123456789")
[(0,""),(1,"0"),(2,"1"),(3,"2"),(4,"3"),(5,"4"),(6,"5"),(7,"6"),(8,"7"),(9,"8"),(10,"9"),(11,"00"),(12,"01")]
zip [0..12] (strings "1234567890")
[(0,""),(1,"1"),(2,"2"),(3,"3"),(4,"4"),(5,"5"),(6,"6"),(7,"7"),(8,"8"),(9,"9"),(10,"0"),(11,"11"),(12,"12")]
drop 99 $ zip [0..121] (strings "123456789X")
[(99,"99"),(100,"9X"),(101,"X1"),(102,"X2"),(103,"X3"),(104,"X4"),(105,"X5"),(106,"X6"),(107,"X7"),(108,"X8"),(109,"X9"),(110,"XX"),(111,"111"),(112,"112"),(113,"113"),(114,"114"),(115,"115"),(116,"116"),(117,"117"),(118,"118"),(119,"119"),(120,"11X"),(121,"121")]
drop 90 $ zip [0..100] (strings "123456789")
[(90,"99"),(91,"111"),(92,"112"),(93,"113"),(94,"114"),(95,"115"),(96,"116"),(97,"117"),(98,"118"),(99,"119"),(100,"121")]