Standardnummerierung
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
[Bearbeiten | Quelltext bearbeiten]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")]