Zajęty bóbr - Busy beaver

W informatyce teoretycznej , ruchliwa gra z bobrami ma na celu znalezienie programu kończącego o określonym rozmiarze, który daje największą możliwą wydajność. Ponieważ łatwo można sobie wyobrazić program zapętlający się w nieskończoność, dający nieskończone wyjście, takie programy są wykluczone z gry.

Dokładniej rzecz biorąc, pracowita gra z bobrami polega na zaprojektowaniu zatrzymującej się maszyny Turinga z binarnym alfabetem , która zapisuje na taśmie najwięcej jedynek, używając tylko określonego zestawu stanów. Zasady gry dwustanowej są następujące:

1. maszyna musi mieć dwa stany oprócz stanu zatrzymania i
2. taśma początkowo zawiera tylko zera.

Gracz powinien wyobrazić sobie stół przejściowy, którego celem jest jak najdłuższe wyjście 1s na taśmie, jednocześnie upewniając się, że maszyna w końcu się zatrzyma.

N th zajęty bóbr , BB- n lub po prostu "zajęty bobra" jest maszyną Turinga, który wygrywa n -state Busy Beaver Game. Oznacza to, że osiąga największą liczbę 1 spośród wszystkich możliwych konkurencyjnych n- stanowych maszyn Turinga. Na przykład maszyna Turinga BB-2 osiąga cztery jedynki w sześciu krokach.

Ustalenie, czy dowolna maszyna Turinga jest zajętym bobrem, jest nierozstrzygnięte . Ma to implikacje w teorii obliczalności , problemie zatrzymania i teorii złożoności . Pojęcie to zostało po raz pierwszy wprowadzone przez Tibora Radó w swoim artykule z 1962 r. „O funkcjach nieobliczalnych”.

Gra

N -state zajęty Beaver gry (lub BB- n gry ), wprowadzony w Tibor Radó 1962 papieru jest, obejmuje klasę urządzeń Turinga , z których każdy człon jest wymagane, aby spełniać następujące wymagania konstrukcyjne:

• Maszyna ma n stanów „operacyjnych” plus stan Halt, gdzie n jest dodatnią liczbą całkowitą, a jeden z n stanów jest rozróżniany jako stan początkowy. (Zazwyczaj stany są oznaczone jako 1, 2, ..., n , ze stanem 1 jako stanem początkowym, lub przez A , B , C , ... ze stanem A jako stanem początkowym.)
• Maszyna wykorzystuje pojedynczą dwukierunkową nieskończoną (lub nieograniczoną) taśmę.
• Alfabet taśmy to {0, 1}, gdzie 0 służy jako pusty symbol.
• Funkcja przejścia maszyny przyjmuje dwa wejścia:

1. aktualny stan non-Halt,
2. symbol w bieżącej komórce taśmy,

i produkuje trzy wyjścia:

1. symbol do nadpisania symbolu w bieżącej komórce taśmy (może to być ten sam symbol, co symbol nadpisany),
2. kierunek ruchu (w lewo lub w prawo; czyli przesunięcie do komórki z taśmą o jedno miejsce w lewo lub w prawo od bieżącej komórki) oraz
3. stan do przejścia (którym może być stan zatrzymania).

Istnieją zatem (4 n + 4) ^{2 n} n- stanowe maszyny Turinga spełniające tę definicję, ponieważ ogólna postać wzoru to ( symbole × kierunki × ( stany + 1)) ^{( symbole × stany )} .

Funkcja przejścia może być postrzegana jako skończona tablica z pięcioma krotkami, każda z postaci

(aktualny stan, aktualny symbol, symbol do zapisania, kierunek przesunięcia, następny stan).

"Uruchomienie" maszyny polega na uruchomieniu się w stanie początkowym, przy czym bieżąca komórka taśmy jest dowolną komórką pustej (wszystkie 0) taśmy, a następnie iteracji funkcji przejścia aż do wejścia w stan zatrzymania (jeśli kiedykolwiek). Jeśli i tylko wtedy, gdy maszyna w końcu się zatrzyma, liczba jedynek, które ostatecznie pozostały na taśmie, nazywana jest wynikiem maszyny .

N -state zajęty Beaver (BB- n ) gry jest walka na znalezienie takiego n -state maszyny Turinga mającą największy możliwy wynik - największa liczba 1S na jego taśmy po wstrzymaniu. Maszyna, która osiąga najwyższy możliwy wynik spośród wszystkich n- stanowych maszyn Turinga, nazywana jest n- stanowym zajętym bobrem, a maszyna, której wynik jest tylko najwyższy do tej pory (może nie najwyższy możliwy) jest nazywana mistrzem n- stanu maszyna.

