As funções não computáveis ​​crescem assintoticamente maiores?

Eu li sobre números de castores ocupados e como eles crescem assintoticamente maiores do que qualquer função computável. Porque isto é assim? É por causa da não computabilidade da função de castor ocupado? Em caso afirmativo, todas as funções não computáveis ​​crescem assintoticamente maiores que as computáveis?

Editar:

Ótimas respostas abaixo, mas eu gostaria de explicar em inglês mais claro o que eu entendo delas.

Se houve uma função computável f que cresceu mais rápido que a função de ocupado beaver, isso significa que a função de ocupado ocupado é limitada por f. Em outras palavras, uma máquina de turing simplesmente precisaria executar várias etapas para decidir o problema da parada. Como sabemos que o problema da parada é indecidível, nosso pressuposto inicial está errado. Portanto, a função de castor ocupado cresce mais rápido que todas as funções computáveis.

Se você pegar um conjunto não-computável de números naturais, a função característica do conjunto usará apenas os valores e não será computável. Portanto, não é o caso de todas as funções não computáveis ​​crescerem muito rapidamente, elas podem até ser limitadas.$\{0,1\}$

A função Busy Beaver cresce mais rapidamente do que todas as funções computáveis ​​porque é construída para isso. A prova de que não é computável prossegue, primeiro provando que cresce mais rápido do que qualquer função computável.

De maneira mais geral, diga que um conjunto tem "grau livre de hiperimunidade" se todas as funções computáveis ​​de A forem delimitadas por uma função computável. Certamente todo conjunto computável possui um grau livre de hiperimunidade. Sabe-se que também existem muitos conjuntos não computáveis ​​que possuem grau livre de hiperimunidade. Portanto, não é o caso de que tudo que não é computável terá que computar alguma função de rápido crescimento. $A \subseteq \mathbb{N}$$A$

No entanto, também é o caso de um redefinição não computável não ter um grau livre de hiperimunidade. Se é re, e enumerado pelo índice e , a função f tal que f ( n ) = k se e enumera n em k etapas ef ( n ) = 0 se e não enumera n , é computável a partir de B, mas isso A função é delimitada por uma função computável se e somente se B for computável.$B$$e$$f$$f(n) = k$$e$$n$$k$$f(n) = 0$$e$$n$$B$$B$

Se uma função cresce mais rapidamente (ou mais lenta) do que qualquer função em um conjunto F de funções, que é f ∈ co ( g ) (ou o ( g ) ) para todas as funções g ∈ F , então é claro que f ∉ F . É isso que é usado para mostrar que a função de ocupado-castor não é computável. Outro exemplo é a prova de que a função - computável e total - Ackermann não é recursiva primitiva.$f$$F$$f \in \omega(g)$$o(g)$$g \in F$$f \notin F$

O inverso não se aplica necessariamente. A função de problema de parada recebe valores em assim está em O ( 1 ) ¹; claramente existem funções computáveis ​​crescendo cada vez mais rápido.$\{0,1\}$$O(1)$

Certamente, existem conjuntos de funções para as quais o tempo de execução é um critério de associação necessário e suficiente, ou seja, aqueles que são caracterizados pelo tempo de execução, como

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

1. Isso faz apenas uma quantidade limitada de sentido. O parâmetro da função HP é uma codificação de máquina de Turing e um número natural; seu tamanho não é uma medida de quão complicado é decidir parar.