Pracowity bóbr

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Pracowity bóbr (ang. busy beaver) to maszyna Turinga o z góry zadanej liczbie stanów N, która zaczynając od pustej taśmy (same zera), generuje jak najdłuższy ciąg jedynek (lub też w innym sformułowaniu: wykonuje jak najwięcej kroków), po czym zatrzymuje się (maszyna, która nie zatrzymuje się jest dyskwalifikowana).

Okazuje się, że zdefiniowana w ten sposób funkcja S(N) nie jest obliczalna, co więcej – rośnie ona szybciej niż każda funkcja obliczalna.

Początkowe wartości są znane i łatwo je wyznaczyć (np. S(3)=21), ale już dla N>4 znane są tylko dolne oszacowania wartości funkcji.

Busy Beaver jest powiązany z problemami tego typu co problem Collatza.

Zabawa w pracowitego bobra[edytuj | edytuj kod]

W swej publikacji z roku 1962, Tibor Radó prezentuje zabawę w pracowitego bobra jak następuje:

Rozpatrujemy maszynę Turinga o dwójkowym alfabecie {0, 1} i n stanach pracy (często określanych jako 1, 2, ... n lub A, B, C, ...) oraz dodatkowym stanie Stop.

Jego definicja pewnej maszyny Turinga wyglądała następująco:

  • Maszyna operuje na dwustronnej nieskończonej (czy inaczej mówiąc nieograniczonej) taśmie.
  • Funkcja zmiany stanu maszyny posiada 2 wejścia:
  1. bieżący stan maszyny oraz
  2. znak pod bieżącą pozycją taśmy
produkuje 3 wyniki:
  1. znak do zapisania nad miejscem wczytanym (może to być ten sam znak co został wczytany);
  2. kierunek ruchu (w lewo lub prawo -- "żaden" nie jest dopuszczalne w tym modelu) i
  3. stan, do którego przejść (może to być ten sam stan lub stan zatrzymania).
Tak więc jest to maszyna Turinga tego rodzaju, że jej "program" składa się z tablicy krotek 5-elementowych o postaci
(bieżący stan, bieżący znak, znak do zapisania, kierunek przesunięcia, następny stan).
  • Maszyna zatrzymuje się zawsze gdy osiągnie stan Stop.

Zacznijmy z czystą taśmą (tzn. każde miejsce na taśmie zawiera 0). Zapuszczamy maszynie (stosując raz po razie funkcję przejścia). Jeśli się zatrzyma zapisujemy liczbę jedynek jaką pozostawiła na taśmie.

Zabawa w n-stanowego pracowitego bobra (BB-n) polega na zawodach w których należy podać taką n-stanową maszynę Turinga, która pozostawia największą liczbę jedynek na taśmie nim się zatrzyma.

Żeby brać udział w tych zawodach należy podać opis n-stanowej maszyny Turinga która się zatrzymuje wraz z ilością kroków koniecznych do jej zatrzymania się. Jest istotnym aby podać liczbę kroków wymaganą do jej zatrzymania się, albowiem w przeciwnym razie nie było by możliwości falsyfikacji proklamowanego wyniku w przypadku maszyny niezatrzymującej się.

Funkcja pracowitego bobra Σ(n)[edytuj | edytuj kod]

Funkcja pracowitego bobra Σ(n) jest zdefiniowana jako ilość jedynek którą drukuje "wygrywająca" maszyna Turinga posiadająca n "stanów" (rozkazów Turinga) i zaczynająca od czystej taśmy.

Radó wykazał że istnieje dobrze określona funkcja "wygrywająca" w zabawie w pracowitego bobra:

Istnieje skończona ilość maszyn Turinga o n stanach i 2 znakach, w szczególności istnieje ich [4(n+1)]2n [1]. Ponadto jest trywialne że pośród nich są maszyny zatrzymujące się. Tak więc dla każdego n istnieje przynajmniej jedna maszyna n-stanowa, 2-znakowa TM, która się zatrzymuje.

