Po čtyřiceti letech nalezen další „pilný bobr“

Skupině nadšenců do matematiky a počítačové vědy, z nichž mnozí nemají formální vzdělání, se povedlo něco dříve nemyslitelného. Podařilo se jim dokázat, že záludná funkce BB (z anglickéhu busy beaver) nabývá v bodě 5 hodnotu 47 176 870.

Tato funkce se vztahuje k Turingovu stroji, což je matematická abstrakce počítače. Klasický Turingův stroj obsahuje pásku s poli, do nichž zapisuje hodnoty 0 nebo 1, a soubor pravidel říkajících, jak se má chovat. Příklad části pravidla A pak může být: pokud je na daném poli hodnota 1, přepiš ji na 0, pokračuj doleva a řiď se pravidlem C. Stroj pokračuje v provádění pravidel, dokud nenarazí na speciální pravidlo, které program ukončí.

Je známo, že neexistuje žádný obecný algoritmus, který by dokázal s jistotou určit, zda se daný Turingův stroj nakonec zastaví, nebo poběží donekonečna. I když stroj budete simulovat úspěšně pro milion kroků, stále může zastavit až v miliontém prvním. Na tomto principu je postavena celá složitost funkce BB. BB(n) označuje největší možný počet kroků, za který zastaví n-pravidlový Turingův stroj, pokud zastaví vůbec. K tomu, abyste dokázali, že je nalezená hodnota skutečně busy beaver, potřebujete dokázat, že všechny ostatní Turingovy stroje buď zastaví dříve, nebo poběží donekonečna.