Informatik zum Jahresanfang – Auflösung für n

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Nachtrag: Der Automat ist nicht notwendigerweise minimal, d.h. es können evtl. Zustände zusammengefasst werden. Es steht die Vermutung im Raum, dass der Automat für n prim minimal ist und für n zusammengesetzt nicht.

Ich hätte nicht so vorschnell einen Nachtrag schreiben sollen. Das ist natürlich Unsinn, wie wir am Beispiel mit der 9 (nicht 😉) gesehen haben. Obwohl 9 nicht prim ist, lässt sich der Automat nicht auf weniger als 9 + 1 Zustände reduzieren.

Ich werfe mal eine andere Vermutung in den Raum: Der Automat lässt sich genau dann auf weniger als n + 1 Zustände reduzieren, wenn n durch 2 oder 5 teilbar ist. (Was die Teiler der 10, der Basis unseres Zahlensystems, sind.)

LLAP 🖖