Wie viele Markierungen mit einer 1 kann eine TuringKara-Maschine mit drei Zuständen maximal produzieren, bevor sie terminiert? Wir machen die folgenden Einschränkungen: nur die Symbole 1 und leeres Feld dürfen verwendet werden, und die Übergänge müssen der Definition von Standard-Turing-Maschinen entsprechen. Jeder Übergang besteht also aus genau einem Schreibbefehl gefolgt von einem Bewegungsbefehl. Wie die 1en angeordnet sind, spielt keine Rolle. Untenstehende Abbildung zeigt die Markierungen, wie sie vom Programm der Lösung dieser Aufgabe produziert werden.

Hinweis: Die Aufgabe ist etwas hinterhältig, ihre Lösung nicht ganz einfach!