Radó wymagał, aby do każdej maszyny zgłoszonej do konkursu było dołączone oświadczenie o dokładnej liczbie kroków, jakie należy wykonać, aby osiągnąć stan zatrzymania, co umożliwia weryfikację wyniku każdego zgłoszenia (zasadniczo) poprzez uruchomienie maszyny na podaną liczbę kroków. (Jeżeli wpisy miałyby składać się tylko z opisów maszyn, wówczas problem weryfikacji każdego potencjalnego wpisu jest nierozstrzygnięty, ponieważ jest to równoważne dobrze znanemu problemowi zatrzymania — nie byłoby skutecznego sposobu na określenie, czy dowolna maszyna w końcu się zatrzyma).

Powiązane funkcje

Funkcja zajętego bobra Σ

Funkcja zajętego bobra określa ilościowo maksymalny wynik, jaki może osiągnąć zajęty bobr w danym takcie. Jest to funkcja nieobliczalna . Ponadto można wykazać, że zajęta funkcja bobra rośnie szybciej asymptotycznie niż jakakolwiek funkcja obliczalna.

Funkcja zajętego bobra, Σ: ℕ → ℕ, jest zdefiniowana tak, że Σ( n ) jest maksymalnym osiągalnym wynikiem (maksymalna liczba jedynek na końcu na taśmie) wśród wszystkich zatrzymujących się 2-symbolowych n- stanowych maszyn Turinga z powyższych: opisanego typu, po uruchomieniu na czystej taśmie.

Jasne jest, że Σ jest dobrze zdefiniowaną funkcją: na każde n istnieje co najwyżej skończenie wiele n- stanowych maszyn Turinga, jak powyżej, aż do izomorfizmu, stąd co najwyżej skończenie wiele możliwych czasów działania.

Ta nieskończona sekwencja Σ jest funkcją zajętego bobra , a każda n- stanowa dwusymbolowa maszyna Turinga M, dla której σ ( M ) = Σ( n ) (tzn. osiąga maksymalny wynik) nazywana jest pracowitym bobrem . Zauważ, że dla każdego n , istnieją co najmniej cztery zajęte bobry w stanie n (ponieważ przy danym zajętym bobrze w stanie n , inny uzyskuje się poprzez zmianę kierunku przesunięcia w przejściu zatrzymania, inny przez przesunięcie wszystkich zmian kierunku na przeciwny , a finał poprzez zmianę kierunku zatrzymania całkowicie zamienionego pracowitego bobra).

Nieobliczalność

Artykuł Radó z 1962 roku dowiódł, że jeśli f : ℕ → ℕ jest dowolną obliczalną funkcją , to Σ( n ) > f(n) dla wszystkich wystarczająco dużych n , a zatem, że Σ nie jest obliczalną funkcją.

Co więcej, oznacza to, że ogólny algorytm nie może rozstrzygnąć , czy dowolna maszyna Turinga jest zajętym bobrem. (Taki algorytm nie może istnieć, ponieważ jego istnienie pozwoliłoby na obliczenie Σ, co jest udowodnioną niemożliwością. W szczególności taki algorytm mógłby zostać użyty do skonstruowania innego algorytmu, który obliczałby Σ w następujący sposób: dla dowolnego danego n , każdy z skończenie wiele n- stanowych 2-symbolowych maszyn Turinga zostałoby przetestowanych, dopóki nie zostanie znaleziony zajęty n- stanowy bobr; ta zajęta maszyna bobra byłaby następnie symulowana w celu określenia jego wyniku, który z definicji jest Σ( n ).)

Mimo że Σ( n ) jest funkcją nieobliczalną, istnieje kilka małych n, dla których można uzyskać jej wartości i udowodnić, że są poprawne. Nietrudno wykazać, że Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, a z coraz większym trudem można wykazać, że Σ(3) = 6 i Σ(4) = 13 (sekwencja A028444 w OEIS ). Σ( n ) nie zostało jeszcze określone dla żadnego przypadku n > 4, chociaż ustalono dolne granice (patrz sekcja Znane wartości poniżej).

W 2016 roku Adam Yedidia i Scott Aaronson uzyskali pierwsze (wyraźne) górne ograniczenie minimalnego n, dla którego Σ( n ) jest niedowodliwe w ZFC . W tym celu skonstruowali 7910-stanową maszynę Turinga, której zachowania nie można udowodnić w oparciu o zwykłe aksjomaty teorii mnogości (teoria mnogości Zermelo-Fraenkela z aksjomatem wyboru ), przy rozsądnych hipotezach niesprzeczności ( stacjonarna własność Ramseya ). Został on później zredukowany do 1919 stanów, zlikwidowano zależność od nieruchomego majątku Ramsey, a później do 748 stanów.

Złożoność i niedowodliwość Σ