Definiujemy:

  • E_n jako skończony i niepusty zbiór zatrzymujących się n-stanowych, 2-znakowych maszyn Turinga wyżej opisanego rodzaju (dwukierunkowa nieskończona taśma, funkcja przejścia określona krotkami 5-elementowymi, itd.).
  • \sigma(M) jest liczbą jedynek na taśmie po zatrzymaniu się maszyny Turinga M zapuszczonej na czystą taśmę (określoną dla wszystkich maszyn M z E_n).
  • \Sigma(n) = \max \{ \sigma(M) | M \in E_n \} (Największa ilość jedynek zapisanych przez jakąkolwiek n-stanową 2-znakową maszynę Turinga)

Ponieważ σ(M) jest dodatnią liczbą skończoną dla każdego zatrzymującego się M (z En), oraz ponieważ En jest niepustym zbiorem skończonym, to Σ(n) jest dobrze określoną dodatnią skończoną liczbą dla każdego n.

Σ jest nazywane funkcją pracowitego bobra i każda n-stanowa, 2-znakowa maszyna M, dla której σ(M) = Σ(n) (tzn. która osiąga maksimum) jest nazywana pracowitym bobrem (Proszę zauważyć, że może istnieć więcej niż jeden n-stanowych pracowitych bobrów. W szczególności mamy: σ(M1) = σ(M2) = Σ(n)).

Nieobliczalność Σ[edytuj | edytuj kod]

Radó dalej udowodnił, że nie istnieje funkcja obliczalna ograniczająca Σ. To znaczy, dla każdej danej funkcji obliczalnej f, musi istnieć takie n (a więc jak można wykazać nieskończenie wiele n) że f(n)< Σ(n). (Dowód podajemy poniżej.) W szczególności, Σ jest nieobliczalne.

Ponadto wynika stąd że jest nierozstrzygalnym za pomocą ogólnego algorytmu czy dany kandydat jest zwycięskim pracowitym bobrem. (Albowiem gdybyśmy algorytmicznie mogli rozstrzygnąć czy dany kandydat jest zwycięzcą, moglibyśmy otrzymać właściwą wartość Σ po prostu wyliczając wszystkich kandydatów i sprawdzając ich.)

Pomimo że nie ma pojedynczego algorytmu A, przyjmującego jako wejście n i obliczającego Σ(n) (ponieważ Σ jest nieobliczalne), to istnieje jednak algorytm An który "oblicza" Σ(n) dla każdej liczby naturalnej n (patrz przykłady w art. funkcja obliczalna). Ponadto dla dostatecznie małych n, jest możliwe obliczenie praktyczne określonych wartości funkcji pracowitego bobra. Przykładowo, łatwo jest wykazać, że Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, a z większym wysiłkiem można wykazać, że Σ(3) = 6 oraz Σ(4) = 13 (ciąg A028444 w OEIS). Σ(n) nie zostało jak dotąd obliczone w żadnym przypadku n > 4, aczkolwiek ograniczenia dolne 4098 i 10^{1439} zostały podane dla n = 5 i odpowiednio n = 6. Dla n = 12, Dewdney[1984] podaje następującą dość dużą dolną granicę:

\Sigma(12) \ \ \geqslant \ \ 6 \ \cdot \ 4096^{4096^{4096^{~.~^{~.~^{~.~^{4096^{4}}}}}}} > 4096 \uparrow \uparrow 166

gdzie 4096 występuje 166-krotnie w tej piramidzie wykładniczej, a gdzie na szczycie jest 4.

Funkcja maksymalnych przesunięć[edytuj | edytuj kod]

Shen Lin wykazał że Σ(3) = 6 w jego wspólnej z Radó publikacji z 1965 r. w Computer Studies of Turing Machine Problems.

