Busy Beaver 기능을 기반으로 한 기능의 비계 산성

Question

허락하다 $\log _b^ac$반복 된 기본을 나타냅니다.$b$로그 함수. 예를 들면$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

기계가 두 개의 기호 알파벳으로 작동한다고 가정 하여 임의 의 Turing 기계 모델 M을 선택하십시오 .$0$ 빈 기호로 $1$공백이 아닌 기호로. 우리는 그러한 기계를“M- 기계”라고 부를 것입니다.

허락하다 $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에 관계없이)? 예 (또는 아니오) 인 경우이를 증명할 수 있습니까?

편집 "Busy Beaver"Wikipedia 기사
의 " 게임"섹션에 설명 된 모델을 선택한다고 가정합니다 . 이다$F$그런 기계로는 계산할 수 없습니까? 이를 증명하는 방법에도 관심이 있습니다.

Answer 1

중첩 로그는 여기에서 실제로 많은 일을하지 않습니다. 계산 가능한 역을 가진 계산 가능한 함수이므로 함수는$n \mapsto x_n$ 과 $f$ 튜링과 동일 할뿐만 아니라 계산 가능한 크기 조정을 통해 관련됩니다.

따라서이 질문에 대한 답 이 여기에도 적용됩니다.

우리는 확실히 우리의 Turing 기계를 설정할 수 있습니다. $x_n$이상한. 허용 가능한 범위를 알아 내기 위해 부차 계산을해야하지만 범위의 크기를 고려할 때 사용할 수있는 다음 간격을 결정하는 데 필요한 기호가 결국 간격에서 벗어나지 않을 것으로 예상합니다.

반면에 자연스러운 설정을 위해 $F$계산할 수있을 것입니다. 그러나 실제로 특정 설정에 대해 이것을 증명하려면 내가 원하는 것보다 특정 Turing 머신 모델의 세부 사항에 대해 훨씬 더 많이 생각해야합니다.