Standardnummerierung

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

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

Beispiel

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

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

${\displaystyle \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 ${\displaystyle \nu _{\sigma }^{i}}$.

${\displaystyle \nu _{\Sigma }^{8}=112}$ entspricht ${\displaystyle \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 e​ines Haskell-Zeileninterpreters lässt s​ich Letzteres schnell überprüfen:

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

zip [0..16] (strings "12")

[(0,"" target="_blank" rel="nofollow"),(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 w​ird dabei, d​ass unser herrschendes Stellenwertsystem angesichts d​er zu überspringenden führenden Nullen keine Standardnummerierung i​m Sinne obiger Definition ergibt:

zip [0..12] (strings "0123456789")

[(0,"" target="_blank" rel="nofollow"),(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,"" target="_blank" rel="nofollow"),(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")]