Wariant złożoności Kołmogorowa jest zdefiniowany następująco [por. Boolos, Burgess i Jeffrey, 2007]: Złożoność liczby n to najmniejsza liczba stanów potrzebna dla maszyny Turinga klasy BB, która zatrzymuje się z pojedynczym blokiem n kolejnych jedynek na początkowo czystej taśmie. Odpowiedni wariant twierdzenia o niezupełności Chaitina stwierdza, że ​​w kontekście danego systemu aksjomatycznego dla liczb naturalnych istnieje taka liczba k , że nie można udowodnić, że żadna konkretna liczba ma złożoność większą niż k , a zatem nie ma określonej górnej granicy. można udowodnić dla Σ( k ) (to ostatnie wynika z tego, że „złożoność n jest większa niż k ” zostałaby udowodniona, gdyby udowodniono „ n > Σ( k )”). Jak wspomniano w cytowanym piśmie, dla każdego systemu aksjomatycznego „matematyki zwykłej” najmniejsza wartość k, dla której jest to prawdą, jest znacznie mniejsza niż 10↑↑10 ; w konsekwencji, w kontekście zwykłej matematyki, ani wartość, ani górna granica Σ(10 ↑↑ 10) nie mogą być udowodnione. ( Pierwsze twierdzenie Gödla o niezupełności ilustruje następujący wynik: w aksjomatycznym systemie zwykłej matematyki istnieje prawdziwe, ale niedowodliwe zdanie postaci "Σ(10 ↑↑ 10) = n ", a jest nieskończenie wiele prawdziwych- zdania, których nie można udowodnić w postaci "Σ(10 ↑↑ 10) < n ".)

Maksymalna funkcja przesunięć S

Oprócz funkcji Σ, Radó [1962] wprowadził inną ekstremalną funkcję dla klasy BB maszyn Turinga, funkcję maksymalnych przesunięć , S , zdefiniowaną w następujący sposób:

• s ( M ) = liczba przesunięć dokonywanych przez M przed zatrzymaniem, dla dowolnego M w E _n ,
• S ( n ) = max{ s ( M ) | M ∈ E _n } = największa liczba przesunięć dokonanych przez dowolną maszynę Turinga w stanie n - wstrzymującym .

Ponieważ te maszyny Turinga muszą mieć przesunięcie w każdym przejściu lub „kroku” (w tym w dowolnym przejściu do stanu zatrzymania), funkcja max-shifts jest jednocześnie funkcją max-steps.

Radó pokazał, że S jest nieobliczalne z tego samego powodu, dla którego Σ jest nieobliczalne — rośnie szybciej niż jakakolwiek funkcja obliczalna. Udowodnił to po prostu zauważając, że dla każdego n , S ( n ) ≥ Σ ( n ). Każda zmiana może zapisać 0 lub 1 na taśmie, podczas gdy Σ zlicza podzbiór zmian, które zapisały 1, a mianowicie te, które nie zostały nadpisane do czasu zatrzymania maszyny Turinga; w konsekwencji S rośnie co najmniej tak szybko, jak Σ, co już zostało udowodnione, że rośnie szybciej niż jakakolwiek funkcja obliczalna.

Poniższy związek między Σ i S został użyty przez Lin i Radó [ Computer Studies of Turing Machine Problems , 1965] do udowodnienia, że ​​Σ(3) = 6: Dla danego n , jeśli S ( n ) jest znane wtedy wszystkie n -stany Maszyny Turinga mogą (w zasadzie) być uruchamiane do S ( n ) kroków, w którym to momencie każda maszyna, która jeszcze się nie zatrzymała, nigdy się nie zatrzyma. W tym momencie, obserwując, które maszyny zatrzymały się z największą liczbą jedynek na taśmie (tj. zajęte bobry), uzyskuje się z ich taśm wartość Σ( n ). Podejście zastosowane przez Lin i Radó w przypadku n = 3 polegało na przypuszczeniu, że S (3) = 21, a następnie symulowaniu wszystkich zasadniczo różnych maszyn 3-stanowych w maksymalnie 21 krokach. Analizując zachowanie się maszyny, które nie zatrzymał się w ciągu 21 etapach, udało się wykazać, że żadne z tych urządzeń będzie zawsze zatrzymania, potwierdzając przypuszczenie, że S (3) = 21, i określenie, które Σ (3) = 6 przez procedura właśnie opisana.

Nierówności odnoszące się do Σ i S obejmują następujące (z [Ben-Amram, et al., 1996]), które są ważne dla wszystkich n  ≥ 1 :

${\ Displaystyle {\ zacząć {wyrównany} S (n) i \ geq \ Sigma (n) \ \ S (n) i \ leq (2n-1) \ Sigma (3n + 3) \ \ S (n) i < \Sigma (3n+6);\end{wyrównany}}}$

