Cálculo da função de castor ocupado

A função de turnos máximos do castor ocupado, , possui valores conhecidos para n ≤ 4 . Existe alguma razão estrutural básica por que é inconcebível encontrarmos S ( n ) para n > 4 ? O que há de tão diferente em n = 4 que n = 5 ? Ou n = 6 ? Em algum lugar ao longo do caminho, deve haver alguma diferença fundamental; caso contrário, S ( n ) seria, em princípio, computável para todos os n , então o que exatamente$S(n)$$n\leq4$$S(n)$$n>4$$n=4$$n=5$$n=6$$S(n)$$n$é essa diferença?

A razão pela qual nenhum programa pode calcular é que, se você soubesse o que S ( n ) é, poderia decidir o problema da interrupção - saberia quando parar de esperar. Por outro lado, para cada m existe um programa que calcula S ( n ) para todos os n ≤ m - apenas usa uma tabela.$S(n)$$S(n)$$m$$S(n)$$n \leq m$

Se fosse possível provar o valor de para todos os n (isto é, para todos n , poderíamos provar S ( n ) = α para alguns α ), poderíamos calcular S ( n ) pesquisando todas as provas ( isso pressupõe que nosso sistema de provas é válido). Portanto, para cada sistema de prova, existe um valor mínimo de n para o qual você não pode provar que S ( n ) = α para qualquer α .$S(n)$$n$$n$$S(n) = \alpha$$\alpha$$S(n)$$n$$S(n) = \alpha$$\alpha$

Finalmente, a razão pela qual conhecemos é provavelmente porque 4 é um número muito pequeno. O número 5 é um pouco maior e, portanto, as coisas ficam mais complicadas. Não existe uma razão profunda para sabermos S ( 4 ), mas não S ( 5 ) , assim como não há uma razão profunda para sabermos o número Ramsey R ( 4 ), mas não R ( 5 ) (embora os números de Ramsey sejam naturalmente computáveis) .$S(4)$$4$$5$$S(4)$$S(5)$$R(4)$$R(5)$

Scott Aaronson discute isso aqui . Ele e seu co-autor encontram um limite superior explícito em para o qual S ( n ) pode ser computado.$n$$S(n)$

outro ângulo, com um esboço informal de uma resposta, que levaria muito tempo para se aprofundar tecnicamente em pesquisas adicionais (ou seja, é basicamente um programa de pesquisa): há algumas evidências preliminares de que o limite do que é computável no Busy Beaver A função é uma medida da complexidade do algoritmo, com duas refs abaixo dessa dica nessa direção. [1] [2] aproximadamente, pequenas TMs com muito poucos estados não podem realizar "tanto" ou "comportamento tão sofisticado" quanto algoritmos mais complexos com mais estados. portanto, o cálculo também parece ter uma ligação profunda com a complexidade de Kolmogorov . [3] Outra maneira de ver isso é que o que é conhecido / computável sobre a função Busy Beaver também coincide estreitamente com o estado da arte do teorema automatizado. provando, que (semelhante ao avanço tecnológico) é uma fronteira que avança continuamente com base em pesquisas em matemática e ciência da computação.

[1] Problema de castor ocupado, um novo ataque de milênio , van Heuveln et al.

[2] Pequenas máquinas de Turing e competição generalizada de castores ocupados , Michel

[3] No tempo de execução dos problemas mais curtos , Batfai