Nieobliczalność funkcji opartej na funkcji Busy Beaver

Question

Pozwolić $\log _b^ac$oznacza iterowaną podstawę$b$funkcja logarytmu. Na przykład,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

Wybierz dowolny model M maszyn Turinga, zakładając, że maszyna działa z alfabetem składającym się z dwóch symboli:$0$ jako pusty symbol i $1$jako niepusty symbol. Takie maszyny będziemy nazywać „maszynami M”.

Pozwolić $f(n)$ oznaczają maksymalną liczbę niepustych symboli, które mogą wystąpić na taśmie, gdy określona M-maszyna zatrzyma się, przy założeniu, że wszystkie maszyny zaczynają się od pustego wejścia, a tabela instrukcji zawiera co najwyżej $n$ stany operacyjne.

Następnie funkcja $F(n)$ jest zdefiniowany w następujący sposób: $${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.$$ gdzie $x_n$ jest najmniejszą liczbą naturalną taką, że $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$

Pytanie: to funkcja $F(n)$ nieobliczalny dla dowolnego modelu M (to znaczy nie istnieje M-maszyna, która mogłaby obliczyć $F(n)$funkcji, bez względu na to, które M wybierzemy)? Jeśli tak (lub nie), czy można to udowodnić?

EDYCJA
Załóżmy, że wybieramy model opisany w sekcji „Gra” w artykule Wikipedii „Busy Beaver” . Jest$F$nieobliczalne przez takie maszyny? Interesuje mnie też, jak to udowodnić.

Answer 1

Zagnieżdżony logarytm nie robi tutaj zbyt wiele. Jest to obliczalna funkcja z obliczalną odwrotnością, a tym samym funkcje$n \mapsto x_n$ i $f$ są nie tylko odpowiednikiem Turinga, ale są powiązane przez przeliczalne przeskalowanie.

W związku z tym odpowiedź na to pytanie ma zastosowanie również tutaj.

Z całą pewnością moglibyśmy ustawić nasze maszyny Turinga w taki sposób, że nigdy nie zapisałyby całkowitej liczby niepustych symboli mieszczących się w zakresie, który $x_n$dziwny. Musielibyśmy wykonać pewne obliczenia poboczne, aby określić dopuszczalne zakresy, ale biorąc pod uwagę rozmiar zakresów, spodziewam się, że symbole, których potrzebujemy do określenia następnego przedziału, którego możemy użyć, ostatecznie nie wyprowadzą nas z tego przedziału.

Z drugiej strony, dla naturalnej konfiguracji nie widzę powodu $F$byłby obliczalny. Ale faktycznie udowodnienie tego dla określonej konfiguracji wymagałoby dużo więcej przemyślenia na temat szczegółów konkretnego modelu maszyny Turinga, niż bym chciał.