oraz asymptotycznie ulepszone ograniczenie (z [Ben-Amram, Petersen, 2002]): istnieje stała c , taka, że ​​dla wszystkich n  ≥ 2 ,

${\ Displaystyle S (n) \ leq \ Sigma \ lewo (n + \ lewo \ lceil {\ Frac {8n} {\ log _ {2} n}} \ po prawej \ rceil + c \ po prawej).}$

${\ Displaystyle S (n)}$bywa zbliżona do kwadratu , aw rzeczywistości wiele maszyn daje mniej niż . ${\ Displaystyle \ Sigma (n)}$${\ Displaystyle S (n)}$${\ Displaystyle \ Sigma ^ {2} (n)}$

Znane wartości Σ i S

Od 2016 roku wartości funkcji dla Σ( n ) i S ( n ) są znane dokładnie tylko dla n  < 5.

Obecny (od 2018 r.) 5-stanowy, zajęty mistrz bobrów produkuje 4098 1s, używając47 176 870 kroków (odkrytych przez Heinera Marxena i Jürgena Buntrocka w 1989), ale pozostaje 18 lub 19 (prawdopodobnie poniżej 10, patrz poniżej) maszyn o nieregularnym zachowaniu, które uważa się, że nigdy się nie zatrzymują, ale nie udowodniono, że biegnij w nieskończoność. Skelet wymienia 42 lub 43 niesprawdzone maszyny, ale 24 są już sprawdzone. Pozostałe maszyny zostały zasymulowane do 81,8 miliarda kroków, ale żadna się nie zatrzymała. Daniel Briggs również sprawdził kilka maszyn. Inne źródło mówi, że 98 maszyn pozostaje niesprawdzonych. Istnieje analiza wstrzymań. Jest więc prawdopodobne, że Σ(5) = 4098 i S(5) = 47176870, ale pozostaje to nieudowodnione i nie wiadomo, czy pozostały jakieś opory (stan na 2018 r.). W tej chwili rekordowy 6-stanowy mistrz produkuje ponad3,515 × 10 ^{18 267}  1s (dokładnie (25×4 ³⁰³⁴¹ +23)/9), używając over7,412 × 10 ^{36 534}  kroków (odnalezionych przez Pavela Kropitza w 2010 r.). Jak wspomniano powyżej, są to 2-symbolowe maszyny Turinga.

Proste rozszerzenie maszyny 6-stanowej prowadzi do maszyny 7-stanowej, która zapisze więcej niż 10 ^{10 10 1018 705 353} 1s do taśmy, ale bez wątpienia są znacznie bardziej zajęte maszyny 7-stanowe. Jednak inni zapracowani łowcy bobrów mają inne zestawy maszyn.

Milton Green, w swoim artykule z 1964 r. „A Lower Bound on Rado's Sigma Function for Binary Turing Machines”, skonstruował zestaw maszyn Turinga, wykazując, że

${\ Displaystyle \ Sigma (2 k)> 3 \ uparrow ^ {k-2} 3> A (k-2, k-2) \ qquad {\ mbox {dla}} k \ geq 2,}$

gdzie ↑ jest notacją Knutha ze strzałką w górę, a A jest funkcją Ackermanna .

Zatem

${\ Displaystyle \ Sigma (10)> 3 \ uparrow \ uparrow \ uparrow 3 = 3 \ uparrow \ uparrow 3 ^ {3 ^ {3}} = 3 ^ {3 ^ {3 ^ {. ^ {. ^ {. ^ {3}}}}}}}$

(przy 3 ^{3 3}  = 7 625 597 484 987 terminów w wieży wykładniczej), oraz

${\ Displaystyle \ Sigma (12)> 3 \ uparrow \ uparrow \ uparrow \ uparrow 3 = g_ {1},}$

gdzie liczba g ₁ jest ogromną wartością początkową w sekwencji, która definiuje liczbę Grahama .

W 1964 Milton Green opracował dolną granicę dla funkcji Busy Beaver, która została opublikowana w materiałach z sympozjum IEEE z 1964 r. na temat teorii obwodów przełączających i projektowania logicznego. Heiner Marxen i Jürgen Buntrock opisali to jako „nietrywialne (nie prymitywne rekurencyjne) ograniczenie dolne”. Ta dolna granica może być obliczona, ale jest zbyt skomplikowana, aby określić jako pojedyncze wyrażenie w kategoriach n. Gdy n=8 metoda daje Σ(8) ≥ 3 × (7 × 3 ⁹² - 1) / 2 ≈ 8,248 × 10 ⁴⁴ .

Z obecnych dolnych granic można wyprowadzić, że:

