ResponseEve, a responsive template by SiGa

Ten artykuł należy dopracować: → poprawić styl – powinien być encyklopedyczny, konieczna weryfikacja terminologii. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Zajęty bóbr (ang. busy beaver) – 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. W istocie maszyny, które podejrzewa się o bycie pracowitymi bobrami wykonują pewną funkcję mocno zbliżoną do funkcji Collatza^[1].

Zabawa w pracowitego bobra

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 ma 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 maszynę (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 liczbą 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łoby możliwości falsyfikacji proklamowanego wyniku w przypadku maszyny niezatrzymującej się.

Funkcja pracowitego bobra Σ(n)

Funkcja pracowitego bobra Σ(n) jest zdefiniowana jako liczba 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:

Maszyn Turinga o n stanach i 2 znakach jest skończenie wiele, istnieje ich dokładnie [4(n+1)]²ⁿ [1]. Ponadto jest oczywiste, ż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:

• ${\displaystyle E_{n}}$ jako skończony i niepusty zbiór zatrzymujących się ${\displaystyle n}$-stanowych, 2-znakowych maszyn Turinga wyżej opisanego rodzaju (dwukierunkowa nieskończona taśma, funkcja przejścia określona krotkami 5-elementowymi itd.).
• ${\displaystyle \sigma (M)}$ jest liczbą jedynek na taśmie po zatrzymaniu się maszyny Turinga ${\displaystyle M}$ zapuszczonej na czystą taśmę (określoną dla wszystkich maszyn ${\displaystyle M}$ z ${\displaystyle E_{n}}$)
• ${\displaystyle \Sigma (n)=\max\{\sigma (M)|M\in E_{n}\}}$ (największa liczba 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 E_n), oraz ponieważ E_n 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: σ(M₁) = σ(M₂) = Σ(n)).

Nieobliczalność Σ

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 A_n, 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 ${\displaystyle 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ę:

${\displaystyle \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ęć

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) = liczba przesunięć robionych przez M przed zatrzymaniem się dla każdego M z E_n
• ${\displaystyle S(n)=\max\{s(M)|M\in E_{n}\}}$ (Największa liczba 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ą liczbą jedynek na taśmie. Znajdziemy wówczas pracowitego bobra i liczbę 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

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 4098 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 10¹⁴³⁹ 1-en, używając ponad 10²⁸⁷⁹ 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ąc, że

${\displaystyle \Sigma (2k+4)>3\ \uparrow ^{k}3>A(k,k)}$ (gdzie ${\displaystyle \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

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

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

Uogólnienia

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ólnioną funkcję pracowitego bobra:

1. Σ(n, m): największa liczba 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 liczba 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 6147 jedynek po 47 339 970 krokach. Tak więc S_RTM(6) ≥ 47 339 970 i Σ_RTM(6) ≥ 6147.

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 liczby rozkazów.

Zastosowania

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^[2].

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 niebę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) > 10²⁸⁷⁹ wymagane jest już specjalne, oparte na szablonach przyspieszanie, aby można było ją wykonać do zakończenia. Ponadto wiemy, że ${\displaystyle 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)

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 jedynek, 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 jedynek, to wyprodukuje ona 2n jedynek na tej taśmie i się zatrzyma.

Następnie złóżmy Double | EvalS | Clean niech n₀ będzie liczbą stanów tejże maszyny. Niech Create_n₀ oznacza maszynę Turinga tworzącą n₀ jedynek na pierwotnie czystej taśmie. Taka maszyna może zostać trywialnie skonstruowana tak aby miała n₀ stanów (stan i zapisuje 1, przesuwa głowicę w prawo i przechodzi w stan i + 1, z wyjątkiem stanu n₀, który zatrzymuje). Niech N oznacza sumę n₀ + n₀.

Niech BadS oznacza złożenie Create_n₀ | Double | EvalS | Clean. Zwróćmy uwagę, że ta maszyna ma N stanów. Zaczynając z czystą taśmą, najpierw tworzy ciąg n₀ jedynek, a potem podwaja go, generując ciąg 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) krokó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ą pierwsze zero 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ą liczbą 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łaby 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

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

	A
0	P1,R,H
1	nieużywane

Wynik: 0 0 1 0 0 (1 krok, 1 jedynka w sumie)

2-stany, 2-znaki

	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, 4 jedynki w sumie)

3-stany, 2-znaki

	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, 6 jedynek w sumie).

Należy 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

	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, 13 jedynek w sumie)

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

	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 jedynek przy 8191 zerach rozsianych pomiędzy w 47 176 870 krokach.

bieżąca najlepsza znana 6-stanowa, 2-znakowa

	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: ≈4640 × 10¹⁴³⁹ jedynek w ≈2584 × 10²⁸⁷⁹ krokach.

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

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 maksimum 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 × 1014 072	???	???
4-znakowe	≥ 3 932 964	≥ 5,2 × 1013 036	???	???	???
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	≥ 4098	≥ 4,6 × 101439
3-znakowe	≥ 9	≥ 374 676 383	≥ 1,3 × 107036	???	???
4-znakowe	≥ 2050	≥ 3,7 × 106518	???	???	???
5-znakowe	≥ 1,7 × 10352	???	???	???	???
6-znakowe	≥ 1,9 × 104933	???	???	???	???

Zobacz też

• złożoność Kołmogorowa
• złożoność obliczeniowa

Przypisy