Standardnummerierung

Die Standardnummerierung der abzählbar-unendlichen Menge der Zeichenketten $\Sigma ^{*}$ ist die unter den Voraussetzungen eines beliebigen Alphabetes $\Sigma :=\{\sigma _{1}\ldots \sigma _{m}\}$ mit endlicher Mächtigkeit $m:=|\Sigma |\in \mathbb {N}$ und eindeutiger Zeichennummerierung $\sigma \in \Sigma ^{\{1\ldots m\}}$ (wo die Zahlen $1\leq i\leq m$ den Gesamtvorrat aller Zeichen $\sigma _{i}\in \Sigma$ produzieren) diejenige Aufzählweise $\nu _{\sigma }\in (\Sigma ^{*})^{\mathbb {N} }$ (wo jede Zahl $n\in \mathbb {N}$ genau ein Wort $\nu _{\sigma }^{n}\in \Sigma ^{*}$ produziert), welche genau diejenige bijektive Aufzählbarkeit $\alpha _{\sigma }\in \mathbb {N} ^{\Sigma ^{*}}$ (wo jede möglichen Zeichenkette $w\in \Sigma ^{*}$genau eine Zahl $\alpha _{\sigma }^{w}\in \mathbb {N}$ produziert) umkehrt, die für alle Worte $\sigma _{i_{1}}\ldots \sigma _{i_{L}}\in \Sigma ^{2+}$jedweder Länge $L\in \mathbb {N}$ der optimalen Konvention gehorcht, dass

$\alpha _{\sigma }^{\sigma _{i_{1}}\ldots \sigma _{i_{L}}}=\sum _{p=1}^{L}i_{p}m^{L-p}$

Beispiel

Sei $\Sigma =\{1,2\}$ mit $(1,2)=(\sigma _{1},\sigma _{2})$.

Die Elemente der Menge $\Sigma ^{*}$ lassen sich systematisch auflisten:

$\Sigma ^{*}=\{\epsilon ,1,2,11,12,21,22,111,112,121,122,211,212,221,222,\ldots \}$

Als i-tes Wort in der Liste erscheint stets $\nu _{\sigma }^{i}$.

$\nu _{\Sigma }^{8}=112$ entspricht $\alpha _{\sigma }^{112}=\alpha _{\sigma }^{\sigma _{1}\sigma _{1}\sigma _{2}}=1\cdot 2^{2}+1\cdot 2^{1}+2\cdot 2^{0}=8$.

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")]