${\ Displaystyle \ Sigma (2k + 1)> 3 \ uparrow ^ {k-2} 31> A (k-2, k-2) \ qquad {\ mbox {dla}} k \ geq 2,}$

W przeciwieństwie do tego, najlepszym dolnym ograniczeniem prądu (stan na 2018 r.) na Σ(6) jest 10 ^{18 267} , co jest większe niż dolne ograniczenie podane we wzorze Greena, 3 ³ = 27 (co jest niewielkie w porównaniu). W rzeczywistości jest znacznie większa niż dolna granica: 3 ↑↑ 3 = 3 ^{3 3} =7 625 597 484 987 , co jest pierwszym dolnym ograniczeniem Greena dla Σ(8), a także znacznie większym niż drugie dolne ograniczenie: 3×(7×3 ⁹² −1)/2.

Σ(7) jest w ten sam sposób dużo, dużo większe niż obecne wspólne dolne ograniczenie 3 ³¹ (prawie 618 bilionów), więc drugie dolne ograniczenie jest również bardzo, bardzo słabe.

Dowód na nieobliczalność S ( n ) i Σ( n )

Załóżmy, że S ( n ) jest funkcją obliczalną i niech EvalS oznacza TM, obliczając S ( n ). Mając taśmę z n jedynek, wytworzy S ( n ) jedynek na taśmie, a następnie zatrzyma się. Niech Clean oznacza maszynę Turinga czyszczącą sekwencję jedynek początkowo zapisaną na taśmie. Niech Double oznacza maszynę Turinga obliczającą funkcję n + n . Biorąc pod uwagę taśmę z n jedynek, wytworzy ona 2 n jedynek na taśmie, a następnie zatrzyma się. Stwórzmy kompozycję Double | EwalS | Wyczyść i niech n ₀ będzie liczbą stanów tej maszyny. Niech Create_n ₀ oznacza maszynę Turinga tworzącą n ₀ jedynek na początkowo czystej taśmie. Maszyna ta może być skonstruowana w trywialny sposób, aby miała n ₀ stanów (stan i zapisuje 1, przesuwa głowę w prawo i przechodzi w stan i + 1, z wyjątkiem stanu n ₀ , który zatrzymuje się). Niech N oznacza sumę n ₀ + n ₀ .

Niech BadS oznacza kompozycję Create_n ₀ | Podwójne | EwalS | Czyste . Zauważ, że ta maszyna ma N stanów. Zaczynając od początkowo czystej taśmy, najpierw tworzy ciąg n ₀ jedynek, a następnie podwaja go, tworząc ciąg N jedynek. Następnie BadS wygeneruje S ( N ) jedynek na taśmie iw końcu wyczyści wszystkie jedynek i zatrzyma się. Ale faza czyszczenia będzie trwała co najmniej S ( N ) kroków, więc czas działania BadS jest ściśle większy niż S ( N ), co jest sprzeczne z definicją funkcji S ( n ).

W podobny sposób można udowodnić nieobliczalność Σ( n ). W powyższym dowodzie, trzeba wymieniać maszyna EvalS z EvalΣ oraz Clean z Przyrost - prosty TM, szukając pierwszego 0 na taśmie i zastąpienie go 1.

Nieobliczalność S ( n ) można również ustalić przez odniesienie do problemu zatrzymania czystej taśmy. Problem zatrzymania pustej taśmy polega na podejmowaniu decyzji dla dowolnej maszyny Turinga, czy zatrzyma się ona po uruchomieniu na pustej taśmie. Problem zatrzymania czystej taśmy jest równoważny ze standardowym problemem zatrzymania i dlatego jest również nieobliczalny. Gdyby S ( n ) było obliczalne, moglibyśmy rozwiązać problem zatrzymania pustej taśmy po prostu uruchamiając dowolną daną maszynę Turinga zn stanami dla S ( n ) kroków; jeśli jeszcze się nie zatrzyma, nigdy się nie zatrzyma. Tak więc, ponieważ problem zatrzymania czystej taśmy nie jest obliczalny, wynika z tego, że S ( n ) również musi być nieobliczalne.

Uogólnienia

Dla każdego modelu obliczeniowego istnieją proste analogi pracowitego bobra. Na przykład uogólnienie do maszyn Turinga z n stanami i m symbolami definiuje następujące uogólnione funkcje zajętego bobra :

1. Σ( n , m ): największa liczba niezerów możliwych do wydrukowania przez maszynę n -state, m -symbol uruchomioną na początkowo czystej taśmie przed zatrzymaniem, oraz
2. S ( n , m ): największa liczba kroków wykonywanych przez maszynę n- stanową, m- symbolową uruchomioną na początkowo czystej taśmie przed zatrzymaniem.

