Nichtberechnbarkeit einer Funktion basierend auf der Busy Beaver-Funktion

Question

Lassen $\log _b^ac$bezeichnen eine iterierte Basis-$b$Logarithmusfunktion. Beispielsweise,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

Wählen Sie ein beliebiges Modell M von Turing-Maschinen aus, vorausgesetzt, eine Maschine arbeitet mit dem Zwei-Symbol-Alphabet:$0$ als leeres Symbol und $1$als nicht leeres Symbol. Wir werden solche Maschinen "M-Maschinen" nennen.

Lassen $f(n)$ bezeichnen die maximale Anzahl von nicht leeren Symbolen, die auf dem Band auftreten können, wenn eine bestimmte M-Maschine angehalten wird, vorausgesetzt, alle Maschinen beginnen mit der leeren Eingabe und die Anweisungstabelle enthält höchstens $n$ Betriebszustände.

Dann die Funktion $F(n)$ ist wie folgt definiert: $${F}(n) = \left\{ \begin{array}{l} 0\quad {\text{if}}\;{x_n}\;{\text{is even}}{\text{,}}\\ 1\quad {\text{if}}\;{x_n}\;{\text{is odd}}{\text{,}} \end{array} \right.$$ wo $x_n$ ist die kleinste natürliche Zahl, so dass $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$

Frage: ist die Funktion $F(n)$ Nicht berechenbar für jedes Modell M (dh es gibt keine M-Maschine, die die berechnen kann $F(n)$Funktion, egal welches M wir wählen)? Wenn ja (oder nein), ist es möglich, dies zu beweisen?

BEARBEITEN
Angenommen, wir wählen ein Modell aus, das im Abschnitt "Das Spiel" im Wikipedia-Artikel "Busy Beaver" beschrieben ist . Ist$F$von solchen Maschinen nicht berechenbar? Ich bin auch daran interessiert, wie ich das beweisen kann.

Answer 1

Der verschachtelte Logarithmus macht hier nicht wirklich viel. Es ist eine berechenbare Funktion mit einer berechenbaren Inversen und damit den Funktionen$n \mapsto x_n$ und $f$ sind nicht nur Turing-Äquivalente, sondern hängen über berechenbare Neuskalierungen zusammen.

Daher gilt auch hier die Antwort auf diese Frage .

Wir könnten unsere Turing-Maschinen mit Sicherheit so einrichten, dass sie niemals eine Gesamtzahl von nicht leeren Symbolen schreiben, die in einen Bereich fallen, der dazu führen würde $x_n$seltsam. Wir müssten einige Nebenberechnungen durchführen, um akzeptable Bereiche herauszufinden, aber angesichts der Größe der Bereiche erwarte ich, dass die Symbole, die wir zur Bestimmung des nächsten Intervalls benötigen, das wir verwenden können, uns letztendlich nicht aus dem Intervall herausholen.

Andererseits sehe ich für ein natürliches Setup keinen Grund warum $F$wäre jemals berechenbar. Um dies für ein bestimmtes Setup zu beweisen, müsste man jedoch viel mehr über die Details eines bestimmten Turing-Maschinenmodells nachdenken, als ich möchte.