Niezrażeni, po trzech dekadach poszukiwań i przy pewnej pomocy superkomputera, matematycy w końcu odkryli nowy przykład specjalnej liczby całkowitej zwanej liczbą Dedekinda.
Tylko dziewiąta część tego rodzaju, czyli D(9), została obliczona jako 286 386 577 668 298 411 128 469 151 667 598 498 812 366, to tak na wszelki wypadek jeśli aktualizujesz gdzieś własne dane. Ten 42-cyfrowy potwór jest następcą 23-cyfrowego D(8) odkrytego w 1991 roku. Zrozumienie pojęcia liczby Dedekinda jest trudne dla nie-matematyków, nie mówiąc już o jej wyliczeniu. W rzeczywistości obliczenia są tak złożone i obejmują tak ogromne liczby, że nie było pewne, czy D(9) kiedykolwiek zostanie odkryte.
„Przez 32 lata obliczenie D(9) było otwartym wyzwaniem i wątpliwe było, czy w ogóle będzie możliwe obliczenie tej liczby” – powiedział informatyk Lennart Van Hirtum z Uniwersytetu w Paderborn w Niemczech, w czerwcu, kiedy ogłoszono jego wynik.
W centrum liczby Dedekinda znajdują się funkcje logiczne (Boolean function), czyli rodzaj logiki, która wybiera wyjście z wejść składających się tylko z dwóch stanów, takich jak prawda i fałsz lub 0 i 1. Monotoniczne funkcje logiczne to te, które ograniczają logikę w taki sposób, że zamiana 0 na 1 na wejściu powoduje jedynie zmianę wartości wyjściowej z 0 na 1, a nie z 1 na 0.
Naukowcy opisują to za pomocą kolorów czerwonego i białego, a nie jedynek i zer, ale idea jest taka sama.
„Zasadniczo można myśleć o monotonicznej funkcji logicznej w dwóch, trzech i nieskończonych wymiarach jak o grze z n-wymiarową kostką” – powiedział Van Hirtum. „Równujesz sześcianem w jednym rogu, a następnie kolorujesz każdy z pozostałych rogów na biało lub czerwono. Istnieje tylko jedna zasada: nigdy nie wolno umieszczać białego rogu nad czerwonym. Tworzy to rodzaj pionowego skrzyżowania czerwono-białego. Celem gry jest policzenie, ile jest różnych cięć”.
Kilka pierwszych liczb jest całkiem prostych do wyliczenia. Matematycy liczą D(1) jako po prostu 2, potem 3, 6, 20, 168…
W 1991 roku superkomputer Cray-2 (jeden z najpotężniejszych wówczas superkomputerów) i matematyk Doug Wiedemann potrzebowali 200 godzin, aby obliczyć D(8).
D(9) okazała się prawie dwukrotnie dłuższa od D(8) i wymagała specjalnego rodzaju superkomputera: takiego, który wykorzystuje wyspecjalizowane jednostki zwane układami bramek programowalnych przez pole (FPGA), które mogą równolegle wykonywać wiele obliczeń. To doprowadziło zespół do superkomputera Noctua 2 na Uniwersytecie w Paderborn.
„Rozwiązywanie trudnych problemów kombinatorycznych za pomocą układów FPGA to obiecująca dziedzina zastosowań, a Noctua 2 to jeden z niewielu superkomputerów na świecie, z którymi eksperyment jest w ogóle wykonalny” – powiedział informatyk Christian Plessl, szef Paderborn Center for Parallel Computing (PC2 ), gdzie przechowywana jest Noctua 2.
Aby wykorzystać Noctua 2 do pracy, konieczne były dalsze optymalizacje. Wykorzystując symetrie we wzorze, aby zwiększyć wydajność procesu, badacze dali superkomputerowi do obliczenia jedną ogromną sumę, która obejmowała 5,5 ✕1018 składowych (liczbę ziaren piasku na Ziemi szacuje się na 7,5 ✕1018, dla porównania).
Po pięciu miesiącach Noctua 2 znalazła odpowiedź i znamy teraz D(9). Naukowcy nie wspomnieli na razie o D(10), ale możemy sobie wyobrazić, że znalezienie go może zająć kolejne 32 lata.
Artykuł został zaprezentowany we wrześniu podczas Międzynarodowych Warsztatów na temat funkcji boolowskich i ich zastosowań (BFA) International Workshop on Boolean Functions and their Applications w Norwegii.
➔ Obserwuj nas w Google News, aby być na bieżąco!
źródło: Uniwersytet w Paderborn | Science Alert
zdjęcie wykorzystane we wpisie z Depositphotos
Od 2005 roku zajmuję się komunikacją internetową i e-marketingiem, jestem pasjonatem urządzeń mobilnych oraz nowych technologii – i nie waham się ich używać.