Na przykład najdłużej działająca maszyna z trzema stanami i trzema symbolami, jaka do tej pory działała 119 112 334 170 342 540 kroków przed zatrzymaniem. Najdłużej działająca maszyna z 6 stanami i 2 symbolami, która ma dodatkową właściwość odwracania wartości taśmy na każdym kroku, daje6147 1s po47 339 970 kroków. Więc S _RTM (6) ≥47 339 970 oraz Σ _RTM (6) ≥6147 .

Możliwe jest dalsze uogólnienie funkcji pracowitego bobra poprzez rozszerzenie do więcej niż jednego wymiaru.

Podobnie możemy zdefiniować analogię do funkcji Σ dla maszyn rejestrujących jako największą liczbę, która może być obecna w dowolnym rejestrze po zatrzymaniu, dla danej liczby instrukcji.

Dokładne wartości i dolne granice

Poniższa tabela zawiera dokładne wartości i niektóre znane dolne granice dla S ( n , m ) i Σ( n , m ) dla uogólnionych problemów z pracowitym bobrem. Uwaga: wpisy wymienione jako „?” są ograniczone od dołu przez maksimum wszystkich wpisów od lewej i od góry. Maszyny te albo nie zostały zbadane, albo zostały później prześcignięte przez mniejszą maszynę.

Maszyny Turinga, które osiągają te wartości, są dostępne na stronie Pascala Michela . Każda z tych stron zawiera również pewną analizę maszyn Turinga i odniesienia do dowodów dokładnych wartości.

Wartości S( n , m )
n m	2-stanowe	3-stanowe	4-stanowe	5-stanowy	6-stanowe	7-stanowe
2-symbolowe	6	21	107	47 176 870  ?	> 7,4 × 10 36 534	> 10 10 10 1018 705 353
3-symbolowe	38	≥ 119 112 334 170 342 540	> 1,0 × 10 14 072	?	?	?
4-symbol	≥ 3 932 964	> 5,2 × 10 13 036	?	?	?	?
5-symbolowe	> 1,9 × 10 704	?	?	?	?	?
6-symbolowe	> 2,4 × 10 9866	?	?	?	?	?
Wartości Σ( n , m )
n m	2-stanowe	3-stanowe	4-stanowe	5-stanowy	6-stanowe	7-stanowe
2-symbolowe	4	6	13	4098  ?	> 3,5 × 10 18 267	> 10 10 10 1018 705 353
3-symbolowe	9	≥ 374 676 383	> 1,3 × 10 7036	?	?	?
4-symbol	≥ 2050	> 3,7 × 10 6518	?	?	?	?
5-symbolowe	> 1,7 × 10 352	?	?	?	?	?
6-symbolowe	> 1,9 × 10 4933	?	?	?	?	?

Niedeterministyczne maszyny Turinga

Problem można rozszerzyć na niedeterministyczne maszyny Turinga, szukając systemu z największą liczbą stanów we wszystkich gałęziach lub gałęzi z najdłuższą liczbą kroków. Pytanie, czy dany NDTM zatrzyma się, jest nadal nieredukowalne obliczeniowo, a obliczenia wymagane do znalezienia zajętego bobra NDTM są znacznie większe niż przypadek deterministyczny, ponieważ istnieje wiele rozgałęzień, które należy wziąć pod uwagę. Dla dwustanowego, dwukolorowego systemu z p przypadkami lub regułami, tabela po prawej podaje maksymalną liczbę kroków przed zatrzymaniem i maksymalną liczbę unikalnych stanów tworzonych przez NDTM.

Aplikacje

Oprócz tego, że stanowią dość wymagającą grę matematyczną , zapracowane funkcje bobra oferują zupełnie nowe podejście do rozwiązywania czystych problemów matematycznych. Wiele otwartych problemów matematycznych można by teoretycznie, ale nie w praktyce, rozwiązać w sposób systematyczny, biorąc pod uwagę wartość S ( n ) dla wystarczająco dużego n .

Rozważ każdą hipotezę, którą można obalić za pomocą kontrprzykładu spośród policzalnej liczby przypadków (np . hipoteza Goldbacha ). Napisz program komputerowy, który będzie kolejno testował to przypuszczenie pod kątem rosnących wartości. W przypadku hipotezy Goldbacha rozważylibyśmy kolejno każdą parzystą liczbę ≥ 4 i sprawdzili, czy jest to suma dwóch liczb pierwszych. Załóżmy, że ten program jest symulowany na n- stanowej maszynie Turinga. Jeśli znajdzie kontrprzykład (liczba parzysta ≥ 4, która nie jest sumą dwóch liczb pierwszych w naszym przykładzie), zatrzymuje się i wskazuje to. Jeśli jednak przypuszczenie jest prawdziwe, nasz program nigdy się nie zatrzyma. (Ten program zatrzymuje się tylko wtedy, gdy znajdzie kontrprzykład.)

