Vom Klassifikationsstandpunkt aus gesehen ist interesssanterweise festzustellen, daß die Ordnung nach Periodenlänge nicht die natürliche Komplexität wieder gibt, sondern entscheidend ist die Darstellbarkeit mittels
eines Automaten mit möglichst kurzem Regelsatz und kleinem Gedächtnis.
Tiefe Regeln Folgenzahl Folge Regelumfang
1 - 0 (random) 0
2 2 +2 AB ABC 1
3 4 +1 ABAC 2
4 16 +3 ABACBC ABABCBCAC 3
ABABCACABCBC 4
5 256 +13 ABACBABC ABABACAC 4
ABABC ABABACBCBC 5
ABABCBACACBC ABABCACBCBAC ABABACBABABC 6
ABABCBACBCBABC ABABCABACACBAC 7
ABABACABCBCBABCACACBC ABABACBCACACBABCBCBAC 7
ABABACABCACACBCABCBCBABC ABABACBABCBCBACBCACACBAC 8
6 65536 +160 6,2*7,8,4*9,3*10,2*11,2*12,2*13,2*14,8*15,14*16,10*18,7*20,
7*22,5*24,6*26,3*27,20*28,25*30,5*33,7*36,4*39,10*45,10*48
ABABCBABAC ABACBACABC 5
ABABABCBCBCACAC ABACABCBABCACBC 5
ABABAC ABABABCACACABCBCBC ABABCABCBCABCACABC ABACABCACBCABCBABC 6
ABABABC ABACABC ABABACBACACABC ABABABCBABABAC 7
ABABCBAC ABABABCACBCBCBAC ABABABCBACACACBC 8
ABABACACBABABCBC ABABACBCBABABCAC ABABCABACBCBACBC 8
ABABCABCBABACBAC ABABCACBACACBABC ABABCBACBABACABC 8
ABABABCAC ABABABCBC ABABACABC ABABACBAC 9
ABABABCBAC 10
ABABACABABC ABABACBABAC 11
ABABACACBABC ABABACBABCAC 12
ABABACBCABCAC ABABACACBACBC 13
Somit ist die exakte Bestimmung dieser Anzahlen und Gitter alles andere als trivial, nämlich NP-schwer.
Physik + Mathematik -> Informatik
Sie sind der . Neugierige seit Semesterbegin