W celu przeprowadzenia dowodu posłużył się on inną ekstremalną funkcją zatrzymujących się n-stanowych maszyn Turinga, czyli funkcją maksymalnych przesunięć. Zdefiniujmy:

  • s(M) = ilość przesunięć robionych przez M przed zatrzymaniem się dla każdego M z En
  • S(n) = \max \{ s(M) | M \in E_n \} (Największa ilość przesunięć wykonanych przez jakąkolwiek n-stanową 2-symbolową maszynę Turing)

Ponieważ te maszyny Turinga muszą wykonać przesunięcie w każdym przejściu, czy inaczej "kroku" (wraz z każdym przejściem do stanu Stop), funkcja maksymalnych przesunięć jest identyczna z funkcją maksymalnych kroków.

Jeśli teraz znamy S(n), to możemy wykonywać wszystkie n-stanowe maszyny Turinga dla S(n) kroków jedna po drugiej i zapamiętywać te które zatrzymały się z największą ilością jedynek na taśmie. Znajdziemy wówczas pracowitego bobra i ilość zapisanych przezeń jedynek będzie równa Σ(n) (ponieważ wszystkie n-stanowe maszyny Turinga, które się zatrzymają zrobią to w S(n) krokach).

Tak więc studium funkcji maksymalnych przesunięć jest blisko powiązane ze studium funkcji pracowitego bobra.

Znane wartości[edytuj | edytuj kod]

Dokładne wartości funkcji Σ(n) i S(n) są znane tylko dla n < 5. Obecnie najlepszy pracowity bóbr dla maszyny 5-stanowej produkuje 4,098 jedynek, w 47 176 870 krokach (odkryty przez Heinera Marxena i Jürgena Buntrocka w 1989 r.), istnieje jednak około 40 maszyn zachowujących się nieregularnie, o których sądzi się że nigdy się nie zatrzymują, ale dla żadnej z nich jak dotąd tego nie udowodniono. W tej chwili rekordowy bóbr 6-stanowy produkuje ponad 101439 1-en, używając ponad 102879 kroków (odkryty przez Terry’ego i Shawna Ligockich w 2007). Jak już podano wyżej te pracowite bobry są 2-znakowymi maszynami Turinga.

Milton Green skonstruował zestaw maszyn wykazujący że

\Sigma(2k+4) > 3\ \uparrow^k 3 > A(k,k) (Gdzie \uparrow jest strzałką w górę Knutha, a A jest funkcją Ackermanna)

w publikacji z 1964 r. "A Lower Bound on Rado's Sigma Function for Binary Turing Machines". Tak więc

\Sigma(10) > 3 \uparrow\uparrow\uparrow 3 = 3 \uparrow\uparrow 3^{3^3} = 3^{3^{3^{.^{.^{.^3}}}}} (z 3^{27} = 7,625,597,484,987 wyrażeniami w piramidzie potęgowania)

Natomiast obecnie znaną granicą dla Σ(6) jest 10^{1439} < 3^{3^{3^3}}, czyli porównywalnie bardzo mało.

Uogólnienia[edytuj | edytuj kod]

W każdym modelu obliczeniowym istnieje analogon pracowitego bobra. Przykładowo w uogólnieniu maszyny Turinga z n stanami i m znakami definiuje się następującą uogólnione funkcje pracowitego bobra:

  1. Σ(n, m): największa ilość nie-zer drukowanych przez n-stanową i m-znakową maszynę startującą na czystej taśmie przed zatrzymaniem, oraz
  2. S(n, m): największa ilość kroków wykonanych przez n-stanową i m-znakową maszynę startującą na czystej taśmie przed zatrzymaniem.

Np. najdłużej pracująca maszyna z 3-stanami i 3-znakami znaleziona dotychczas wykonuje 119,112,334,170,342,540 kroków przed zatrzymaniem. Najdłużej pracująca 6-stanowa i 2-znakowa maszyna mająca dodatkową tą własność że obraca taśmę przed każdym następnym krokiem generuje 6,147 jedynek po 47,339,970 kroków. Tak więc SRTM(6) ≥ 47,339,970 i ΣRTM(6) ≥ 6,147.

