O castor ocupado é a função de crescimento mais rápido conhecida pelo homem?

Eu só tive essa pergunta interessante. Qual é a função de crescimento mais rápido conhecida pelo homem? É castor ocupado ?

Conhecemos funções como , mas essa função cresce mais devagar que , que por sua vez cresce mais devagar que, que por sua vez cresce mais lentamente que . Podemos então combinar funções, terque cresce mais rápido que , e assim por diante.$x^2$ x ! x x ( x x ) ! x $2^x$$x!$$x^x$$(x^x)!$$x^x$

Chegamos então a funções recursivas, como a função Ackermann que cresce muito mais rápido que. Então, as pessoas pensam sobre a função do castor ocupado que cresce ainda mais rápido que a função de Ackermann.( x x ) ! B ( x $A(x,x)$$(x^x)!$$B(x)$

Neste ponto, eu não ouvi falar de outras funções que crescem mais rápido do que o castor ocupado. Isso significa que não existem outras funções que possam crescer mais rapidamente do que um castor ocupado? (Além do fatorial de e como , etc.)A ( B ( x ) , B ( x ) $B(x)$$A(B(x), B(x))$

A função de castor ocupado cresce mais rapidamente do que qualquer função computável . No entanto, ele pode ser calculado por uma máquina de Turing que teve acesso a um oráculo para resolver o problema de parada. Você pode definir uma função de castor ocupado de "segunda ordem", que cresce mais rapidamente do que qualquer função que possa ser calculada mesmo por qualquer máquina de Turing com um oráculo para o problema de parada. Você pode continuar fazendo isso para sempre, criando uma hierarquia de funções de castores cada vez mais crescentes.

Veja o excelente ensaio de Scott Aaronson sobre este tópico, Quem pode nomear o número maior? .

Não existe "a função que mais cresce". De fato, nem sequer existe uma sequência de funções de crescimento mais rápido. Isso já foi demonstrado por Hausdorff. Dadas duas funções , diga que cresce mais rápido que se Dada uma função , a seguinte função cresce mais rapidamente que :Dada uma sequência de funções , a seguinte função cresce mais rapidamente que todas elas:$f,g\colon \mathbb{N} \longrightarrow \mathbb{N}$$g$$f$

$$\lim_{n\rightarrow\infty} \frac{g(n)}{f(n)} = \infty.$$ $f$$g$$f$ $$g(n) = nf(n).$$ $f_n$$g$ $$g(n) = n \max_{m \leq n} f_m(n).$$ Uma pergunta natural a ser feita é se existe uma "escala" de funções de crescimento mais rápido. Este é um conjunto bem ordenado de funções que é "cofinal", ou seja, dada qualquer função , existe uma função de crescimento mais rápido . (Em vez de um conjunto bem ordenado, podemos falar de forma equivalente sobre uma cadeia, ou seja, quaisquer duas funções no conjunto precisam ser comparáveis.) A existência de uma escala é independente do ZFC: assumindo CH, existe uma escala, enquanto no modelo de Cohen que falsifica CH (adicionando reais), não existe escala.$g_\alpha$$f$$g_\alpha$$\omega_1$

Outras respostas abordam a questão diretamente. Para um histórico cada vez mais profundo, este artigo de Lafitte sobre o assunto considera o contexto maior de funções ocupadas do tipo castor. Ele também possui alguns resultados e teoremas que ajustam a ideia a uma estrutura mais geral. Isso mostra que (informalmente) "funções ocupadas do tipo castor" têm uma estreita conexão com os fenômenos de incompletude de Chaitin (Teorema 2.1). Também mostra que existem teorias que não são "poderosas" o suficiente para "compreender" as funções ocupadas do tipo castor, ou seja, são improváveis ​​nessas teorias devido à incompletude relacionada a Godel. Ele mostra a idéia de assumir resultados ocupados do tipo castor como axiomas e uma progressão lógica de teorias que resulta semelhante às idéias originalmente previstas por Turing.

[1] Castores ocupados enlouquecidos por Grégory Lafitte. Abstrato:

Mostramos alguns resultados incompletos no Chaitin usando as funções de castor ocupado. Então, com a ajuda da lógica ordinal, mostramos como obter uma teoria na qual os valores das funções de castores ocupados podem ser comprovadamente estabelecidos e usamos isso para revelar uma estrutura sobre a possibilidade dos valores dessas funções.

Os teoremas da hierarquia de tempo e espaço de Hartmanis-Stearns provam que não há função de "crescimento mais rápido" em termos de tempo ou espaço, porque a escala é ilimitada. Mas fornece uma ordem de modo que todas as funções computáveis ​​/ recursivas "bem comportadas" possam ser comparadas. Mas muitas funções matemáticas de "crescimento rápido" parecem não ter sido avaliadas em termos de complexidade de tempo / espaço até agora, apesar de ser uma "lacuna" teórica um tanto óbvia ou até gritante para preencher. Fazer isso pode levar a importantes "teoremas da ponte".