Função de castor ocupado de crescimento mais rápido

A função padrão de movimento ocupado chama a atenção para a contagem final de símbolos diferentes de zero na fita. Em vez disso, poderíamos observar a maior quantidade de símbolos diferentes de zero que aparecem na fita em qualquer ponto do cálculo. O limite inferior dessa função seria e o limite superior seria (função de turnos máximos). Houve alguma pesquisa sobre tais funções? Em caso afirmativo, existem valores conhecidos para isso?$\Sigma(n)$$S(n)$

Suponha que exista uma máquina usando estados que, em algum momento, tenha símbolos diferentes de zero na fita. Pode-se construir uma máquina com estados que simula uma execução da máquina original com um alfabeto de fita de três símbolos , com a seguinte pequena alteração: sempre que a máquina original mudar de para , a nova máquina altera para ; sempre que a fita é lida, é interpretado como . A nova máquina termina com símbolos diferentes de zero na fita (obtemos vez de$n$$X$$O(n)$$\{0,1,2\}$$1$$0$$2$$2$$0$$Y \in [X,2X]$$\Theta(X)$$X$pois a simulação requer o uso de dois símbolos para cada símbolo original). Portanto, sua nova função, vamos chamá-la de , satisfaz .$F(n)$$B(n) \leq F(n) \leq B(O(n))$

Sua função (chame-a $F$) obviamente satisfaz

$$\Sigma(n) \le F(n) \le space(n)$$ Onde $space(n)$ é o número máximo de quadrados de fita visitados por qualquer $n$-state parada TM na mesma classe que aqueles considerados na definição de $\Sigma$. Além disso, $$space(n) \le \Sigma(3n-1)$$ conforme comprovado no seguinte artigo:

Ben-Amram, AM, BA Julstrom e K. Zwick. " Uma nota sobre castores ocupados e outras criaturas ." Teoria dos Sistemas Matemáticos 29.4 (1996).

Portanto

$$\Sigma(n) \le F(n) \le \Sigma(3n-1)$$