Teraz ten program jest symulowany przez n- stanową maszynę Turinga, więc jeśli znamy S ( n ), możemy zdecydować (w skończonej ilości czasu), czy kiedykolwiek się zatrzyma, po prostu uruchamiając maszynę w wielu krokach. A jeśli po S ( n ) krokach maszyna nie zatrzyma się, wiemy, że nigdy się nie zatrzyma, a zatem, że nie ma kontrprzykładów dla danej hipotezy (tj. nie ma parzystych liczb, które nie są sumą dwóch liczb pierwszych). To udowodniłoby, że przypuszczenie jest prawdziwe.

W ten sposób określone wartości (lub górne granice) dla S ( n ) mogą być użyte do systematycznego rozwiązywania wielu otwartych problemów matematycznych (w teorii). Jednak obecne wyniki dotyczące problemu pracowitych bobrów sugerują, że nie będzie to praktyczne z dwóch powodów:

• Niezwykle trudno jest udowodnić wartości dla funkcji zajętego bobra (i funkcji max shift). Udowodniono to tylko w przypadku bardzo małych maszyn z mniej niż pięcioma stanami, podczas gdy jeden prawdopodobnie potrzebowałby co najmniej 20-50 stanów, aby stworzyć użyteczną maszynę. Co więcej, każda znana dokładna wartość S ( n ) została udowodniona przez wyliczenie każdej n- stanowej maszyny Turinga i udowodnienie, czy każda się zatrzymuje, czy nie. Trzeba by obliczyć S ( n ) jakąś mniej bezpośrednią metodą, żeby było to rzeczywiście użyteczne.
• Ale nawet gdyby ktoś znalazł lepszy sposób na obliczenie S ( n ), wartości funkcji zajętego bobra (i funkcji maksymalnego przesunięcia) stają się bardzo duże, bardzo szybko. S (6) > 10^{36 534} wymaga już specjalnego przyspieszenia opartego na wzorcach, aby móc przeprowadzić symulację do końca. Podobnie wiemy, że S (10) > Σ(10) > 3 ↑↑↑ 3 to gigantyczna liczba, a S (17) > Σ(17) > G, gdzie G to liczba Grahama - ogromna liczba. Tak więc, nawet gdybyśmy wiedzieli, powiedzmy, S (30), zupełnie nierozsądne jest uruchamianie jakiejkolwiek maszyny z taką liczbą kroków. W znanej części wszechświata nie ma wystarczającej zdolności obliczeniowej, aby wykonać bezpośrednio nawetoperacje S (6).

Wybitne instancje

Skonstruowano 748-stanową binarną maszynę Turinga, która zatrzymuje się, jeśli ZFC jest niespójne. Skonstruowano 744 stanową maszynę Turinga, która zatrzymuje się, jeśli hipoteza Riemanna jest fałszywa. Skonstruowano 43-stanową maszynę Turinga, która zatrzymuje się, jeśli hipoteza Goldbacha jest fałszywa, a 27-stanowa maszyna dla tej hipotezy została zaproponowana, ale jeszcze nie zweryfikowana.

Skonstruowano 15-stanową maszynę Turinga, która zatrzymuje się, jeśli hipoteza sformułowana przez Paula Erdősa w 1979 roku jest fałszywa: dla wszystkich n > 8 istnieje co najmniej jedna cyfra 2 w podstawie 3 reprezentacji 2 ⁿ .

Przykłady

Pokazuje pierwsze 100 000 kroków czasowych aktualnie najlepszego zajętego bobra w 5 stanach. Pomarańczowy to „1”, biały to „0” (obraz skompresowany w pionie).

Są to tabele reguł dla maszyn Turinga, które generują Σ(1) i S (1), Σ(2) i S (2), Σ(3) (ale nie S (3)), Σ(4) i S (4) oraz najbardziej znane dolne ograniczenie dla (5) i S (5) oraz Σ(6) i S (6). W przypadku innych wizualizacji,

W tabelach kolumny reprezentują bieżący stan, a wiersze reprezentują bieżący symbol odczytany z taśmy. Każdy wpis w tabeli jest ciągiem trzech znaków, wskazującym symbol do zapisania na taśmie, kierunek ruchu i nowy stan (w tej kolejności). Stan zatrzymania jest pokazany jako H .

Każda maszyna zaczyna się w stanie A z nieskończoną taśmą, która zawiera same zera. Tak więc początkowy symbol odczytany z taśmy to 0.

Kluczowym wynikiem: (zaczyna się od położenia nadkreślone , zatrzymanie w położeniu podkreślone )

1-stanowy, 2-symbolowy zajęty bóbr

	A
