Um diese Aufgabe zu verstehen, braucht ein wenig Hintergrundswissen. Universelle Berechnungsmodelle spielen in der Theoretischen Informatik eine wichtige Rolle. Die Church-Turing-These besagt, dass jede Funktion, die intuitiv "berechenbar" ist, auch mit einer Turing-Maschine berechnet werden kann. Das Standard-Beispiel eines unentscheidbaren Problems ist das Halteproblem. Es gibt keine Turing-Maschine, die entscheiden kann, ob eine beliebige andere Turing-Maschine je anhält oder nicht.

Von Tibor Rado stammt 1962 ein Beispiel einer nicht berechenbaren Funktion, deren Output sich gut visualisieren lässt. Man betrachtet alle Turing-Maschinen mit Alphabet {1, leeres Feld} mit n Zuständen, die beginnend auf einem leeren Band irgendwann anhalten. Der Stop-Zustand wird dabei nicht gezählt. Die Funktion S(n) bezeichnet die maximale Anzahl Markierungen (nicht notwendigerweise zusammenhängend), die eine Turing-Maschine mit n Zuständen auf dem Band hinterlassen kann, bevor sie anhält. Eine Turing-Maschine, welche S(n) Markierungen (Einsen) liefert, wird ein "fleissiger Biber" genannt.

Schon Turing-Maschinen mit einer kleinen Anzahl Zustände sind in der Lage, eine sehr grosse Anzahl Markierungen auf dem Band zu hinterlegen. Die fleissigen Biber beginnen klein: S(1) = 1, S(2) = 4, S(3) = 6, S(4) = 13. H. Marxen und J. Buntrock haben gezeigt, dass der fleissige Biber mit 5 Zuständen mindestens S(5) >= 4098 Markierungen und der fleissige Biber mit 6 Zuständen mindestens S(6) >= 1.29*10865 Markierungen auf dem Band hinterlassen!

Die untenstehende Abbildung zeigt eine TuringKara-Maschine, von der wir vermuten, dass es sich um einen fleissigen TuringKara-Biber-Kandidaten mit drei Zuständen handelt. Die Maschine wurde ermittelt durch eine Brute-Force-Suche über alle TuringKara-Maschinen, die obigen Einschränkungen genügen und innerhalb von 100 Übergängen terminieren.