Aktuální číslo:

2025/4

Téma měsíce:

Prázdno

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

Rostliny vyprávějí o lidech

Rostliny vyprávějí o lidech

Ondřej Vrtiška  |  31. 3. 2025
V Súdánu už dva roky zuří krvavá občanská válka. Statisíce lidí zahynuly, miliony jich musely opustit domov. Etnobotanička a archeobotanička Ikram...
O prázdnech v nás

O prázdnech v nás uzamčenovideo

Jan Černý  |  31. 3. 2025
Naše tělo je plné dutin, trubic a kanálků. Malých i velkých. Některé jsou zaplněné, jiné prázdné, další jak kdy. V některých proudí tekutina, v...
Nejúspěšnější gen v evoluci

Nejúspěšnější gen v evoluci

Eduard Kejnovský  |  31. 3. 2025
Dávno před vznikem moderních forem života sváděly boj o přežití jednodušší protoorganismy, z počátku nejspíše „nahé“ replikující se molekuly...