Podobnie można by zdefiniować analogiczną funkcję Σ dla maszyn von Neumana jako największą możliwą wartość w rejestrze, która może znaleźć się tam po zatrzymaniu dla określonej ilości rozkazów.

Zastosowania[edytuj | edytuj kod]

Poza tym, że jest to bardzo wyzywająca zabawa matematyczna, funkcje pracowitych bobrów mają dogłębne zastosowania. Wiele otwartych problemów matematycznych mogłoby zostać rozwiązanych w systematyczny sposób, jeśli znałoby się wartość S(n) dla dostatecznie dużego n[1].

Rozpatrzmy dowolną tezę, którą można by rozstrzygnąć na podstawie kontrprzykładu wśród skończonej liczby przypadków (np. hipoteza Goldbacha). Napiszmy program komputerowy kolejno sprawdzający każdą hipotezę dla rosnących wartości (w przypadku Goldbacha rozpatrywalibyśmy kolejno parzyste liczby ≥ 4 i sprawdzali, czy też nie są sumą dwóch liczb pierwszych). Zakładamy, że ten program będzie wykonywany przez n-stanową maszynę Turinga (chociaż można by też zdefiniować funkcję pracowitego bobra dla dowolnego dobrze zdefiniowanego języka programowania). Jeśli znajdzie przeciwprzykład (liczbę parzystą ≥ 4, która nie jest sumą 2 liczb pierwszych w danym przykładzie), to zatrzyma się i powiadomi nas. Jednakże, jeżeli przypuszczenie jest prawdą, to nasz program nigdy się nie zatrzyma. (Ten program zatrzymuje się tylko jeśli znajdzie przeciwprzykład.)

Ten program jest wykonywany przez n-stanową maszynę Turinga. Tak więc jeśli znamy S(n) to możemy rozstrzygnąć (w ograniczonym czasie), czy się kiedykolwiek zatrzyma czy nie, pozwalając maszynie pracować tyleż kroków. Jeśli po S(n) krokach maszyna nie zatrzymała się, to wiemy, że nigdy się nie zatrzyma, a tym samym, że nie istnieją żadne przeciwprzykłady dla danej hipotezy (w szczególności że nie ma liczby parzystej nie będącej sumą dwóch liczb pierwszych). Tak więc udowodnilibyśmy naszą hipotezę.

Zatem określone wartości (lub górnej granicy) dla S(n) można by wykorzystać do systematycznego rozwiązywania wielu otwartych problemów matematycznych (przynajmniej teoretycznie). Jednak obecne wyniki dla pracowitych bobrów wskazują, że nie będą one miały nigdy praktycznego zastosowania z dwóch powodów:

  • Udowodnienie wartości funkcji pracowitego bobra jest bardzo trudne (jak i również dla funkcji maksymalnych przesunięć). Jak dotąd wykazano jedynie wartości dla bardzo małych maszyn posiadających mniej niż 5 stanów, podczas gdy potrzebne by były 20–50 stany do konstrukcji pożytecznej maszyny.
  • Wartości funkcji pracowitego bobra (i funkcji maksymalnych przesunięć) stają się bardzo szybko ekstremalnie duże. Dla S(6) > 102879 wymagane jest już specjalne, oparte na szablonach przyspieszanie aby można było ją wykonać do zakończenia. Ponadto wiemy, że S(10) > \Sigma(10) > 3 \uparrow\uparrow\uparrow 3 co jest gigantyczną liczbą. Nawet gdybyśmy znali np. S(30), to mogłoby się okazać, że wykonanie tak wielu kroków maszyny jest praktycznie niewykonalne.

Dowód nieobliczalności dla S(n) i Σ(n)[edytuj | edytuj kod]