0	1R H
1	(nieużywany)

Wynik: 0 0 1 0 0 (1 krok, jedna suma „1”)

2-stanowy, 2-symbolowy zajęty bóbr

	A	b
0	1R B	1L A
1	1L B	1R H

Wynik: 0 0 1 1 1 1 0 0 (6 kroków, łącznie cztery „1”)

Animacja 3-stanowego, 2-symbolowego zajętego bobra

3-stanowy, 2-symbolowy zajęty bóbr

	A	b	C
0	1R B	0R C	1L C
1	1R H	1R B	1L A

Wynik: 0 0 1 1 1 1 1 1 0 0 (14 kroków, sześć „1” łącznie).

W przeciwieństwie do poprzednich maszyn, ta jest pracowitym bobrem tylko dla Σ, ale nie dla S . ( S (3) = 21.)

Animacja 4-stanowego, 2-symbolowego zajętego bobra

4-stanowy, 2-symbolowy zajęty bóbr

	A	b	C	D
0	1R B	1L A	1R H	1R D
1	1L B	0L C	1L D	0R A

Wynik: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 kroków, łącznie trzynaście „1”)

obecny 5-stanowy, 2-symbolowy najlepszy pretendent (możliwy zajęty bóbr)

	A	b	C	D	mi
0	1R B	1R C	1R D	1L A	1R H
1	1L C	1R B	0L E	1L D	0L A

Wynik: 4098 „1” z 8191 „0” przeplatanymi w 47 176 870 krokach.

Zwróć uwagę na obrazek po prawej, jak to rozwiązanie jest jakościowo podobne do ewolucji niektórych automatów komórkowych .

obecny 6-stanowy, 2-symbolowy najlepszy pretendent

	A	b	C	D	mi	F
0	1R B	1R C	1L D	1R E	1L A	1L H
1	1L E	1R F	0R B	0L C	0R D	1R C

Rezultat: ≈3.515 x 10 ¹⁸²⁶⁷ "1" s w ≈7.412 x 10 ³⁶⁵³⁴ kroków.

Wizualizacje

W poniższej tabeli reguły dla każdego zajętego bobra (maksymalizacja Σ) są przedstawione wizualnie, z pomarańczowymi kwadratami odpowiadającymi „1” na taśmie, a białymi odpowiadającymi „0”. Pozycja głowy jest oznaczona czarnym jajkiem, a orientacja głowy reprezentuje stan. Poszczególne taśmy układane są poziomo, z czasem w pionie. Stan zatrzymania jest reprezentowany przez regułę, która przypisuje sobie jeden stan (głowa się nie porusza).

Ewolucja pracowitych bobrów z 1-4 stanami

Zasady dotyczące 1-stanowego zajętego bobra.

Zasady dotyczące dwustanowego zajętego bobra.

Zasady dla zajętego bobra w trzech stanach.

Zasady dla 4-stanowego zajętego bobra.

Ewolucja 1-stanowego zajętego bobra aż do zatrzymania. Stan początkowy powoduje zatrzymanie, a przed zakończeniem zapisywana jest pojedyncza „1”.

Ewolucja dwustanowego zajętego bobra aż do zatrzymania.

Ewolucja zajętego bobra w trzech stanach aż do zatrzymania.

Ewolucja 4-stanowego zajętego bobra aż do zatrzymania. Dolna linia na lewym obrazie zawija się do górnej linii prawego obrazu.

Zobacz też

• Numer Rayo
• Turmite

Uwagi

Bibliografia

Zewnętrzne linki

• Strona Heinera Marxena , który wraz z Jürgenem Bunrockiem odnalazł wspomniane wyżej zapisy dla 5- i 6-stanowej maszyny Turinga.
• Historyczne badanie wyników pracowitych bobrów Pascala Michela, które zawiera również najlepsze wyniki i pewne analizy.
• Definicja klasy RTM - Reversal Turing Machines, prosta i silna podklasa TM.
• " Millennium Attack " w Rensselaer RAIR Lab na problem zapracowanego bobra. Ten wysiłek znalazł kilka nowych rekordów i ustanowił kilka wartości dla poczwórnej formalizacji.
• Archiwum strony Daniela Briggsa i forum do rozwiązywania problemu 5-stanowego, 2-symbolowego zajętego bobra, oparte na liście nieregularnych maszyn Skelet (Georgi Georgiev).
• Aaronson, Scott (1999), Kto może wymienić największą liczbę?
• Weisstein, Eric W. „Zajęty bóbr” . MatematykaŚwiat .
• Pracowite maszyny Turinga Bóbr - Komputerfil
• Pascala Michela. Konkurs Pracowitego Bobra: przegląd historyczny . 70 stron. 2017. <hal-00396880v5>