ビジービーバー関数に基づく関数の計算不可能性

Question

しましょう $\log _b^ac$反復ベースを示します-$b$対数関数。例えば、$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

マシンが2記号のアルファベットで動作すると仮定して、チューリングマシンの任意のモデルMを選択します。$0$ 空白の記号として $1$空白以外の記号として。そのような機械を「M-machines」と呼びます。

しましょう $f(n)$ すべてのマシンが空白の入力で開始し、命令の表に最大で含まれていると仮定して、特定のMマシンが停止したときにテープで発生する可能性のある空白以外の記号の最大数を示します $n$ 動作状態。

次に、関数 $F(n)$ は次のように定義されます。 $${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.$$ どこ $x_n$ は、次のような最小の自然数です。 $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$

質問：機能は $F(n)$ どのモデルMでも計算できません（つまり、計算できるMマシンは存在しません。 $F(n)$機能、どのMを選択しても）？はい（またはいいえ）の場合、これを証明することは可能ですか？

編集「ビジービーバー」ウィキペディアの記事の「
ゲーム」セクションで説明されているモデルを選択するとします。です$F$そのようなマシンでは計算できない？これを証明する方法にも興味があります。

Answer 1

ネストされた対数は、ここではあまり効果がありません。これは計算可能な逆関数を持つ計算可能な関数であり、したがって関数$n \mapsto x_n$ そして $f$ チューリングと同等であるだけでなく、計算可能な再スケーリングを介して関連しています。

そのため、この質問に対する答えはここにも当てはまります。

チューリングマシンを、空白以外の記号の総数が次のような範囲に収まらないように設定できることは間違いありません。 $x_n$奇妙な。許容範囲を把握するためにいくつかのサイド計算を行う必要がありますが、範囲のサイズを考えると、使用できる次の間隔を決定するために必要な記号は、最終的には間隔から外れることはないと思います。

一方、自然な設定の場合、理由はわかりません $F$計算可能になるでしょう。しかし、実際に特定のセットアップでこれを証明するには、特定のチューリングマシンモデルの詳細について、私がやりたいよりもはるかに多くのことを考える必要があります。