Załóżmy że S(n) jest funkcją obliczalną i niech EvalS oznacza maszynę Turinga obliczającą S(n). Jeśli mamy taśmę z n jedynkami to zapisze ona S(n) jedynek na taśmie i zatrzyma się. Niech Clean oznacza maszynę Turinga czyszczącą ciąg jedynek pierwotnie zapisanych na taśmie. Niech Double oznacza maszynę Turinga obliczającą funkcję n + n. Jeśli weźmiemy taśmę z n jedynkami to wyprodukuje ona 2n jedynek na tej taśmie i się zatrzyma. Następnie złóżmy Double | EvalS | Clean niech n0 będzie ilością stanów tejże maszyny. Niech Create_n0 oznacza maszynę Turinga tworzącą n0 jedynek na pierwotnie czystej taśmie. Taka maszyna może zostać trywialnie skonstruowana tak aby miała n0 stanów (stan i zapisuje 1, przesuwa głowicę w prawo i przechodzi w stan i + 1, z wyjątkiem stanu n0, który zatrzymuje). Niech N oznacza sumę n0 + n0.

Niech BadS oznacza złożenie Create_n0 | Double | EvalS | Clean. Zwróćmy uwagę, że ta maszyna ma N stanów. Zaczynając z czystą taśmą najpierw tworzy ciąg n0 jedynek a potem podwaja go, generując ciąg of N jedynek. Następnie BadS wygeneruje S(N) jedynek na taśmie i w końcu wyczyści wszystkie jedynki i zatrzyma się. Ale czyszczenie zajmie jej przynajmniej S(N) ktroków, tak więc czas pracy BadS jest z pewnością większy niż S(N), co jest sprzeczne z definicją funkcji S(n).

Nieobliczalność Σ(n) można wykazać analogicznie. W powyższym dowodzie należy zamienić maszynę EvalS na EvalΣ i Clean na Increment – prostą maszynę Turinga wyszukującą pierwszego 0-a na taśmie i zastępującą je jedynką.

Nieobliczalność S(n) można również udowodnić trywialnym odniesieniem do problemu stopu. Ponieważ S(n) jest największą ilością kroków wykonywalnych przez zatrzymującą się maszynę Turinga, każda maszyna działająca przez więcej kroków nie może się nigdy zatrzymać. Można by więc rozstrzygnąć czy dana maszyna Turinga z n stanami zatrzymuje się wykonując S(n) jej kroków; gdyby nadal się nie zatrzymała to nigdy się nie zatrzyma. Tak więc zdolność obliczenia S(n) dawała by nam rozwiązanie nierozwiązywalnego problemu stopu. Ponieważ udowodniono że nie ma takiej możliwości aby rozstrzygnąć problem zatrzymania, wnioskujemy że S(n) musi być również nieobliczalne.

Przykłady maszyn Turinga będących pracowitymi bobrami[edytuj | edytuj kod]

Przykład tablicy 3-stanowego pracowitego bobra i jego pracy podajemy pod przykłady maszyn Turinga.

To są tablice reguł dla maszyn Turinga wytwarzających Σ(1) i S(1), Σ(2) oraz S(2), Σ(3) (lecz nie S(3)), Σ(4) i S(4), oraz najlepsze znane dolne granice dla Σ(5) i S(5), oraz Σ(6) i S(6).

W danych tablicach kolumny przedstawiają bieżący stan a wiersze przedstawiają bieżący znak wczytany z taśmy. Pola tablic zawierają kolejno znak mający do zapisu na taśmie oraz kierunek ruchu i następny stan.

Każda z maszyn zaczyna w stanie A z nieskończoną taśmą zawierającą same 0-a. Tak więc pierwszym wczytanym znakiem z taśmy jest 0.

