Standardnummerierung

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

α σ σ i 1 … σ i L = ∑ p = 1 L i p m L − p {\displaystyle \alpha _{\sigma }^{\sigma _{i_{1}}\ldots \sigma _{i_{L}}}=\sum _{p=1}^{L}i_{p}m^{L-p}}

Beispiel

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

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

Σ ∗ = { ϵ , 1 , 2 , 11 , 12 , 21 , 22 , 111 , 112 , 121 , 122 , 211 , 212 , 221 , 222 , … } {\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 ν σ i {\displaystyle \nu _{\sigma }^{i}} .

ν Σ 8 = 112 {\displaystyle \nu _{\Sigma }^{8}=112} entspricht α σ 112 = α σ σ 1 σ 1 σ 2 = 1 ⋅ 2 2 + 1 ⋅ 2 1 + 2 ⋅ 2 0 = 8 {\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 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")]