Schneller wachsende beschäftigte Biberfunktion

Die Standardfunktion für beschäftigte Biber macht auf die endgültige Anzahl von Symbolen ungleich Null auf dem Band aufmerksam. Wir könnten stattdessen die größte Anzahl von Symbolen ungleich Null betrachten, die zu jedem Zeitpunkt der Berechnung auf dem Band erscheinen . Die Untergrenze dieser Funktion wäre$\Sigma(n)$und die Obergrenze wäre (maximale Verschiebungsfunktion). Wurden solche Funktionen untersucht? Wenn ja, gibt es dafür bekannte Werte?$S(n)$

Angenommen, es wird eine Maschine verwendet $n$ Staaten, die irgendwann hat $X$Nicht-Null-Symbole auf dem Band. Man kann eine Maschine mit bauen$O(n)$ Zustände, die einen Lauf der Originalmaschine mit einem Bandalphabet aus drei Symbolen simulieren $\{0,1,2\}$, mit der folgenden kleinen Änderung: wann immer sich die ursprüngliche Maschine ändert $1$ zu $0$ändert die neue Maschine es in $2$;; wann immer das Band gelesen wird,$2$ wird interpretiert als $0$. Die neue Maschine endet mit$Y \in [X,2X]$ Nicht-Null-Symbole auf dem Band (wir bekommen $\Theta(X)$ anstatt $X$da für die Simulation zwei Symbole für jedes Originalsymbol verwendet werden müssen). Nennen wir es also Ihre neue Funktion$F(n)$befriedigt $B(n) \leq F(n) \leq B(O(n))$.

Ihre Funktion (nennen Sie es $F$) befriedigt offensichtlich

$$\Sigma(n) \le F(n) \le space(n)$$ wo $space(n)$ ist die maximale Anzahl von Bandquadraten, die von einem besucht werden $n$-State Stop TM in der gleichen Klasse wie die in der Definition von $\Sigma$. Außerdem, $$space(n) \le \Sigma(3n-1)$$ wie im folgenden Papier bewiesen:

Ben-Amram, AM, BA Julstrom und K. Zwick. " Ein Hinweis auf beschäftigte Biber und andere Kreaturen ." Mathematical Systems Theory 29.4 (1996).

Deshalb

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