Legenda wyników: (zaczyna w pozycji podkreślonej, i zatrzymuje się w pozycji wytłuszczonej')

1-stan, 2-znaki[edytuj | edytuj kod]

A
0 P1,R,H
1 nieużywane

Wynik: 0 0 1 0 0 (1 krok, jedna "1" w sumie)

2-stany, 2-znaki[edytuj | edytuj kod]

A B
0 P1,R,B P1,L,A
1 P1,L,B P1,R,H

Wynik: 0 0 1 1 1 1 0 0 (6 kroków, cztery "1"-ki w sumie)

3-stany, 2-znaki[edytuj | edytuj kod]

A B C
0 P1,R,B P0,R,C P1,L,C
1 P1,R,H P1,R,B P1,L,A

Wynik: 0 0 1 1 1 1 1 1 0 0 (14 kroków, sześć "1"-ek w sumie).

Proszę zwrócić uwagę że w przeciwieństwie do poprzedniej maszyny ta jest jedynie wygrywającym dla Σ, a nie dla S. (S(3) = 21.)

4-stany, 2-znaki[edytuj | edytuj kod]

A B C D
0 P1,R,B P1,L,A P1,R,H P1,R,D
1 P1,L,B P0,L,C P1,L,D P0,R,A

Wynik: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 kroków, trzynaście "1"-ek w sumie)

aktualnie najlepsza będąca możliwą wygrywającą dla 5-stanów, 2-znaków[edytuj | edytuj kod]

A B C D E
0 P1,R,B P1,R,C P1,R,D P1,L,A P1,R,H
1 P1,L,C P1,R,B P0,L,E P1,L,D P0,L,A

Wynik: 4098 "1"-ek przy 8191 "0"-er rozsianych pomiędzy w 47,176,870 krokach.

bieżąca najlepsza znana 6-stanowa, 2-znakowa[edytuj | edytuj kod]

A B C D E F
0 P1,R,B P1,L,C P1,L,D P1,L,E P1,L,A P1,L,E
1 P0,L,E P0,R,A P0,R,C P0,L,F P1,L,C P1,R,H

Wyniki: ≈4.640 × 101439 jedynek w ≈2.584 × 102879 krokach.

Dokładne wartości oraz dolne granice dla niektórych S(n, m) i Σ(n, m)[edytuj | edytuj kod]

W następujących tablicach podajemy dokładne wartości oraz pewne znane dolne granice dla S(n, m) i Σ(n, m) i przypadku uogólnionych problemów pracowitego bobra. Znane dokładne wartości podajemy jako zwykłe liczby całkowite i znane dolne granice ze znakiem większe mniejsze przed nimi (≥). Uwaga: wartości podane jako "???" są ograniczone przez maksymym wszystkich wpisów z lewej i powyżej. Te maszyny albo nie zostały zbadane albo prześcignięte później przez maszynę poprzedzającą.

Maszyny Turinga osiągające dane wartości można znaleźć pod witrynami WWW Heiner Marxen's oraz Pascal Michel's. Każda z tych witryn zawiera pewne analizy niektórych maszyn Turinga i odniesienia do dowodów wartości dokładnych.

Wartości dla S(n,m)':

2-stany 3-stany 4-stany 5-stanów 6-stanów
2-znakowe 6 21 107 ≥ 47,176,870 ≥ 2.5 × 102879
3-znakowe ≥ 38 ≥ 119,112,334,170,342,540 ≥ 1.0 × 1014072  ???  ???
4-znakowe ≥ 3,932,964 ≥ 5.2 × 1013036  ???  ???  ???
5-znakowe ≥ 1.9 × 10704  ???  ???  ???  ???
6-znakowe ≥ 2.4 × 109866  ???  ???  ???  ???

Wartości dla Σ(n,m):

2-stany 3-stany 4-stany 5-stanów 6-stanów
2-znakowe 4 6 13 ≥ 4,098 ≥ 4.6 × 101439
3-znakowe ≥ 9 ≥ 374,676,383 ≥ 1.3 × 107036  ???  ???
4-znakowe ≥ 2,050 ≥ 3.7 × 106518  ???  ???  ???
5-znakowe ≥ 1.7 × 10352  ???  ???  ???  ???
6-znakowe ≥ 1.9 × 104933  ???  ???  ???  ???

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. Chaitin 1987