Obliczanie funkcji zajętego bobra

Funkcja maksymalnych przesunięć bobra zajętego, , ma znane wartości dla . Czy istnieje jakiś podstawowy, strukturalny powód, dla którego jest nie do pomyślenia, abyśmy kiedykolwiek znaleźli dla ? Czym tak różni się niż ? Lub ? Gdzieś po drodze musi być jakaś zasadnicza różnica, w przeciwnym razie byłby w zasadzie obliczalny dla wszystkich , więc co dokładnie $S(n)$ $n\leq4$ $S(n)$ $n>4$ $n=4$ $n=5$ $n=6$ $S(n)$ $n$ czy to różnica?

computability busy-beaver PeteyPabPro
źródło

Odpowiedzi:

Powodem, dla którego żaden program nie może obliczyć jest to, że jeśli wiesz, co to jest możesz zdecydować o problemie zatrzymania - będziesz wiedział, kiedy przestać czekać. Z drugiej strony, dla każdego istnieje program, który oblicza dla wszystkich - po prostu używa tabeli. $S(n)$ $S(n)$ $m$ $S(n)$ $n \leq m$

$S(n)$ $n$ $n$ $S(n) = \alpha$ $\alpha$ $S(n)$ $n$ $S(n) = \alpha$ $\alpha$

$S(4)$ $4$ $5$ $S(4)$ $S(5)$ $R(4)$ $R(5)$

Yuval Filmus
źródło

S (4)

$S(4)$

S (5)

$S(5)$

S (n) = " S (n) "

$S(n)=\text{"}S(n)\text{"}$

S (n) \neq " S (n) "

$S(n)\neq\text{"}S(n)\text{"}$

Nadal nie wyjaśniłeś, dlaczego możemy być tak pewni, że S (4) jest poprawny, podczas gdy S (5) lub wyższy nigdy nie możemy wiedzieć. Czy to dlatego, że nie jesteśmy w 100% związani z S (4), ale tylko „bardzo” prawie pewni?

Dan W

Jesteśmy w 100% pewni co do S (4). Nie sądzę, aby istniał jakiś głęboki powód naszej ignorancji w odniesieniu do S (5). To tylko obecny limit naszej wiedzy.

Yuval Filmus

Uważam, że istnieje naprawdę silny system sprawdzający i 6-stanowa maszyna do kolorowania 2 kolorów, dzięki czemu można udowodnić, że nie ma w tym systemie dowodów, że nigdy się nie zatrzyma i nie zatrzyma się przed żadnym algorytmem, który można udowodnić w tym systemie w obrębie postaci googol, aby ostatecznie zatrzymać zatrzymania.

Tymoteusz

$n$ $S(n)$

PeteyPabPro
źródło

Czy możesz podać odpowiednią część?

Zły

z innej strony, z nieformalnym szkicem odpowiedzi, która zajęłaby dużo czasu, aby technicznie rozwinąć dalsze badania (tj. jest to zasadniczo program badawczy): istnieją pewne wstępne dowody na to, że granica tego, co można obliczyć w Busy Beaver funkcja jest miarą złożoności algorytmu, z dwoma referencjami poniżej tej wskazówki w tym kierunku. [1] [2] z grubsza, małe bazy TM z bardzo małą liczbą stanów nie mogą osiągnąć „tyle” lub „tak wyrafinowanego zachowania” jak bardziej złożone algorytmy z większą liczbą stanów. dlatego wydaje się, że jej obliczenie ma ścisły związek ze złożonością Kołmogorowa . [3] Innym sposobem patrzenia na to jest to, że to, co jest znane / obliczalne o funkcji Busy Beaver, jest również ściśle zbieżne z najnowocześniejszym w automatycznym twierdzeniu udowadniający, która (podobnie jak postęp technologiczny) stanowi stale postępującą granicę opartą na badaniach matematycznych i informatycznych.

[1] Problem zajętego bobra, nowy tysiącletni atak , van Heuveln i in

[2] Małe maszyny Turinga i uogólnione zawody bobrów , Michel

[3] W kwestii czasu najkrótszych problemów , Batfai

vzn
źródło