Aktuální číslo:

2025/6

Téma měsíce:

Červená

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

Hvězdy, které se červenají

Hvězdy, které se červenají

Soňa Ehlerová  |  2. 6. 2025
Existují dvě skupiny lidí, kteří při slově „červenání“ pociťují výrazně nelibé pocity. Do první patří ti, kteří se hodně rdí a jimž to zároveň...
Barva krve, moci a života

Barva krve, moci a života

Jan Turek  |  2. 6. 2025
Červená barva není ani trochu neutrální. Její vnímání člověkem má velmi široké rozpětí. Je pro nás barvou lásky a života, ale také krve,...
Červená v říši zvířat

Červená v říši zvířat uzamčeno

Jaroslav Petr  |  2. 6. 2025
Jasnými barvami živočichové varují své okolí, ale také lákají partnery. Červené zbarvení získávají mnoha rozličnými způsoby.