Czy funkcje nieobliczalne stają się asymptotycznie większe?

Czytam o zajętych liczbach bobrów io tym, jak rosną one asymptotycznie większe niż jakakolwiek obliczalna funkcja. Dlaczego tak jest? Czy to z powodu niemożności obliczenia funkcji zajętego bobra? Jeśli tak, to czy wszystkie funkcje niepoliczalne stają się asymptotycznie większe niż funkcje obliczalne?

Edytować:

Świetne odpowiedzi poniżej, ale chciałbym wyjaśnić prostszym językiem, co rozumiem.

Jeśli istniała obliczalna funkcja f, która rosła szybciej niż zajęty bóbr, oznacza to, że funkcja zajętego bobra jest ograniczona przez f. Innymi słowy, maszyna Turinga musiałaby po prostu pobiec dla wielu etapów, aby zdecydować o problemie zatrzymania. Ponieważ wiemy, że problem zatrzymania jest nierozstrzygalny, nasze początkowe założenie jest błędne. Dlatego funkcja zajętego bobra rośnie szybciej niż wszystkie funkcje obliczalne.

Jeśli weźmiesz dowolny niepoliczalny zestaw liczb naturalnych, funkcja charakterystyczna tego zestawu przyjmuje tylko wartości i jest niepoliczalna. Tak więc nie jest tak, że każda funkcja, która nie jest obliczalna, rośnie bardzo szybko, można ją nawet ograniczyć.$\{0,1\}$

Funkcja Busy Beaver rośnie szybciej niż każda funkcja obliczalna, ponieważ jest do tego stworzona. Dowód na to, że jest niekompatybilny, najpierw udowadnia, że ​​rośnie szybciej niż jakakolwiek funkcja obliczalna.

Mówiąc bardziej ogólnie, powiedzmy, że zestaw ma „stopień wolny od hiperimmunizacji”, jeśli każda funkcja obliczalna z jest ograniczona funkcją obliczalną. Z pewnością każdy zestaw obliczalny ma stopień wolny od hiperimmunizacji. Wiadomo, że istnieje również wiele zestawów, które nie są obliczalne, i wykazują stopień wolny od hiperimmunizacji. Nie jest więc tak, że wszystko, co nieobliczalne, będzie musiało obliczyć jakąś szybko rosnącą funkcję. $A \subseteq \mathbb{N}$$A$

Jednak zdarza się również, że zestaw, który nie jest obliczalny, nie będzie miał stopnia wolnego od hiperimmunizacji. Jeśli jest re i wyliczone przez indeks , funkcję taką, że jeśli wylicza w krokach , i jeśli nie wylicza , można obliczyć z ale to funkcja jest ograniczona funkcją obliczalną, tylko wtedy, gdy jest obliczalna.e f f ( n ) = k e n k f ( n ) = 0 e n B $B$$e$$f$$f(n) = k$$e$$n$$k$$f(n) = 0$$e$$n$$B$$B$

Jeśli funkcja rośnie szybciej (lub wolniej) niż jakakolwiek funkcja w zestawie F funkcji, to znaczy f ∈ ω ( g ) (lub o ( g ) ) dla wszystkich funkcji g ∈ $f$$F$$f \in \omega(g)$$o(g)$$g \in F$ , to oczywiście . To jest używane do pokazania, że ​​funkcja zajętego bobra nie jest obliczalna. Innym przykładem jest dowód, że - obliczalna i całkowita - funkcja Ackermanna nie jest prymitywną rekurencyjną.$f \notin F$

Odwrotność niekoniecznie się sprawdza. Funkcja problemu zatrzymania przyjmuje wartości w $\{0,1\}$ więc jest w ¹; najwyraźniej funkcje obliczeniowe rosną tak szybko i szybciej.$O(1)$

Z pewnością istnieją zestawy funkcji, dla których środowisko wykonawcze jest zarówno niezbędnym, jak i wystarczającym kryterium członkostwa, a mianowicie funkcje charakteryzujące się środowiskiem wykonawczym, takie jak

.$\qquad \displaystyle \mathrm{Poly} = \{f : \mathbb{N} \to \mathbb{N} \mid \exists k.\, f \in O(n^k)\}$

1. To ma tylko ograniczony sens. Parametrem funkcji HP jest kodowanie maszyny Turinga i liczba naturalna; jego rozmiar nie jest miarą tego, jak skomplikowane jest podjęcie decyzji o zatrzymaniu.