Aktuální číslo:

2025/7

Téma měsíce:

Umění

Obálka čísla

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

 |  31. 3. 2025
 |  Vesmír 104, 202, 2025/4

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.

Nyní vidíte 48 % článku. Co dál:

Jsem předplatitel, mám plný přístup
Jsem návštěvník
Chci si přečíst celé číslo
Předplatným pomůžete zajistit budoucnost Vesmíru. Více o předplatném
OBORY A KLÍČOVÁ SLOVA: Počítače, internet, Matematika
RUBRIKA: Mozaika

O autorovi

Lukáš Tabery

 

Doporučujeme

Najít své těžiště kontroly

Najít své těžiště kontroly uzamčeno

„Svobodu, nebo smrt je návod, jak vyhrát bitvu, ale zároveň recept na rozchod,“ říká bývalý hlavní armádní psychiatr Jan Vevera. Faktory, které...
Věstonická superstar

Věstonická superstar video

Soška tělnaté ženy z ústředního tábořiště lovců mamutů u dnešních Dolních Věstonic pod Pálavou je jistě nejznámějším archeologickým nálezem...
K čemu je umění?

K čemu je umění? uzamčeno

Petr Tureček  |  7. 7. 2025
Výstižná teorie lidské evoluce by měla nabídnout vysvětlení, proč trávíme tolik času zdánlivě zbytečnými činnostmi. Proč, jako například lvi,...